3
$\begingroup$

I've noticed that for integer programming models with binary variables some use upper bound constraints and others use big M constraints in order to have two mutually exclusive choices.

I have trouble understanding the difference and when to use one instead of the other?

Example of a lower upper bound constraint assuming $y$ to be a binary variable : $x \leq 3y$

From this constraint I understand that x can be at most $= 3$ if $y = 1$ otherwise $x \leq 0$. However usually we have non-negativity constraints so $x = 0$ in this case.

Example of a big M constraint assuming $y$ to be a binary variable : $x_1 + x_2 + x_3 \leq 15 + M(1-y)$.

I understand that the expression at the left of the inequation can either be $\leq 15$ when $y = 1$ or $\leq \infty$. The latter suggest that we can have any values we want for left side.

$\endgroup$
2
  • 3
    $\begingroup$ I think you are missing a +-sign between 15 an $M$? Also, I would consider them both to be big-$M$ constraints. In the first inequality you have $M=3$ and in the latter $M$ hasn't been specified. $\endgroup$
    – Sune
    Dec 20 '20 at 17:47
  • $\begingroup$ Ok so they're both considered big M constraints? The sign between 15 and M is indeed a + sign. $\endgroup$
    – WindBreeze
    Dec 20 '20 at 18:41
6
$\begingroup$

As Sune said in a comment, they really are both "big-M" constraints, differing (perhaps) in how "big" $M$ is. If you choose $M$ sufficiently large, then yes, your second constraint will not meaningfully limit the values of the $x$ variables ... which likely is by design. Other constraints in the model will probably restrict the values of those variables. For instance, your constraint might mean that shipments to three customers (left side) are limited to 15 units if being sent by air freight ($y=1$). If being sent via ground transportation ($y=0$), this constraint does limit shipments to those customers ... but something else (supply, demand) will.

Also, the $\le \infty$ part is not entirely correct. There is a misconception, fostered in part by textbook authors who do not want to spend time or energy explaining how to choose values of $M$, that in a "big-M" constraint $M$ is a stand-in for infinity. In practice, it should be as small as possible subject to the requirement that when $y=0$ the constraint becomes nonbinding. So, continuing my example, I would choose $M$ to be the smaller of supply for whatever is in the constraint or combined demand of the three customers. That implies that the left side when $y=0$ would not be unconstrained; it just would not be constrained enough to rule out valid choices. Choosing a stupid-large value for $M$ can result in numerical stability problems leading to incorrect answers from solvers.

$\endgroup$
1
  • 1
    $\begingroup$ Including the dreaded "trickle flow".which causes the intended logic of the Big M constraints to not function as intended. $\endgroup$ Dec 21 '20 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.