Prefix sum computation
AnsweredConsider the following Gurobi model:
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")
Where we are essentially just trying to fill up `ai` with as many bits as possible such that the sum of bits up to position `r` is never greater than `x[r]`.
My question is whether or not GurobiPy is "smart" in the way it goes through the constraint, i.e. if it computes a prefix sum of `ai` or instead, actually recomputes the sum for each `r<N`. The former case would be linear time, whereas the latter would be quadratic. I have a LP which contains many such sums and constraints, and I'm wondering or not it would be better to create a separate variable to store the prefix sum of each sequence to prevent GurobiPy from recomputing the sum for every constraint, but I don't want to have to do that if it already is smart enough.

Hi Bryce,
For sure such a structure would be detected and handled in the algorithmic (C) layer, but not at the Python layer, so the sum of objects would be created over and over while building the expressions. Still, model building should be a small percentage of the overall optimization time.
0
Please sign in to leave a comment.
Comments
1 comment