Back to the on-screen lesson ·
Why rounding a continuous answer is not an answer, what binaries buy, and why integrality is what makes a model hard.
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 say which variables in a model must be integers and why, explain with an example why rounding a continuous solution can be both infeasible and far from optimal, use the linear relaxation as an upper bound on a maximisation, and say what integrality costs in structural terms — the feasible set stops being convex, so the corner argument that made the continuous problem easy no longer applies.
You can write a model and find a two-variable optimum at a corner. That corner argument has been doing quiet work: it rests on the feasible region containing the whole segment between any two of its points. This lesson is the first place that fails, and it fails for a reason that has nothing to do with size.
Integer variable: one restricted to whole numbers, $x \in \mathbb{Z}_{\ge 0}$.
Binary variable: one restricted to $\{0, 1\}$ — a yes-or-no decision written as arithmetic.
Integer program: a model with at least one integer variable. Mixed when others stay continuous.
Relaxation: the same model with the integrality dropped. Its feasible set contains the integer one.
Upper bound: for a maximisation, a number no answer can beat. The relaxation supplies one.
Lattice point: a point whose coordinates are all whole numbers.
Gap: the distance between a bound and a solution in hand — what is still unknown about the answer.
Some quantities are not divisible. You cannot dispatch $2.4$ lorries, open half a warehouse, or hire a third of a nurse. The model has to say so:
$$x_j \in \mathbb{Z}_{\ge 0} \quad\text{or}\quad x_j \in \{0, 1\}.$$
That single line changes the problem class completely.
Rounding is not a method. Given the continuous answer $x = 2.4$, neither $2$ nor $3$ is reliable:
Why it is genuinely harder. The continuous feasible region is convex: the segment between any two feasible points is feasible, which is what makes the optimum sit at a corner. The integer points do not have that property — the midpoint of two lattice points need not be one — so the region is a scatter of dots, not a shape, and there is no line to sweep.
The relaxation. Drop the integrality and solve what is left. Every integer solution is still feasible for the relaxation, so for a maximisation its value is an upper bound on the integer optimum. That bound is the single most useful object in unit 4: it is what lets a search discard whole regions without looking inside them.
Another way: picture
The same shaded polygon as before, with a grid of dots drawn on it. The continuous problem may stop anywhere in the shading; the integer problem may only stop on a dot inside it. The best dot is often not the dot nearest the best shaded point, and the picture is the fastest way to see why.
Another way: steps
Faced with a model that needs whole numbers:
A field holds cranes and turtles: 10 heads and 32 legs. How many of each?
With $c$ cranes and $t$ turtles: $c + t = 10$ and $2c + 4t = 32$. Subtracting twice the first from the second gives $2t = 12$, so $t = 6$ and $c = 4$.
The answer came out whole, and nothing in the working made it do so. Change the legs to 33 and the same steps give $t = 6.5$ — arithmetically correct and meaningless. The lesson is that the integrality was a fact about the world that the equations never knew, and a model that does not state it is a model that will sometimes hand back half a turtle with complete confidence.
Most integer modelling in practice uses $x \in \{0,1\}$, where the variable is a yes-or-no rather than a count: open this depot, use this route, assign this nurse to this shift. Binaries are what let a model express things linear algebra cannot:
| In words | With a binary |
|---|---|
| Use route $j$ at all | $x_j \le M y_j$, $y_j \in \{0,1\}$ |
| At most three depots open | $\sum_j y_j \le 3$ |
| If A is chosen then B must be | $y_A \le y_B$ |
| Exactly one of these | $\sum_j y_j = 1$ |
Lesson 21 comes back to these properly. What matters now is that the expressive power and the difficulty arrive together: the same line that lets you say "if A then B" is the line that breaks convexity.
Rounding and reporting. The most common and the most expensive. A rounded answer has no claim to optimality and may not even be feasible.
Making everything an integer. Integrality is costly; impose it only where the quantity really is indivisible. Tonnes of steel are not.
Reading the relaxation's value as the answer. It is a bound. For a maximisation the true answer is at most that, and saying how much less is the job of unit 4.
Assuming the integer answer is near the continuous one. Sometimes it is. There is no theorem saying so, and problems where it is badly false are easy to build.
It is tempting to think of an integer program as a continuous one with a tidy-up afterwards, because that is what a person does by hand. It is not: the integer problem is a different problem with a different feasible set, and its answer is not a function of the continuous answer. The clearest way to hold this is the picture — the continuous problem optimises over a shaded shape and the integer problem over a scatter of dots. The best dot is chosen by looking at dots. Everything in unit 4 is machinery for doing that without looking at all of them, and the relaxation's only role is to say which regions of dots are not worth looking at.
Items worth $6, 10, 12, 7$ weighing $1, 2, 3, 2$, and a bag holding $5$. Each item is in or out: sixteen bags.
Binary decisions, small enough to list.
Discard the overweight ones. Among those left, $\{1,2,3\}$ weighs $6$ — too heavy. $\{2,3\}$ weighs $5$ and is worth $22$; $\{1,2,4\}$ weighs $5$ and is worth $23$.
Check weight before value.
The best that fits is $23$. Sixteen bags was easy; forty items would be over a million million, which is why unit 4 exists and why the bound from the relaxation matters so much.
Enumeration works and does not scale.
$\max\ x + y$ subject to $2x + 2y \le 3$, $x, y \ge 0$ integer. The relaxation's optimum is anywhere on $x + y = 1.5$, value $1.5$.
The continuous answer.
Round $(0.75, 0.75)$ to $(1, 1)$: the constraint reads $4 \le 3$, false. The rounded point is infeasible.
Rounding up broke it.
The integer optimum is $1$, at $(1,0)$ or $(0,1)$ — a third below the bound. The bound was not wrong; it was a bound, and the gap between it and the truth is the thing a search has to close.
The gap is real and is the subject of unit 4.
A bakery decides how many kilograms of each of three flours to buy, and which of four suppliers to open an account with. Kilograms of flour: divisible, so continuous.
Ask what half a unit would mean.
Opening an account: yes or no, so a binary per supplier. Four binaries.
So this is a mixed-integer model: three continuous variables and four binaries, and it is the four binaries that make it hard. Note also the link that will need writing — you may not buy from a supplier you have no account with, which is the $x \le M y$ pattern from the table above and lesson 21's main subject.
Match each decision to the kind of variable its model needs.
| Non-negative integer | Binary (0 or 1) | Continuous quantity | |
|---|---|---|---|
| Number of lorries to buy | |||
| Whether to open a depot | |||
| Litres of fuel to purchase |
A field holds cranes (two legs each) and turtles (four legs each): $15$ heads and $44$ legs in all. Complete the count.
| heads | legs | |
|---|---|---|
| Cranes | ||
| Turtles | ||
| Total | 15 | 44 |
A continuous model recommends buying $6.4$ lorries. Is rounding to $6$ a sound way to get an integer answer?
Four items are worth $9, 5, 8, 4$ and weigh $3, 2, 4, 1$. The bag holds $6$. What is the best total value that fits?
Answer:
Allowing fractions of items, the best value is $22$. A search has already found a whole-item bag worth $22$ but has not finished. Which values $v$ can the best whole-item value still turn out to be?
This task has no paper form; do it on a device.
Why is an integer program harder than the same model without the integrality requirement?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A continuous model recommends buying $8.4$ lorries. Is rounding to $8$ a sound way to get an integer answer?
You can decide which variables need to be whole numbers, explain why rounding is not a method, and use a relaxation as a bound. Next: reading a model somebody else wrote, and saying what it assumes.
11. Your turn: which variables here need to be integers?, step 3