Skip to main content
 首页 » 编程设计

python之Gurobi 前缀和优化

2024年11月24日12rubylouvre

考虑以下 Gurobi 模型:

import gurobipy as gb 
import numpy as np 
N = 100 
x = np.random.randint(10, high=2*N, size=N) 
model = gb.Model("ACC") 
amp_i_vars = model.addVars(N, vtype=gb.GRB.BINARY, name='ai') 
model.setObjective(amp_i_vars.sum(*), gb.GRB.MINIMIZE) 
model.addConstrs(gb.quicksum(amp_i_vars[i] for i in range(r+1)) <= x[r]  
                 for r in range(N), "SumConstr") 

我们基本上只是试图填充 ai使用尽可能多的位,使得位的总和达到位置 r永远不会大于 x[r] .

我的问题是 GurobiPy 在通过约束的方式上是否“智能”,即它是否计算 ai 的前缀和或者,实际上重新计算每个 r<N 的总和.前一种情况是线性时间,而后者是二次时间。我有一个包含许多这样的总和和约束的 LP,我想知道是否创建一个单独的变量来存储每个序列的前缀和以防止 GurobiPy 重新计算每个约束的总和会更好,但我不知道如果它已经足够聪明,我不想这样做。

请您参考如下方法:

您的确切公式有 O(N^2) 个非零值,因此您必须使用 O(N^2) 算法来构建它。您可以避免通过这个更具程序性的循环重新创建表达式。

import gurobipy as grb 
import numpy as np 
np.random.seed(10) 
 
N = 5000 
x = np.random.randint(10, high=2*N, size=N) 
obj = -np.random.randint(10, high=2*N, size=N) 
model = gb.Model("ACC") 
 
# more interesting objective 
amp_i_vars = model.addVars(N, vtype=grb.GRB.BINARY, name='ai', obj=obj) 
model.update() 
cum = grb.LinExpr() 
for i, ai in amp_i_vars.items(): 
    cum += ai 
    model.addConstr(cum <= x[i]) 
model.optimize() 

但是,您可以通过添加代表累积和的变量的平行列表,并使用递归来构建具有 O(n) 个非零值的等效模型 累积[i] = 累积[i - 1] + x[i]。这也将导致求解速度更快的模型。

import gurobipy as grb 
import numpy as np 
N = 5000 
np.random.seed(10) 
x = np.random.randint(10, high=2*N, size=N) 
obj = -np.random.randint(10, high=2*N, size=N) 
model = gb.Model("ACC") 
 
# more interesting objective function 
amp_i_vars = model.addVars(N, vtype=grb.GRB.BINARY, name='ai', obj=obj) 
# since cum_vars are variables, use simple upper bound 
cum_vars = model.addVars(N, vtype=grb.GRB.CONTINUOUS, name='cum', ub=x) 
 
prev_cum = 0 
for i, (ai, cum) in enumerate(zip(amp_i_vars.values(), cum_vars.values())): 
    model.addConstr(cum == prev_cum + ai, name="sum_constr." + str(i)) 
    prev_cum = cum 
model.optimize() 

对于 N=5000,这在 0.5 秒内求解,而密集模型则为 16 秒。