Adding Range constraints versus linear constraints
Answered
Hello,
I'm dealing with a very large MIP and was wondering if there is any computational benefit to using range constraints versus adding constraints separately in the standard method?
Thank you,
Taylor
-
I would hope that the preprocessor is able to detect two corresponding constraints and make a ranged constraint out of them.
From a linear point of view, if I knew there is a ranged constraint, I would also store it as a ranged constraint, because if it is not detected (e.g. due to a disabled preprocessor), then it would increase the size of the basis, the matrix, the LU decomposition, etc. . Despite of this, there are some minor disadvantages using ranged constraints. E.g. if you deal with dual varialbes or farkas certificates, the handling becomes a little more annoying (but not impossible).
From a mixed-integer point of view, I would hope that there are no disadvantages using ranged constraints.
0 -
It should not matter as long as presolve is enabled. From a practical point of view, range constraints in Gurobi are a bit painful because adding a range constraint will actually add an equation and a new variable (the explicit slack variable of the range constraint). In other words, if you add a range constraint
l <= ax <= r
then you are actually addingax + s = r
with a new variable s with 0 <= s <= r-l. This can be a bit confusing if you add a constraint and suddenly the number of variables in your problem increases.
For this reason, I would just add the explicit slack variable yourself.
Regards,
Tobias
1 -
Thank you for the responses, this helps a ton!
0 -
When providing LP warm start (C/VBASIS or P/DSTART) after GRBaddrangeconstr(), I receive ''Warning, invalid warm-start basis discarded" (printer 2x for some reason). Will this be fixed or the advice is still the same to implement range constraints manually?
0 -
Gurobi has only a very rudimentary support for range constraints. Namely, what we do is to directly add an explicit slack variable for the range constraint. Hence, GRBaddrangeconstr() is nothing else than calling GRBaddvar() with a continuous variable that ranges from 0 to the range value of the constraint, plus calling GRBaddconstr() with the constraint as equality constraint and the new slack variable added to the constraint.
Consequently, your model and then also your basis will have one more variable that you would expect.
Hence, the recommendation is to only use range constraints if you have a simple data-in-solution-out work flow. If you do anything more fancy (like warm start bases, inspecting or modifying the model afterwards, and so forth), then you should just add the explicit slack variable yourself. Or, alternatively, add two inequality constraints instead and rely on the presolver to merge these parallel constraints into a single range constraint (again, by introducing an explicit slack).
Regards,
Tobias
1 -
A similar question for quadratic range constraints: is the extra slack variable the best way of modelling as well?
0 -
It is the only way, because Gurobi does not support quadratic range constraints. But note that as soon as you have a quadratic range constraint (which you would turn into an equation by adding a slack), you are immediately in the domain of non-convex MIQCP. Thus, you need to use the "NonConvex=2" parameter setting (at least in current versions). And you need to use at least Gurobi 9.0. Better 9.1 as this is much faster on average on non-convex MIQCP.
1 -
Well I guess an alternative way is to have 2 opposite constraints (<=, >=). For the C API, this is the only 'official' way because GRBaddqconstr only documents GRB_LESS_EQUAL or GRB_GREATER_EQUAL, although GRB_EQUAL works fine in practice.
0 -
Thanks for pointing out this bug in our documentation. This is still from Gurobi versions prior to 9.0, where an equality Q constraint would automatically lead to a "non-PSD" error (quadratic equations are always non-convex). But since with Gurobi 9.0 we support solving non-convex MIQCPs, it is now of course valid to also add quadratic equations.
Previously, it was also already possible to add quadratic equations, but unless they get removed by presolve or can be linearized, this would have triggered a "non-PSD" error.
0
Please sign in to leave a comment.
Comments
9 comments