Dealing with big-M constraints

Big-M constraints are a regular source of instability for optimization problems. They are so named because they typically involve a large coefficient <span>$</span>M<span>$</span> that is chosen to be larger than any reasonable value that a continuous variable or expression may take. Here's a simple example:

\begin{eqnarray*}
x&\leq&10^6y\
x&\geq&0\
y&\in& \{0,1\},
\end{eqnarray*}


Big-M constraints are typically used to propagate the implications of a binary, on-off decision to a continuous variable. For example, a big-M might be used to enforce the condition that an edge can only admit flow if you pay the fixed charge associated with opening the edge, or a facility can only produce products if you build it. In our example, note that the <span>$</span>y = 0.0000099999<span>$</span> satisfies the default integrality tolerance (IntFeasTol=<span>$</span>10^{-5}<span>$</span>), which allows <span>$</span>x<span>$</span> to take a value of <span>$</span>9.999<span>$</span>. In other words, <span>$</span>x<span>$</span> can take a positive value without incurring an expensive fixed charge on <span>$</span>y<span>$</span>, which subverts the intent of only allowing a non-zero value for <span>$</span>x<span>$</span> when the binary variable <span>$</span>y<span>$</span> has the value of 1. You can reduce the effect of this behavior by adjusting the IntFeasTol parameter, but you can't avoid it entirely.

However, if the modeler has additional information that the <span>$</span>x<span>$</span> variable will never be larger than <span>$</span>10^3<span>$</span>, then you could reformulate the earlier constraint as:

\begin{eqnarray*}
x&\leq&10^3y\
x &\geq& 0\
y &\in & \{0,1\}
\end{eqnarray*}


And now, <span>$</span>y = 0.0000099999<span>$</span> would only allow for <span>$</span>x \leq 0.01<span>$</span>.

For cases when it is not possible to either rescale variable <span>$</span>x<span>$</span> or tighten its bounds, an SOS constraints or an indicator constraint (of the form <span>$</span>y = 0 \Rightarrow x = 0<span>$</span>) may produce more accurate solutions, but often at the expense of additional processing time.

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License
Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Academic License
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Search