cplex.linear_constraints.add對於大型模型太慢

Question

我一直在嘗試使用cplex來解決最佳運輸問題。問題模型通常非常大（在我的描述中，變量的總數是1048576（= 1024^2），約束的數量是2048）。我的問題是添加約束的過程太慢而不切實際（儘管花費在解決模型上的時間很短）。我google了這個問題，有一些提示，但我仍然找不到一個可行的解決方案。

的問題是如下：給定兩個非負矢量一個和b相同的長度1024，和1024通過-1024非負矩陣Ç。假設a的所有元素的總和與b（np.sum（a）== np.sum（b））的總和相同。我想找到一個1024×1024的非負矩陣，使得C [i，j] * X [i，j]的和最小化，受限於以下限制：所有元素的總和爲i的X -th行等於的一個的我個元件和X的Ĵ第列的所有元素來的的Ĵ個元素的總和等於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")