Back to the on-screen lesson ·
Either-or, fixed charges and logical conditions as linear constraints, and why the size of big-M decides whether the model solves.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write common logical conditions — at most one, exactly one, at most k, if A then B, and use-only-if-opened — as linear constraints on binary variables, and check a formulation by enumerating the combinations. You will also be able to choose a big-M constant correctly, and explain why one too small silently forbids good answers while one too large leaves the model correct and the search hopeless.
From lesson 5: integrality is what breaks convexity, and binaries are the common case. From lesson 7: every or in a specification is a union, and unions are where convexity goes. This lesson is the constructive side of both — the small vocabulary of patterns that turns logical conditions into linear constraints.
A binary variable $y \in \{0,1\}$ is not a quantity. It is an answer to a yes-or-no question, and the value of the whole technique is that logical conditions about those answers can be written as linear inequalities — so a solver that understands only linear algebra can reason about either, if, and at most.
| In words | As a constraint |
|---|---|
| At most one of A, B | $y_A + y_B \le 1$ |
| Exactly one | $y_A + y_B = 1$ |
| At most $k$ of $n$ | $\sum_j y_j \le k$ |
| If A then B | $y_A \le y_B$ |
| A and B together or not at all | $y_A = y_B$ |
| Use route $j$ only if opened | $x_j \le M_j y_j$ |
| Fixed charge for using $j$ | add $f_j y_j$ to the objective |
The last two are the big-M pattern and are the workhorse. $x_j \le M_j y_j$ with $x_j \ge 0$ says: if $y_j = 0$ then $x_j = 0$; if $y_j = 1$ then $x_j$ may go up to $M_j$. That single line is what links a continuous decision to a yes-or-no one.
Choosing $M$ is a modelling decision, not a formality. $M_j$ must be at least the largest value $x_j$ can legitimately take, or the model forbids something you meant to allow. But every unit larger than necessary makes the relaxation weaker: with a huge $M$, the relaxation can set $y_j$ to a tiny fraction and still use the full capacity, paying almost none of the fixed cost. A weak relaxation is a weak bound, and a weak bound prunes nothing — so the model is correct and the search is hopeless. Tightening $M$ is the single highest-value thing a modeller does to an integer program.
Another way: picture
A switch and a tap. The binary is the switch; the continuous variable is how far the tap is open. The big-M constraint is the linkage: with the switch off the tap cannot open at all, and with it on the tap may open as far as the pipe allows — and $M$ is the width of the pipe, not an arbitrary large number.
Another way: steps
To write a logical condition as constraints:
Opening warehouse $j$ costs $f_j$; shipping $x_j$ from it costs $c_j$ per unit; a warehouse can ship at most $u_j$.
$$\min \sum_j (f_j y_j + c_j x_j) \quad\text{subject to}\quad x_j \le u_j y_j,\quad x_j \ge 0,\quad y_j \in \{0,1\}.$$
The fixed cost appears only when $y_j = 1$; and $x_j$ can only be positive when $y_j = 1$, because of the linking constraint. Two lines express a cost structure — a step at zero followed by a linear rate — that no purely continuous model can, because that cost function is not convex.
Notice that $M_j = u_j$: the capacity that was already in the model is the tightest valid big-M. That is the common case, and reaching for $10^6$ instead is how a correct model becomes an unsolvable one.
Treating a binary as a quantity. $y_1 \le y_2$ is an implication, not a comparison of sizes. Reading it as the latter leads to formulations that are quietly wrong.
A big-M that is too small. It silently forbids legitimate solutions, and the model returns a worse answer with no complaint.
A big-M that is far too large. It is correct and makes the problem unsolvable in practice. The two failures are opposite and only the first is visible.
Multiplying binaries. $y_A y_B$ is not linear. Replace it with a new binary $z$ and the three constraints $z \le y_A$, $z \le y_B$, $z \ge y_A + y_B - 1$, which force $z = y_A \wedge y_B$ exactly.
This is the idea that separates integer programming from everything before it. In units 2 and 3, a correct model was a correct model: the solver found the optimum and how you wrote it down barely mattered. Here it decides everything. Two formulations with identical integer solutions can have relaxations whose values differ enormously, and since the relaxation is the bound the search prunes with, one solves in seconds and the other never finishes. The practical consequence is that "the model is right but the solver is too slow" is usually a false diagnosis — the model is right and weak, and tightening it is modelling work, not tuning.
Either $x \le 10$ or $x \ge 40$ — a hole in the middle, so the feasible set is a union and not convex.
The or, from lesson 7.
Introduce $y \in \{0,1\}$ and write $x \le 10 + M y$ and $x \ge 40 - M(1-y)$.
One binary picks which branch holds.
With $y = 0$: $x \le 10$, and the second reads $x \ge 40 - M$, which is no restriction if $M \ge 40$. With $y = 1$: $x \ge 40$, and the first is no restriction if $M$ covers the upper bound on $x$. So one binary and two big-M constraints express a disjunction — and the smallest $M$ that works is read off the bounds on $x$.
The union, made linear.
Claim: $y_A + y_B \le 1$ says at most one. Combinations: $(0,0) \to 0$, allowed. $(0,1) \to 1$, allowed. $(1,0) \to 1$, allowed.
Three of four.
$(1,1) \to 2 > 1$: forbidden. Exactly the one combination that should be.
The fourth is the one ruled out.
Now check the near-miss: does $y_A + y_B \le 1$ also say if A then not B? Yes — it is the same statement. But it does not say if A then B, which is $y_A \le y_B$ and forbids $(1,0)$ instead. Two inequalities one character apart, forbidding different combinations; enumerating is the only reliable way to tell them apart.
Enumeration is the check that works.
One binary per depot: $y_1, y_2, y_3, y_4 \in \{0,1\}$, with $1$ meaning open.
Name the binaries and say what 1 means.
A count of open depots is the sum of the binaries. "At least two" is a lower bound on that count: $y_1 + y_2 + y_3 + y_4 \ge 2$.
Check the edges: all shut sums to $0$, correctly refused; exactly two sums to $2$, allowed; all four sums to $4 \ge 2$, allowed. And note what would go wrong with $\ge 2$ written as two separate constraints or as an or — the sum form is linear and the alternatives are not, which is why cardinality rules are the easiest thing in this whole vocabulary.
Two depots have binaries $y_1, y_2 \in \{0,1\}$. What does $y_1 \le y_2$ say?
| Allowed: neither depot is open | Allowed: only depot 2 is open | Forbidden: depot 1 open while depot 2 is shut | Allowed: both depots are open | |
|---|---|---|---|---|
| $(y_1,y_2)=(0,0)$ | ||||
| $(y_1,y_2)=(0,1)$ | ||||
| $(y_1,y_2)=(1,0)$ | ||||
| $(y_1,y_2)=(1,1)$ |
A route may carry $x \ge 0$ units only if it is opened ($y = 1$), and capacity limits it to $168$. What is the smallest valid $M$ in $x \le M y$?
Answer:
There are $7$ depots and at most $1$ may be open. How many must be shut?
Answer:
For $y_1 + y_2 \le 1$, fill in the left-hand side for each combination, and write $1$ if it is allowed and $0$ if not.
| $y_1 + y_2$ | allowed? | |
|---|---|---|
| $y_1=0, y_2=0$ | ||
| $y_1=0, y_2=1$ | ||
| $y_1=1, y_2=0$ | ||
| $y_1=1, y_2=1$ |
Two depots have binaries $y_1, y_2 \in \{0,1\}$. What does $y_1 \le y_2$ say?
| Allowed: neither depot is open | Allowed: only depot 2 is open | Forbidden: depot 1 open while depot 2 is shut | Allowed: both depots are open | |
|---|---|---|---|---|
| $(y_1,y_2)=(0,0)$ | ||||
| $(y_1,y_2)=(0,1)$ | ||||
| $(y_1,y_2)=(1,0)$ | ||||
| $(y_1,y_2)=(1,1)$ |
A modeller writes $M = 10^6$ where $84$ would do. The model is still correct. What is the cost?
| Strongest valid formulation | Permits capacity while paying almost no fixed cost | Can exploit $x \le M y$ with tiny $y$ | Prunes little, producing a much larger branch-and-bound tree | |
|---|---|---|---|---|
| Smallest justified $M$ | ||||
| Arbitrarily huge $M$ | ||||
| Fractional binary in the relaxation | ||||
| Weak relaxation bound |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A route may carry $x \ge 0$ units only if it is opened ($y = 1$), and capacity limits it to $142$. What is the smallest valid $M$ in $x \le M y$?
Answer:
You can express logical conditions as linear constraints, write a fixed-charge model, and choose a tight big-M. Next: what the relaxation of such a model is good for.
9. Your turn: write "at least two of the four depots must be open", step 3