Prefix sum computation
Answered
Consider 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.
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
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
Post is closed for comments.
Comments
2 comments