考虑以下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)算法来构建它。您可以避免通过这个更程序化的循环重新创建表达式。你知道吗
但是,您可以通过添加表示累积和的平行变量列表,并使用递推公式来建立O(n)非零的等效模型 cum[i]=cum[i-1]+x[i]。这也将产生一个求解速度更快的模型。你知道吗
当N=5000时,求解时间为0.5秒,而稠密模型为16秒。你知道吗
在建模层上,gurobipy将而不是“聪明”并应用您描述的替换,因此它将逐个生成约束,每次重新计算部分和。你可以尝试为这些部分和引入辅助变量,但我猜 “哑巴”方法只有在总和真的很大的情况下才会被注意到。你知道吗
相关问题 更多 >
编程相关推荐