python - 为什么scip python接口中的quicksum很慢

Question

我在 ubuntu 上使用 scip python 接口。我正在尝试使用 quicksum 添加约束：

m.addCons(quicksum(covfinal[i,j]*weightVars[i]*weightVars[j] \
          for i in I for j in J)<=z)

由于某种原因，此步骤需要很长时间。我有I=range(2500)，J=range(2500)。有没有办法让这一步更有效？

Answer 1

目前，除了使用该方法之外，没有其他方法可以添加约束addCons()。quicksum()与 Python 的内置函数相比，显着减少了必要的时间，sum()因为只创建了一个表达式实例，然后使用单个术语进行迭代更新。否则，将创建大量新的表达式对象，这是非常昂贵的。

该命令需要一些时间的（可能）原因是因为您正在尝试添加一个具有 625 万个系数的约束 - 假设这covfinal是一个密集矩阵。

此外，请务必始终使用来自 GitHub 的最新 PySCIPOpt 版本：

Answer 2

这是一个老问题，但是，quicksum 在当前的 PySCIPOpt 中仍然运行缓慢。作为 quicksum 的替代方案，我建议创建空约束并稍后添加变量系数。这里是 MWE。

from scipy import sparse
import random
from pyscipopt import Model, quicksum, Expr
from pyscipopt.scip import Term
import time as t

## construct model:
# max {c'x}
# A * x <= b
#   A: random positive sparse matrix 200 x 300
#   b: random right hand side
#   c: objective vector
#   x: variables

numvars    = 200
numconstr  = 300
A = sparse.rand(numconstr,numvars,density=0.005,format="csr")
b = [random.uniform(1,10) for _ in range(numconstr)]
c = [random.uniform(1,10) for _ in range(numvars)]

## 1. benchmark quicksum approach:
m1 = Model()
m1.setMaximize()
x1 = [m1.addVar(obj=c[i]) for i in range(numvars)] # creating variables
t0 = t.time()
for i in range(numconstr): # generating and adding constraints in a loop
    m1.addCons(quicksum(A[i,j]*x1[j] for j in range(numvars)) <= b[i])
print("1: construction time ",t.time()-t0,"seconds")
m1.optimize()
print("1: Optimum ",m1.getObjVal())

## 2. Add rows and set coefficients
m2 = Model()
m2.setMaximize()
x3 = [m2.addVar(obj=c[i]) for i in range(numvars)] # creating variables
t0 = t.time()
constr = [m2.addCons(Expr() <= b_i) for b_i in b]
for k,a_ineq in zip(constr,A):
    X = [x3[i] for i in a_ineq.indices]
    for x,a in zip(X,a_ineq.data):
        m2.addConsCoeff(k,x,a)
print("2: construction time ",t.time()-t0,"seconds")
m2.freeTransform()
m2.optimize()
print("2: Optimum ",m2.getObjVal())

输出：

1: construction time  3.013126850128174 seconds
1: Optimum  11581263.217800427
2: construction time  0.019999980926513672 seconds
2: Optimum  11581263.217800427

不是 100% 确定这是否是您所要求的，因为您的约束似乎包含二次项。无论如何，希望这对其他人有所帮助。