私はcplexを使用して最適な輸送問題を解決しようとしています。問題モデルは通常非常に大きい(私の説明では、変数の総数は1048576(= 1024^2)、制約の数は2048)。私の問題は、制約を追加するプロセスが実用的には遅すぎることです(ただし、モデルを解くのに時間がかかります)。私はこの問題を探検し、いくつかのヒントがありますが、まだ実現可能な解決策を見つけることができませんでした。次のようにcplex.linear_constraints.addは大型モデルでは遅すぎます
問題は、2つの非負ベクトルと同じ長さ1024 B、および1024によって-1024非負行列C考えます。 のの全要素の合計がb(np.sum(a)== np.sum(b))と同じであると仮定します。私は、のすべての要素の和が1であるという制約に従って、C [i、j] * X [i、j]の和が最小になる1024×1024の非負行列Xを見つけたいと思います。 Xの行目は、のI番目の要素とのJ番目の要素にXのJ番目の列のすべての要素の和に等しいと等しいですb、可能な限りiおよびj、すなわち
Minimize:
C[0,0] * X[0,0] + C[0,1] * X[0,1] + ... + C[1023,1023] * X[1023,1023]
Subject to:
All X[i,j] >= 0
X[0,0] + X[0,1] + ... + X[0,1023] == a[0]
X[1,0] + X[1,1] + ... + X[1,1023] == a[1]
...
X[1023,0] + X[1023,1] + ... X[1023,1023] == a[1023]
X[0,0] + X[1,0] + ... + X[1023,0] == b[0]
X[0,1] + X[1,1] + ... + X[1023,1] == b[1]
...
X[0,1023] + X[1,1023] + ... X[1023,1023] == b[1023]
私のコードは大体次のようなものです:(以下のコードでは、DOTは輸送モデルです。 aとbは長さが1024のリスト、Cは長さが1048576(= 1024 ** 2)のリストです。
from __future__ import print_function
import cplex
DOT = cplex.Cplex()
DOT.objective.set_sense(DOT.objective.sense.minimize)
size = 1024
# set up names of variables
nms = ["x{0}".format(i) for i in range(size * size)]
# add variables to the model
DOT.variables.add(obj = C, names = nms) # C is a nonnegative list with length 1048576
constraints = list()
for i in range(size):
constraints.append([nms[i * size : (i + 1) * size], [1.0] * size])
for i in range(size):
constraints.append(cplex.SparsePair(nms[i : size * size : size], [1.0] * size))
rhs = a + b # a, b are nonnegative lists with the same length and sum
constraint_senses = ["E"] * (size * 2)
# the following line: adding constraints to model is too slow
DOT.linear_constraints.add(lin_expr = constraints, senses = constraint_senses, rhs = rhs)
# solve the model
DOT.solve()
# print some information
print("Solution status :", DOT.solution.get_status())
print("Cost : {0:.5f}".format(DOT.solution.get_objective_value()))
print()
コメントに書き込むと、モデルに制約を追加するプロセスが遅すぎます。それをスピードアップする方法はありますか?
ご協力いただければ幸いです。前もって感謝します!
魔法のように動作します:ここで
は、インデックスを使用して、あなたの例の修正版(単なるモデル構築の一部)です!どうもありがとう! – user12345