In integer programming what's the difference between using lower upper bound constraints and using a big M constraints?

Question

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.

Answer 1

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.