cplex.linear_constraints.add 对于大型模型来说太慢了

Question

我一直在尝试使用 cplex 来解决最佳运输问题。问题模型通常非常大（在我下面的描述中，变量总数为 1048576 (= 1024^2)，约束数为 2048）。我的问题是添加约束的过程太慢而不实用（虽然花在解决模型上的时间很好）。我搜索了这个问题，有一些提示，但我仍然找不到可行的解决方案。

问题如下：给定两个长度相同为1024的非负向量a和b，以及一个1024× 1024 非负矩阵C。假设 a 的所有元素的总和与 b 的总和相同 (np.sum(a) == np.sum(b)).我想找到一个 1024×1024 的非负矩阵 X 使得 C[i,j] * X[i,j] 的总和最小化，受限于i-th 行的所有元素之和 X 等于 i-th 元素a 和 X 的第 j 列的所有元素之和等于 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")

cplex.linear_constraints.add 对于大型模型来说太慢了

cplex.linear_constraints.add too slow for large models

python

python-3.x

linear-programming

cplex