Try our new documentation site (beta).
Filter Content By
Version
Text Search
${sidebar_list_label} - Back
Filter by Language
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 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*}](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img216.png?x70725)
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>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img217.png?x70725)
![<span>$</span>10^{-5}<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img183.png?x70725)
![<span>$</span>x<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img9.png?x70725)
![<span>$</span>9.999<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img218.png?x70725)
![<span>$</span>x<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img9.png?x70725)
![<span>$</span>y<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img26.png?x70725)
![<span>$</span>x<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img9.png?x70725)
![<span>$</span>y<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img26.png?x70725)
However, if the modeler has additional information that the
variable will never be larger than
, then you could reformulate
the earlier constraint as:
![\begin{eqnarray*}
x&\leq&10^3y\
x &\geq& 0\
y &\in & \{0,1\}
\end{eqnarray*}](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img219.png?x70725)
And now,
![<span>$</span>y = 0.0000099999<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img217.png?x70725)
![<span>$</span>x \leq 0.01<span>$</span>](https://www.gurobi.com/wp-content/plugins/hd_documentations/documentation/8.1/refman/img220.png?x70725)
For cases when it is not possible to either rescale variable
or tighten its bounds, an SOS constraints or an indicator constraint
(of the form
) may produce more accurate
solutions, but often at the expense of additional processing time.
![](/wp-content/plugins/hd_documentations/content/images/documentation-ampl-guide.webp?x70725)
![](/wp-content/plugins/hd_documentations/content/images/documentation-cloud.webp?x70725)
![](/wp-content/plugins/hd_documentations/content/images/documentation-example-tour.webp?x70725)
![](/wp-content/plugins/hd_documentations/content/images/documentation-quick-start.webp?x70725)
![](/wp-content/plugins/hd_documentations/content/images/documentation-reference-manuals.webp?x70725)
![](/wp-content/plugins/hd_documentations/content/images/documentation-remote-services.webp?x70725)
![](/wp-content/plugins/hd_documentations/content/images/quickstart-os-linux.webp?x70725)
![](/wp-content/plugins/hd_documentations/content/images/quickstart-os-mac-osx.webp?x70725)
![](/wp-content/plugins/hd_documentations/content/images/quickstart-os-windows.webp?x70725)