为什么 quicksum 在 SCIP python 接口中很慢

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() 方法外，没有其他方法可以添加约束。与 Python 的内置 sum() 相比，quicksum() 显着减少了必要的时间，因为只创建了一个表达式实例，然后用单个术语迭代更新。否则，会创建很多新的表达式对象，这是非常昂贵的。

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

此外，请务必始终使用 latest PySCIPOpt version from GitHub:

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% 确定这是否是您所要求的，因为您的约束条件似乎包含二次项。希望这对其他人有帮助。

为什么 quicksum 在 SCIP python 接口中很慢

Why is quicksum very slow in SCIP python interface

python

scip