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

Presentation on theme: "最短路問題をGurobiで解こう！ 流通最適化工学 補助資料."— Presentation transcript:

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

2 単純な実装 キー（枝）のリスト， 費用を表す辞書 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 を返す．

3 モデルの構築 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()

4 結果の出力 最適値 Optimal Value= 9.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（π）で双対変数を得る！ 最適双対解

5 より一般的な実装 隣接する点のリスト 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]]

6 モデルの構築 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)

7 モデルの確認 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” が 出力される