Gurobi MILP convergerce
AnsweredI am solving a Mixed-Integer Linear Program (MILP) using Gurobi that includes the linearization of a product term, $\mathbf{u = x \cdot y}$, where $x$ and $y$ are binary decision variables. I found a significant difference in solver speed: Convergence is much faster when I explicitly declare the product variable $u$ as a binary variable ($\mathbf{u \in \{0, 1\}}$), compared to defining $u$ as a continuous variable with explicit bounds of $0 \le u \le 1$ (relying on the linearization constraints to enforce the product relationship). I am looking for the reason why the solver's performance is so sensitive to this variable type declaration.
-
-
Gurobi Staff
Hi Nick,
I'm a little skeptical, but maybe we're missing something. What version of Gurobi are you using, and are you setting any parameters?
Would you be able to provide a MPS model file (via google drive, dropbox, github etc.) and the name of the u variable. We'll take a look and verify your result and see what's going on.
- Riley
0 -
-
Hi Riley,
within this google drive folder you can find the m.mps, and the m_relaxed.mps. The m.mps is when the product is modelled as a binary variable, while the m_relaxed.mps is when the product is modelled as a continuous variable bounded within the [0,1] range. The name of the u variables are U, X_rec.
0 -
-
-
Thanks Nick, models downloaded, feel free to remove the link if you wish!
I'll report back when I know more.
- Riley
0 -
-
-
Hi Nick,
Just an update to say we haven't forgotten about this, will hopefully have time to look at this week.
- Riley
0 -
-
-
Hi Nick,
We finally got to the bottom of this.
Although the continuous variables are detected as implied integer we don't make the conversion in this instance. This decision is based on some model structure and properties and is intended to be the “right decision” but in this case it wasn't. We're using this example to see how we can improve (thanks!).
The main takeaway here is for the modellers among us - try ideas and experiment (as you have done) and see which works best. I don't think we have a more specific learning that can be communicated at this stage.
- Riley
0 -
-
Hi Riley,
Thank you very much for the clarification.
Is there a recommended way to declare these variables—given that they may be continuous—in order to minimize the solver’s execution time?
Best regards,
Nikos0 -
-
-
Hi Nick,
There isn't a way to tell Gurobi “these continuous variables will take binary values in an optimal solution”, or something similar, if that's what you are asking.
- Riley
0 -
Please sign in to leave a comment.
Comments
7 comments