Fast processing of forced values from sorted list
AnsweredHello,
I'm working on a problem using gurobipy where some variables can only be taken from a specific list of values, which are not equally separated, but are sorted, e.g.:
sortedlist = [0.20, 0.33, 0.45, 0.61, 0.80, 0.85]
Then I enforce Gurobi to use these values by introducing binary values for each allowed value and a constraint that exactly one should be chosen:
binValues = model.addVars(len(sortedlist), vtype=GRB.BINARY)
value = model.addVar()
model.addConstrs(((binValues[i] == 1) >> (value == sortedlist[i]) for i in range(len(sortedlist))))
model.addConstr(gp.quicksum(binValues[i] for i in range(len(sortedlist))) == 1)
Furthermore, I have a constraint that the value should be smaller than a certain other variable:
model.addConstr(value <= value2)
If we set value2 = 0.4, and the objective is to maximize value, I assume Gurobi is still trying the other values in the list even if it concluded that 0.45 is not feasible.
So, first my question is if that is true? And if yes, is there a way to tell Gurobi to stop processing the sorted list at this point, in order to reduce the computation time?
-
Official comment
-
Gurobi Staff
Our solver does not rely on enumeration to see whether a point is feasible or not. In fact, this approach does not work on real-world problems, as they typically have an astronomical number of feasible solutions.
In a nutshell, our solver considers the feasible region (i.e. a mathematical object representing the set of feasible points). Geometrically, each constraint in Linear Programming is defined either as a hyperplane or a half-space; the feasible region, which happens to be a convex set, is simply the intersection of these. Then, it considers the objective function to get the direction of maximum improvement (a.k.a. the gradient) to get the point(s) within this feasible region that optimize(s) the given criterion. Any optimal point always lies either on a vertex or an edge (i.e. a convex combination of some vertices) of the feasible region. The Simplex method consists in visiting promising vertices until no improvement can be made.
Finally, while your implementation looks correct, there's an alternative: Instead of specifying an indicator constraint for each element in the list, you can specify a single constraint that forces the variable value to be equal to a weighed sum of the binary variables, where each weight is the corresponding element in the list.
-
-
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 Juan,
Thank you for the clear explanation and suggestion for an alternative way of formulating this problem.
0 -
Post is closed for comments.
Comments
3 comments