Gurobi Python API：model.addVars() 太慢

Question

我目前正在使用 Gurobi Python API 来解决大型 LP。我发现添加变量的过程花费了太多时间，在某些情况下甚至超过优化时间。我的代码大致是这样的（我删除了读取数据的部分，让它更简单）：

from gurobipy import *
import numpy as np
import time

height = 32
width = 32
size = height * width

# set dummy data
supply = [1.0] * size
demand = [1.0] * size

# compute cost
costs = ((np.arange(size) // height  - 
             np.arange(size).reshape(size,1) // height) ** 2 + \
             (np.arange(size) % width - 
              np.arange(size).reshape(size,1) % width) ** 2).ravel().tolist()

# now build up the model
model = Model("model")
model.Params.Threads = 8

# add variables to model, and record the time spent: too long (around 7.3sec ~ 7.4sec on my computer)
time_1 = time.time()
plan = model.addVars(size, size, name = "plan")
time_2 = time.time()
print(time_2 - time_1)
model.update()

# set objective
obj = LinExpr(costs, model.getVars())
model.setObjective(obj, GRB.MINIMIZE)

# add constraints
model.addConstrs(plan.sum(i, '*') == supply[i] for i in range(size))
model.addConstrs(plan.sum('*', j) == demand[j] for j in range(size))

model.optimize()

我在我的笔记本电脑上运行了这个修改后的代码，我发现使用这些虚拟数据添加变量的过程大约需要 7.3 秒到 7.4 秒，而求解时间大约是 6 到 7 秒。所以model.addVars() 函数太慢了。有没有办法改善这个？我尝试了以下操作（当然，有了这个更改，我也必须修改代码的其他部分）：

plan = model.addVars(size * size, name = "plan")

现在向模型添加变量的速度要快一些，但与求解时间相比仍然不可接受。

Answer 1

我今天遇到了同样的问题并找到了两个部分解决方案。

首先，要解决这些评论——我同意，构建这个问题的缓慢问题的唯一原因是它太容易解决了；结果，求解速度非常快，而构建速度缓慢确实成为一个问题。

但是，我不同意这会使问题变得无关紧要。有很多应用程序需要的是依次解决数千个非常简单的问题，而不是解决一个巨大的问题。在这些情况下，构建问题所需的时间是一个真正的问题。

对于上述场景，我发现了两种可能的解决方案 - 都涉及首先构建问题的“通用”版本，然后每次需要解决问题时“编辑它”。“模型编辑”过程比模型构建过程快得多，从而缓解了上述问题。两种方法如下

• 使用该函数将模型写入 MPS 文件write。每次需要求解程序时，直接编辑MPS文件来定制程序，将MPS文件读入并求解。在我的基准测试中，这比从头开始构建模型大约快 4 倍。

• 正常构建模型并将其保存在内存中。创建约束对象时存储它。之后，每次需要求解模型时，都使用该chgCoeff函数更改相关系数。在我的基准测试中，这比从头开始构建模型大约快 17-18 倍。

当然，上面假设每个待求解程序的结构足够相似，可以通过简单地改变一些系数来从另一个程序获得一个。事实上，这没有帮助，据我所知，没有简单的解决方案 - 尽管我希望有人证明我错了，但令人惊讶的是 Gurobi 没有提供此类问题的解决方案。