最短路問題をGurobiで解こう! 流通最適化工学 補助資料.

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

Python を用いた Gurobi 入門 久保 幹雄. Why Python? モジュールを読み込めば何 でもできる! 最適化もできる! import gurobipy (MIP) import SCOP (CP) グラフも描ける! import networkX import matplotlib.
2 dimensional bit vector approach Mikio Kubo. TIGER/Line graph DC.tmp 9559 nodes and arcs Shortest Paths between all border nodes of 2 regions.
なぜ今Pythonか? Pythonをお薦めする18の理由
Fortran と有限差分法の 入門の入門の…
京都大学情報学研究科 通信情報システム専攻 湯淺研究室 M2 平石 拓
プログラミング言語としてのR 情報知能学科 白井 英俊.
サプライ・チェインにおける様々な最適化問題を解くための 統一言語
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
二千十三年五月 あたらしい数理最適化 出版記念セミナー 主催 近代科学社 オクトーバースカイ 共催 構造計画研究所
Ex7. Search for Vacuum Problem
スレッドの同期と、スレッドの使用例 スレッドの同期 Lockオブジェクト: lockオブジェクトの生成
Ex8. Search for Vacuum Problem(2)
言語処理系(4) 金子敬一.
Lightweight Language Weekend ls-lRシェル
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
最適化ソルバーのための Python言語入門
プログラミング序論演習.
JavaServlet&JSP入門 01K0018 中村太一.
情報工学概論 (アルゴリズムとデータ構造)
Bottle/Pythonによる Webアプリ入門
Real Time Graph 指定された計測のデータを実時間収集サーバ(LABCOM)から取得し、リアルタイムにグラフとして表示する。
1章前半.
問題 1 キーボードから入力した数の合計を計算するプログラムを 作成せよ。最初に、何個の数を入力するかその数を入力 するようにする。
10進ベーシックファイル入出力.
米澤研究室 全体ミーティング 2010/12/22 M2 渡邊裕貴.
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
ピカチュウによる オブジェクト指向入門 (新版)
テキストボックス、チェックボックス×2、コマンドボタンを配置する。 コマンドボタンに機能を与える
シミュレーション演習 G. 総合演習 (Mathematica演習) システム創成情報工学科
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.3 節 Lagrange緩和 pp
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
情報処理3 第5回目講義         担当 鶴貝 達政 11/8/2018.
割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース(マッチング) • 3種類のものを割当てる問題.
本時の目標 「簡単なプログラム言語の意味を理解し、マクロ機能を使って簡単なプログラムを作ることができる。」
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
アルゴリズムとデータ構造 2013年7月16日
MATLAB測位プログラミングの 基礎とGT (2)
第6回 2007年6月1日 応用Java (Java/XML).
AMPLについて 2011年12月2日(金) 経営システム工学科 森戸 晋.
京都大学情報学研究科 通信情報システム専攻 湯淺研究室 D1 平石 拓 2005/10/18
メタ解法設計者のための Python超入門
2016年度 植物バイオサイエンス情報処理演習 第6回 情報処理(4) データを加工する・2
情報基礎Ⅱ (第11回) 月曜4限 担当:北川 晃.
人為変数や二段階を不要とする 実数型simplex法の解き方の 提案と検証
スケジューリング最適化システム OptSeq II Pythonモジュールの使い方 補助資料:OptSeq II によるスケジューリング入門 トライアルバージョン
データ構造と アルゴリズム 第五回 知能情報学部 新田直也.
「入力」はInputBoxやテキストボックスに限らず、 セルからのデータの入力や、チェックボックス等からの入力全てを含める。
第4回 線形計画 2000年11月 第4回 線形計画.
任意数の制約階層化 2007/10/31 上田研究室 M2 西村 光弘.
Ex7. Search for Vacuum Problem
プログラムの基本構造と 構造化チャート(PAD)
Python講座 2017/5/11(木).
アルゴリズムとデータ構造 2011年7月8日課題の復習
ファイルの読み込み #!/usr/bin/env perl #Perlスクリプトの指定 open(FILE, "food.txt");
情報知能学科「アルゴリズムとデータ構造」
制約最適化モジュール SCOP   東京海洋大学 久保幹雄.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
IF文 START もしも宝くじが当たったら 就職活動する 就職活動しない YES END NO.
Selfish Routing 4章前半 岡本 和也.
情報工学Ⅱ (第9回) 月曜4限 担当:北川 晃.
Solver for COnstraint Programming:スコープ Pythonモジュールの使い方
土木計画学 第12回(1月14日) 計画における代替案の作成2 担当:榊原 弘之.
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
寡占理論(Oligopoly Theory) 第13講 Competition in Quality
岩村雅一 知能情報工学演習I 第10回(後半第4回) 岩村雅一
君ならどうする – ls-lRシェル Python編
while(<FILE>){
= 55 課題6-1 #define _CRT_SECURE_NO_WARNINGS
情報処理3 第4回目講義         担当 鶴貝 達政 12/17/2019.
Presentation transcript:

最短路問題をGurobiで解こう! 流通最適化工学 補助資料

単純な実装 キー(枝)のリスト, 費用を表す辞書 cost を返す. from gurobipy import * E, cost = multidict( {(0,1):10, (0,2):5, (1,2):2, (1,4):1, (2,1):3, (2,3):2, (3,4):6} ) V=range(5) print "E=",E print "cost=",cost E= [(0, 1), (1, 2), (2, 3), (1, 4), (3, 4), (0, 2), (2, 1)] cost= {(0, 1): 10, (1, 2): 2, (2, 3): 2, (1, 4): 1, (3, 4): 6, (0, 2): 5, (2, 1): 3} multidict( ) 関数は,辞書を入力 キー(枝)のリスト, 費用を表す辞書 cost を返す.

モデルの構築 m=Model() x={} for (i,j) in E: x[i,j] = m.addVar(name="x(%s,%s)"%(i,j)) m.update() m.addConstr( -x[0,1] - x[0,2] == -1 , name="source") m.addConstr( x[0,1] + x[2,1] -x[1,2] -x[1,4] ==0 , name="1" ) m.addConstr( x[0,2] + x[1,2] -x[2,1] -x[2,3] ==0 , name="2") m.addConstr( x[2,3] - x[3,4] ==0 , name="3") m.addConstr( x[1,4] + x[3,4] ==1 , name="sink") m.setObjective(quicksum( cost[i,j]*x[i,j] for (i,j) in E ), GRB.MINIMIZE) m.optimize()

結果の出力 最適値 Optimal Value= 9.0 0 1 0.0 1 2 0.0 1 4 1.0 2 3 0.0 2 1 1.0 3 4 0.0 0 2 1.0 source -5.0 1 3.0 2 0.0 3 2.0 sink 4.0 print "Optimal Value=",m.ObjVal for (i,j) in x: print i,j,x[i,j].X for c in m.getConstrs(): print c.ConstrName, c.Pi 最適解 モデルオブジェクト m のgetConstrs()メソッド で制約オブジェクトのリストを得る 各制約 c に対して,ConstrNameで制約名, Pi(π)で双対変数を得る! 最適双対解

より一般的な実装 隣接する点のリスト Out, Inの準備 Out= [[1, 2], [2, 4], [3, 1], [4], []] from gurobipy import * E, cost = multidict( {(0,1):10, (0,2):5, (1,2):2, (1,4):1, (2,1):3, (2,3):2, (3,4):6} ) V=range(5) Out =[ [] for i in V ] In =[ [] for i in V ] for (i,j) in E: Out[i].append(j) In[j].append(i) print "Out=",Out print "In=",In 隣接する点のリスト Out, Inの準備 Out= [[1, 2], [2, 4], [3, 1], [4], []] In= [[], [0, 2], [1, 0], [2], [1, 3]]

モデルの構築 m=Model() x={} for (i,j) in E: x[i,j] = m.addVar(name="x(%s,%s)"%(i,j)) m.update() for i in V: if i==0: m.addConstr( quicksum( x[i,j] for j in Out[i]) ==1 ) elif i==4: m.addConstr( quicksum( x[j,i] for j in In[i]) ==1 ) else: m.addConstr( quicksum( x[j,i] for j in In[i]) == quicksum( x[i,j] for j in Out[i]) ) m.setObjective(quicksum( cost[i,j]*x[i,j] for (i,j) in E ), GRB.MINIMIZE)

モデルの確認 m.update() m.write("sp.lp") Minimize 10 x(0,1) + 2 x(1,2) + 2 x(2,3) + x(1,4) + 6 x(3,4) + 5 x(0,2) + 3 x(2,1) Subject To R0: x(0,1) + x(0,2) = 1 R1: x(0,1) - x(1,2) - x(1,4) + x(2,1) = 0 R2: x(1,2) - x(2,3) + x(0,2) - x(2,1) = 0 R3: x(2,3) - x(3,4) = 0 R4: x(1,4) + x(3,4) = 1 Bounds End モデル更新 update()の後で Writeメソッド ファイル “sp.lp” が 出力される