複数の最適解をGurobiで求めたい

整数変数の値が異なる解を列挙するには，

• PoolSearchModeを2に設定する．

• 列挙する解の個数を制限する．

• PoolGapを0にする．

として問題を解けばよい．

from gurobipy import *

model = Model("count the number of optimal solutions")

model.setParam("PoolSearchMode", 2)
model.setParam("PoolSolutions", 200)
model.setParam("PoolGap", 0)
model.setParam("SolFiles","./test")

I = [1,2,3]
x = {}
for i in I:
	x[i] = model.addVar(vtype="B", name=f"x({i})")

model.setObjective(quicksum(x[i] for i in I), GRB.MINIMIZE)
model.addConstr(quicksum(x[i] for i in I)==1, name="equal")

model.optimize()

PoolSearchModeが2の場合，目的関数を設定しても無視するようである．実行すると，test_0.sol, test_1.sol, test_2.solの3つのファイルを生成する．この場合，解の個数は3個である．それらの中身は，次のようになっている．

# Solution for model count the number of optimal solutions
# Objective value = 1
x(1) 1
x(2) 0
x(3) 0

# Solution for model count the number of optimal solutions
# Objective value = 1
x(1) 0
x(2) 1
x(3) 0

# Solution for model count the number of optimal solutions
# Objective value = 1
x(1) 0
x(2) 0
x(3) 1

もし目的関数の最適値PI*がわかっており，最適解を複数個列挙する場合は，

PI<= PI*

を制約式にすればよい．次の例では，x[1]<=0を制約として追加した．

from gurobipy import *

model = Model("count the number of optimal solutions")

model.setParam("PoolSearchMode", 2)
model.setParam("PoolSolutions", 200)
model.setParam("PoolGap", 0)
model.setParam("SolFiles","./test")

I = [1,2,3,4]
x = {}
for i in I:
	x[i] = model.addVar(vtype="B", name=f"x({i})")

model.addConstr(quicksum(x[i] for i in I)==1, name="equal")
model.addConstr(x[1]<=0)

model.optimize()

結果は以下のようになり，x(1)=0のもとで，3つの解を列挙できている．

x(1) 0
x(2) 0
x(3) 0
x(4) 1

x(1) 0
x(2) 1
x(3) 0
x(4) 0

x(1) 0
x(2) 0
x(3) 1
x(4) 0

あるいは，SolCountとSolutionNumberを使って次のようにしてもよい．

from gurobipy import *

# モデルを作成
model = Model("count the number of optimal solutions")

# 変数を定義
I = [1,2,3,4]
x = {}
for i in I:
	x[i] = model.addVar(vtype="B", name=f"x({i})")

# 制約条件を追加
model.addConstr(quicksum(x[i] for i in I)==1, name="equal")
model.addConstr(x[1]<=0)

# PoolSearchModeを2にPoolGapを0に設定
model.Params.PoolSearchMode = 2
model.Params.PoolGap = 0

# 最適化を実行
model.optimize()

# 解の列挙
if model.SolCount > 0:
    print("最適解を含むプール内の解:")
    for i in range(model.SolCount):
        model.Params.SolutionNumber = i
        print(f"Solution {i + 1}:")
        for var in model.getVars():
            print(f"{var.VarName}: {var.Xn}")
else:
    print("解が見つかりませんでした。")

出力結果は，次のようになる．

最適解を含むプール内の解:
Solution 1:
x(1): 0.0
x(2): 0.0
x(3): 0.0
x(4): 1.0
Solution 2:
x(1): 0.0
x(2): 1.0
x(3): -0.0
x(4): -0.0
Solution 3:
x(1): 0.0
x(2): -0.0
x(3): 1.0
x(4): -0.0