変数数40万の0-1変数線形計画問題を解きたい

質問

0-1変数線形計画問題を解きたいです。目的関数および制約条件は１次関数(線形)です。
ただし、変数数が40万ほどあるのですが、
こういった問題を解くことはできますか？
出来たらMATLABのライセンスがあるのでMATLABで解きたいです。（Global Optimazation ToolBoxおよびOptimazation ToolBoxのライセンスあり。）

もしくは、gruobiやNuoptのようなソフトを使えば解けるものでしょうか？
ご知見ございましたら、よろしくお願いいたします。

回答No.1

f272 · ベストアンサー

どんな問題だかわからないが，試しにこんなのを書いてみた。
元ネタは
https://qiita.com/samuelladoco/items/703bf78ea66e8369c455
の問題2です。
変数の数は全部で36万，目的関数および制約条件は１次関数になっています。
私の普段使っているPCだと問題作成に148秒，求解に46秒くらいかかっています。
# pulp_problem.py
# coding: UTF-8
import pulp
import time
import numpy as np
time_start = time.clock()
I = np.arange(600)
J = np.arange(600)
c1 = np.random.randint(0,100,360000)
c = c1.reshape((600,600))
problem = pulp.LpProblem("Problem-2", pulp.LpMinimize)
x = {}
for i in I:
for j in J:
x[i,j] = pulp.LpVariable("x({:},{:})".format(i,j), 0, 1, pulp.LpInteger)
problem += pulp.lpSum(c[i][j] * x[i,j] for i in I for j in J), "TotalCost"
for i in I:
problem += sum(x[i,j] for j in J) <= 1, "Constraint_leq_{:}".format(i)
for j in J:
problem += sum(x[i,j] for i in I) == 1, "Constraint_eq_{:}".format(j)
#print("問題の式")
#print(problem)
#print("--------")
time_stop = time.clock()
print("作成時間 = {:} (秒)".format(time_stop - time_start))
solver = pulp.solvers.PULP_CBC_CMD()
time_start = time.clock()
result_status = problem.solve(solver)
time_stop = time.clock()
print("計算結果")
print("最適性 = {:}, 目的関数値 = {:}, 計算時間 = {:} (秒)"
.format(pulp.LpStatus[result_status], pulp.value(problem.objective),
time_stop - time_start))
#print("解 x[i,j]: ")
#for i in I:
# for j in J:
# print("{:} = {:}, "
# .format(x[i,j].name, x[i,j].value()), end="")
# print("")
#print("********")

お礼

ありがとうございます。。
Pythonですねーー。
解ける例があるのですね！！
参考にしてみます m..m