Gurobiに関する備忘録

初期値を与えてGurobiで解きたい。

　整数計画法メモの許容解を与えた状態で分枝限定法をスタートしたいにあるように、初期値となる解を与えてGurobiを解きたいときがある。その場合は、次に示すようなMSTファイル(IV.txt)を用意して、model.read("IV.txt")で読み込めばよい。

# initial value for transportation
x[1,1]  80.0
x[2,2] 270.0
x[3,2] 230.0
x[3,3]  20.0
x[4,3] 160.0
x[5,3] 180.0

↑　初期値ファイルIV.txtの中身

from gurobipy import *

I,d = multidict({1:80, 2:270, 3:250 , 4:160, 5:180}) # demand
J,M = multidict({1:500, 2:500, 3:500})               # capacity

c = {(1,1):4,    (1,2):6,    (1,3):9,  # cost
     (2,1):5,    (2,2):4,    (2,3):7,
     (3,1):6,    (3,2):3,    (3,3):4,
     (4,1):8,    (4,2):5,    (4,3):3,
     (5,1):10,   (5,2):8,    (5,3):4,
     }

model = Model("transportation")

# Create variables vtype="C" -> vtype="I"
x = model.addVars(I,J,vtype="I",name="x")
model.update()

model.read("IV.mst")

# Demand constraints
model.addConstrs((quicksum(x[i,j] for j in J if (i,j) in x) == d[i] for i in I), name="Demand")

# Capacity constraints
model.addConstrs((quicksum(x[i,j] for i in I if (i,j) in x) <= M[j] for j in J), name="Capacity")

# Objective
model.setObjective(quicksum(c[i,j]*x[i,j]  for (i,j) in x), GRB.MINIMIZE)

model.optimize()
print(f"Optimal value: {model.ObjVal}")

EPS = 1.e-6
for (i,j) in x:
	if x[i,j].X > EPS:
		print(f"sending quantity {x[i,j].X: >10} from factory {j: >3} to customer {i: >3}")

↑　輸送問題をGurobiで解くコード

　プログラムは、久保ら「新しい数理最適化　Python言語とGurobiで解く」、近代科学社のp.11～15の輸送問題をもとにしている。ここで、x[i,j]は工場jから顧客iに輸送される量で、通常、連続変数である。上のプログラムでは、連続変数ではなく、整数変数に置き換えている。連続変数に対して、初期値を与えても、その解を無視して解くようである。GurobiのReference Manualによれば、次のように書かれている。

A MIP start (MST) file is used to specify an initial solution for a mixed integer programming model.

　model.read("IV.txt")する前に、必ず、model.update()が必要である。参考までに、初期値を与えないときの解は、次のようになり、「新しい数理最適化」p.15の解とは異なる。最適解が複数個存在する。

Optimal value: 3370.0
sending quantity       80.0 from factory   1 to customer   1
sending quantity       20.0 from factory   1 to customer   2
sending quantity      250.0 from factory   2 to customer   2
sending quantity      250.0 from factory   2 to customer   3
sending quantity      160.0 from factory   3 to customer   4
sending quantity      180.0 from factory   3 to customer   5

　そこで、「新しい数理最適化」p.15の解を初期値（IV.mst）として与えて、上のプログラムを実行したところ、p.15の解となることを確認した。
　用いたGurobiは、Ver. 9.5.1である。