cplex.linear_constraints.add对于大型模型太慢 [英] cplex.linear_constraints.add too slow for large models

问题描述

我一直在尝试使用cplex解决最佳运输问题.问题模型通常非常大(在我的描述中，变量的总数为1048576(= 1024 ^ 2)，约束的数量为2048).我的问题是添加约束的过程太慢而无法实用(尽管解决模型所花费的时间很好).我用谷歌搜索了这个问题，有一些技巧，但仍然找不到可行的解决方案.

I've been trying to use cplex to solve an optimal transportation problem. The problem model is normally very large (in my description below the total number of variables are 1048576 (= 1024^2), and the number of constraints is 2048). My problem is that the process of adding constraints is far too slow to be practical ( the time spent in solving the model is fine though). I googled this issue, there are some tips, but still I couldn't find a feasible solution.

问题如下:给定两个长度为1024的非负向量 a 和 b ，以及一个1024×1024的非负矩阵 C .假设 a 的所有元素的总和与 b 的总和(np.sum(a)== np.sum(b)).我想找到一个1024×1024非负矩阵 X ，使得C [i，j] * X [i，j]的总和最小化，但要受所有总和的约束 X 的第 i 行的元素等于 a 的第 i 个元素和对于所有而言， X 的 j 列的所有元素都等于 b 的 j 元素可能的 i 和 j ，即

The problem is as follows: Given two nonnegative vectors a and b of the same length 1024, and a 1024-by-1024 nonnegative matrix C. Assuming that the sum over all elements of a is the same as that of b (np.sum(a) == np.sum(b)). I want to find a 1024-by-1024 nonnegative matrix X such that the sum of C[i,j] * X[i,j] is minimized, subject to the constraints that the sum of all elements of the i-th row of X equals to the i-th element of a and the sum of all elements of the j-th column of X equals to the j-th element of b, for all possible i and j, i.e.

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)的列表.

My code is roughly like: (in the following code DOT is the transportation model; a and b are lists with length 1024, C is a list with length 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()

正如我在评论中所写，向模型添加约束的过程太慢.有什么办法可以加快速度吗?

As I write in the comment, the process of adding constraints to the model is too slow. Is there any way to speed up it?

任何帮助将不胜感激.预先感谢！

Any help will be appreciated. Thanks in advance!

推荐答案

使用索引而不是名称将获得更好的性能.这在文档此处.

You will get much better performance using indices rather than names. This is discussed in the documentation here.

以下是使用索引的示例的修改版本(仅是模型构建部分):

Here is a modified version of your example (just the model building part) that uses indices:

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对于大型模型太慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！