Dropping the requirement that the variables be whole numbers gives a different problem — a relaxation — whose optimum bounds the integer optimum rather than being it. The rounded point is a third object again: it can break a row outright, and when it does not it can be worth much less than the best whole-number plan, which may sit at the far end of the region.
Core ideas
One hard idea, and it is a distinction: the relaxation, the rounded point and the integer optimum are three different objects, and the arithmetic that relates them relates only two.
Delete the words “and whole” from the model and every plan that was allowed is still allowed, plus a great many that were not. A maximum taken over a larger set cannot be smaller, so z_LP ≥ z_IP always — and that inequality is the entire relationship. It says nothing about where the integer optimum is, only that it is not above z_LP.
A point fractional in two coordinates has four roundings: floor and ceiling in every combination, 2ⁿ of them for n fractional coordinates. “Round the answer” does not name one of them, and on this instance three of the four break a row. The one that does not is worth 10 against an optimum of 12.
A rounding can pass every row and still be a poor plan, and that is the case worth fearing, because nothing complains. Here the best feasible rounding is (2, 1) and the best whole-number plan is (0, 3) — not adjacent to the fractional corner, not reachable from it by rounding, and worth two more.
The material
Three objects, one of which is a bound on another, and neither of which is the third.
A relaxation of an optimisation problem is another problem with the same objective and a feasible set that contains the original one. Dropping the requirement that the variables be integers gives the linear programming relaxation: the same rows, the same objective, and x ≥ 0 in place of x ∈ {0, 1, 2, …}.
The word is worth taking literally. Nothing has been approximated and nothing has been solved approximately. A second, easier problem has been written down, and it has its own exact answer, which the simplex method of the earlier courses produces in exact fractions.
For a maximisation, z_LP ≥ z_IP. For a minimisation, z_LP ≤ z_IP. In both cases the relaxation errs on the optimistic side, and by an amount nothing in the relaxation reveals.
Every plan that satisfies the rows and is whole also satisfies the rows, so the integer feasible set is a subset of the relaxed one.
A maximum over a subset is at most the maximum over the whole set. Hence z_IP ≤ z_LP, and the minimisation case is the same argument with the inequality reversed.
□
That is all that is proved, and readers routinely hear more in it. It does not say the integer optimum is close to z_LP; it does not say the integer optimum is near the fractional point; and it says nothing whatever about rounding, which has not been mentioned.
The relaxation of max 3x₁ + 4x₂ subject to 2x₁ + x₂ ≤ 6 and 2x₁ + 3x₂ ≤ 9 stops at (9/4, 3/2), worth 51/4. Its roundings are (2, 1), (2, 2), (3, 1) and (3, 2). (2, 2) breaks the second row, which wants 10 where 9 is allowed; (3, 1) breaks the first, which wants 7; (3, 2) breaks the first, which wants 8. Only (2, 1) survives, and it is worth 10.
There are ten whole-number plans in this region, and the best of them is (0, 3), worth 12. It is not a rounding of (9/4, 3/2); it is at the other end of the region, with the first variable at zero rather than at two or three. No amount of care about which way to round finds it, because rounding only ever looks at the corners of one little box.
The 3/4 between 51/4 and 12 is the integrality gap of this instance. It is not an error bar and not a rounding error: it is the price of the requirement that the plan be whole, measured on this instance and no other. The second gap, the 2 between 12 and 10, is the price of having rounded instead of solved.
The integer optimum here was found by trying every whole-number point in the box — thirty candidates, ten of them feasible. That is honest at this size and hopeless at any interesting one, which is what the last four lessons of this course are for. What matters now is that a number produced by enumeration is an answer, and a number produced by rounding is a guess with no bound attached.
Algebra’s “Systems of Inequalities and Linear Programming” ends by saying that rounding an optimal corner is not guaranteed to give the best whole-number answer, and that this is a different subject. This is that subject, and this is its first page: everything after it exists because the sentence is true.
Interactive
The relaxation bounds the integer optimum; the rounded point is a different object
Method
Four steps, and the third is the one that stops a wrong answer leaving the building.
Exactly, as fractions. (9/4, 3/2) worth 51/4 is a fact about a different problem, and labelling it z_LP rather than “the answer” is half of this lesson.
Floor and ceiling in every combination of the fractional coordinates: four here, 2ⁿ in general. A coordinate that is already whole is not rounded at all and does not double the list.
A rounding is a candidate until it has passed all of them, and when it fails, name the row. “It breaks the finishing row, which wants 10 where 9 is allowed” is a diagnosis; “it looked wrong” is not.
At this size, by enumerating the lattice points of the region. The point of doing it once by hand is to see where the answer actually is before any method is trusted to find it.
z_LP, then z_IP, then whatever the rounding was worth. The order z_LP ≥ z_IP ≥ z_rounded is the shape of every result in this course, and a report missing the middle term is a report with no answer in it.
Two rows, two variables, and every figure exact. The instance is the lab's opening preset, so each line below can be checked against the panel.
The line worth staring at is the last block. The relaxation put the first variable at 9/4 and the integer optimum puts it at 0. Nothing about (9/4, 3/2) pointed at (0, 3), and nothing was going to.
The (0, 3) plan is also the one that uses the finishing row to the last unit — 2(0) + 3(3) = 9 exactly — while leaving three units of assembly idle. A whole-number plan often has that shape: one row tight, another slack, because the corner where both are tight is not a whole point.
For a faded rehearsal, use the lab's slider to move the assembly right-hand side down to 5 and repeat all four steps. The supplied first move is that z_LP can only fall, because the region only shrank: it becomes 25/2 at (3/2, 2). Notice that only one coordinate is fractional now, so there are two roundings rather than four. Say which of them is feasible and what it is worth, and whether z_IP moved at all, before the panel tells you.
You should be able to solve a two-variable relaxation exactly, list all of its roundings, name the row each infeasible one breaks, find the whole-number optimum by enumeration at this size, and state z_LP ≥ z_IP ≥ z_rounded while saying which of those two inequalities is a theorem and which is an observation about the instance in front of you.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.