general discrete variables in gurobi
Answered
Dear Gurobi-Team,
is there any (direct) way to model general discrete variables in gurobi?
What I mean are variables that take ("countable") specific integer or also specific non-integer values, e.g.:
d = {1, 5, 6, 7, 10}.
[This example is not my application, but I wanted to keep the example simple]
Of course, I could model the general discrete variable with the help of one binary variable for each discrete value and the following exemplary constraints:
d = b1*1 + b2*5 + b3*6 + b4*7 + b5*10
b1 + b2 + b3 +b4 +b5 =1
But I think this enlarges the model and may not be optimal for the solving process, because relexations are non-unique, e.g.:
d = 6 = 0*1 + 0*5 + 1*6 + 0*7 + 0*10
d = 6 = 0*1 + 0*5 + 0*6 + 0*7 + 0.6*10
d = 6 = 0*1 + 0.5*5 + 0*6 + 0.5*7 + 0*10 .......
and with respect to the branch & bound/cut process, multiple binary variables have to be handeld instead of one discrete variable that can be branched&bounded.
Thanks in advance
Thomas
-
Hi Thomas,
There isn't a way to specify a subset of integer values via the API, but one alternative would be to introduce a binary variable for each break in the integer sequence. Since we have a break from 1 to 5, and 7 to 10 we could introduce x and y and assuming the integer variables is v we could use the following formulation
v <= 1 + (v.ub - 1)*x
v >= v.lb + (5 - v.lb)*x
v <= 7 + (v.ub - 7)*y
v >= v.lb + (10 - v.lb)*y
y <= x # one of these constraints for every pair of auxiliary binary variablesIn this formulation we have more constraints, less variables, whether it works better in practice would be subject to experiment and probably very much dependent on the exact details of the problem. But, you can also set these constraints to be Lazy, as if the value of the integer variable in the optimum solution naturally takes one of the allowed values then these constraints simply aren't needed.
- Riley
0 -
Hi Riley,
thank you very much for your answer - your suggestion is an interesting "modeling trick" to me.
It also gave me another idea to reduce the number of constraints. What do you think about the following approach, where v is the discrete variable and x & y are auxiliary binary variables, as in your suggestion? The idea is similar to semi-continous variables, but with multiple steps/breaks:
v <= 1 + (7-1)*x + (10-1)*y
v >= 1 + (5-1)*x + (10-1)*y
x + y <= 1But in general I am looking for a "smart way" to model general discrete variables with non-integer values and with non-constant distance between the values. In my actual problem I need:
d = {1^(1/3), 2^(1/3), 3^(1/3), 4^(1/3), ...}.
Do you have an idea for something like that?0 -
Hi Thomas,
That's another nice way to model the problem. I suspect these different ways of modeling the problem are exploring the tradeoff between LP size and strength of the LP relaxation, and so what works best will be dependent on the actual numbers involved and how many of these types of discrete variables are in your problem.
For your specific case you can define an integer variable x and a continuous variable d, both with lower bound 1, then use addGenConstrPow to link them
addGenConstrPow(x, d, 1/3)
or alternatively
addGenConstrPow(d, x, 3)
Not sure whether there is an advantage of one over the other but seems like it would be relatively simple to test assuming that the model doesn't run too long (because ideally the comparison would be across many seeds).
- Riley
0 -
Hi Riley,
addGenContrPow is an interesting option. I knew it existed, but it didn't come to my mind to use it for my specific problem ...
As far as I know, Gurobi internaly uses some kind of piecewise linearization to implement GenContrPow. So I could implement a piecewise linearization myself directly with addGenConstrPWL and breakpoints at the values I want to be represented exactly, couldn't I?
addGenConstrPWL(d, y, [1, 2, 3, 4], [1^(1/3), 2^(1/3), 3^(1/3), 4^(1/3)])
Are there any (dis)advantages known in comparision of Pow and Pwl?
But all this seems to "blow up" my problem, because additional variables and constraints are necessary.
Perhaps I imagine it to be too simple, but wouldn't it be a nice feature for Gurobi to have an additional variable type that allows to provide specific feasible values to the solver, e.g. the following set:
{1^(1/3), 2^(1/3), 3^(1/3), 4^(1/3), ...} = {1, 1.26, 1.44, 1.59, ...}.
Let's assume the continuous relexation finds 1.3 as the optimal value, then branching could be used to produce two subproblems/nodes with d1<=1.26 and d2>=1.44.
Obviously Gurobi is doing much more than this simple branching steps, but is there an unavoidable necessity in the algorithms for equidistant integer values?0 -
Hi Thomas,
Are there any (dis)advantages known in comparision of Pow and Pwl?
If you are approximating a nonlinear function using a piecewise linear function then you are defining the approximation prior to the solve, and it remains static. I dare say allowing Gurobi to perform this approximation means it may be dynamic, i.e. the approximation may be iteratively refined where appropriate. I'd certainly suggest that using addGenConstrPow is the more attractive option.
Let's assume the continuous relexation finds 1.3 as the optimal value, then branching could be used to produce two subproblems/nodes with d1<=1.26 and d2>=1.44.
Yes this is certainly one way to do the branching and is the idea behind the original approach where a binary variable is used for each break in the sequence, and used to branch on - and done so in a lazy manner. A branch on the binary variable corresponds to a branch in the continuous variable domain.
If you have just the one variable in the model that has this set of non-integer values it can take, and the set is not too large, then another approach would be to build a multi-scenario model - a scenario for each of the discrete values - where the lb and ub of the variable vary from scenario to scenario and lock it into place.We have put the suggestion to the devs as a feature request!
- Riley
0
Please sign in to leave a comment.
Comments
5 comments