最短路問題をGurobiで解こう！

最短路問題をGurobiで解こう！
流通最適化工学
補助資料
単純な実装
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}
)
E= [(0, 1), (1, 2), (2, 3), (1, 4), (3, 4), (0, 2),
V=range(5)
(2, 1)]
print "E=",E
cost= {(0, 1): 10, (1, 2): 2, (2, 3): 2, (1, 4):
print "cost=",cost
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()
結果の出力
最適値
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（π）で双対変数を得る！
最適双対解
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
より一般的な実装
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, Inの準備
Out =[ [] for i in V ]
In =[ [] for i in V ]
Out= [[1, 2], [2, 4], [3, 1], [4], []]
for (i,j) in E:
In= [[], [0, 2], [1, 0], [2], [1, 3]]
Out[i].append(j)
In[j].append(i)
print "Out=",Out
print "In=",In
モデルの構築
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")
モデル更新 update()の後で
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

Download Report