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")