cplex.linear_constraints.addは大型モデルでは遅すぎます

Question

私はcplexを使用して最適な輸送問題を解決しようとしています。問題モデルは通常非常に大きい（私の説明では、変数の総数は1048576（= 1024^2）、制約の数は2048）。私の問題は、制約を追加するプロセスが実用的には遅すぎることです（ただし、モデルを解くのに時間がかかります）。私はこの問題を探検し、いくつかのヒントがありますが、まだ実現可能な解決策を見つけることができませんでした。次のように

問題は、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() 

コメントに書き込むと、モデルに制約を追加するプロセスが遅すぎます。それをスピードアップする方法はありますか？

ご協力いただければ幸いです。前もって感謝します！

Answer 1

名前ではなくインデックスを使用すると、パフォーマンスが大幅に向上します。これについては、hereのマニュアルを参照してください。

from __future__ import print_function 
import cplex 

DOT = cplex.Cplex() 
DOT.objective.set_sense(DOT.objective.sense.minimize) 

size = 1024 
C = [1.0] * (size * size) # dummy data 
# set up names of variables 
nms = ["x{0}".format(i) for i in range(size * size)] 
# add variables to the model and store indices as a list 
nmindices = list(DOT.variables.add(obj = C, names = nms)) 

constraints = list() 
for i in range(size): 
    constraints.append([nmindices[i * size : (i + 1) * size], [1.0] * size]) 

for i in range(size): 
    constraints.append(cplex.SparsePair(nmindices[i : size * size : size], [1.0] * size)) 
rhs = [1.0] * (size * 2) # dummy data 
constraint_senses = ["E"] * (size * 2) 
# the following line: adding constraints to model is faster now 
DOT.linear_constraints.add(lin_expr = constraints, senses = constraint_senses, rhs = rhs) 
# write out the model in LP format for debugging 
DOT.write("test.lp")