こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

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

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

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

投稿日時 - 2018-10-09 10:09:32

QNo.9545785

困ってます

質問者が選んだベストアンサー

どんな問題だかわからないが,試しにこんなのを書いてみた。
元ネタは
https://qiita.com/samuelladoco/items/703bf78ea66e8369c455
の問題2です。
変数の数は全部で36万,目的関数および制約条件は1次関数になっています。
私の普段使っている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("********")

投稿日時 - 2018-10-09 19:35:27

お礼

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

投稿日時 - 2018-10-09 19:58:19

ANo.1

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(1)

あなたにオススメの質問