Gurobi Python APIで求解途中の実行可能解を確認する
求解に時間がかかる整数計画問題を解いているとき、暫定実行可能解を図などで確認したいことがある。
Gurobi Python APIでは、callbackを用いることで実現できるので、その方法を書いていく。
例として、ランダムに設定した0-1ナップザック問題を解いていく。コードは以下の通り。(わかりやすさのために、Gurobiからのコンソールへの出力を抑制している。)
import random import gurobipy as gp from gurobipy import GRB n = 100 # 荷物の数 W = 5000 # 荷物の容量 w = [random.randint(1, 1000) for _ in range(n)] # 各荷物の重さ v = [random.randint(1, 1000) for _ in range(n)] # 各荷物の価値 # Gurobi からの出力を表示しない env = gp.Env(empty=True) env.setParam("OutputFlag", 0) env.start() model = gp.Model(env=env) x = model.addVars(n, vtype=GRB.BINARY) model.setObjective(x.prod(v), GRB.MAXIMIZE) model.addConstr(x.prod(w) <= W) model.optimize() print(model.getVars())
もし、分枝限定法で新たな解が見つかったときに、そのときのxを表示したければ、モデルを解く部分を以下のようにすればよい。
def mycallback(model, where): if where == GRB.Callback.MIPSOL: x_current = model.cbGetSolution(x) print(x_current) model.optimize(mycallback)
コーディングの都合上、他の変数に依存する変数(いわゆる従属変数)をLinExprで保持して制約に組み込むことがあるが、cbGetSolutionで直接LinExprの値を得ることはできない。
x = model.addVars(n, vtype=GRB.BINARY) model.setObjective(x.prod(v), GRB.MAXIMIZE) total_weight = x.prod(w) model.addConstr(total_weight <= W) def mycallback(model, where): if where == GRB.Callback.MIPSOL: w_sum = model.cbGetSolution(total_weight) # エラーになる。 print(w_sum) model.optimize(mycallback)
LinExprは、getVar(i)とgetCoeff(i)でそれぞれi番目の変数と係数をもってくることができるため、それを利用して計算すれば、LinExprでも求解途中に確認することができる。
def mycallback(model, where): if where == GRB.Callback.MIPSOL: w_sum = sum([total_weight.getCoeff(i) * model.cbGetSolution(total_weight.getVar(i)) for i in range(n)]) print(w_sum)
また、以下のように変数の型によって処理を分けるような関数を書いておくと、実装時に意識しなくていいため便利になる。
def get_variable_in_callback(var, model): if isinstance(var, gp.Var) or isinstance(var, gp.tupledict): return model.cbGetSolution(var) elif isinstance(var, gp.LinExpr): return sum([model.cbGetSolution(var.getVar(i)) * var.getCoeff(i) for i in range(var.size())]) else: raise TypeError()
