Back to the on-screen lesson ·
Dropping the whole-number requirement gives a bound; rounding the answer it returns gives nothing.
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 form the LP relaxation of an integer program and use its optimum as a bound, bracket the integer optimum between a known plan and that bound, say why rounding a relaxed solution is neither safe nor optimal, and round a fractional bound when the objective takes only whole values.
You can solve a linear program and read its answer. Everything in this unit starts from a linear program you can already solve — and from the fact that its answer is not the one you want.
The LP relaxation of an integer program is the same program with the whole-number requirement dropped. Its optimum is a bound on the integer optimum — an upper bound for a maximisation. The integrality gap is the distance between the relaxation's value and the best integer plan known.
Requiring $x$ to be whole numbers replaces the feasible polygon by the lattice points inside it. Nothing about the constraints has changed; what has gone is the geometry the whole course has relied on. The feasible set is no longer convex, an optimum need not sit at a corner of anything, and the simplex method has nothing to walk along.
The relaxation. Drop the requirement and you have an ordinary linear program again. Every integer-feasible point is feasible for it, so its optimum is a ceiling over the integer optimum. That ceiling is the single most useful thing in the subject.
Rounding is not the answer. Rounding up can leave the region altogether; rounding down stays feasible when the coefficients are positive but need not be optimal, and in two or more variables there may be no feasible rounding of the relaxed point at all. The integer optimum can sit far from the relaxed one.
Rounding the bound is different. When the objective can take only whole values, a bound of seven and a half may be lowered to seven, because the objective cannot reach anything between. That is a statement about the numbers, not a guess at a plan.
Another way: steps
Another way: picture
The same polygon twice. In the first it is shaded solid and the optimum sits on a corner. In the second only the lattice points inside it are marked, the corner is bare, and the best marked point is somewhere along an edge — or not near the corner at all.
The relaxed answer is rounded and reported. Even where the rounding happens to be feasible, nothing has been proved about it, and the habit is hard to unlearn because in one variable it always works. The second error is the mirror image: refusing to round the bound when the objective is integer-valued, which throws away a free proof.
Maximise $x + y$ subject to $4x + 4y \le 9$ over non-negative whole numbers. The relaxation gives $x + y = 9/4 = 2.25$.
A fractional bound.
Rounding up to a total of $3$ needs $4 \times 3 = 12 > 9$: infeasible in every direction at once.
No rounding up works.
The objective is whole, so the bound $2.25$ becomes $2$, and the plan $(2, 0)$ attains it. The bound proved it, and no rounding of the plan did.
Round the bound, not the plan.
The objective takes only whole values, so the bound $37.6$ may be lowered to $37$.
Round the bound down.
The known plan attains $37$, so it is optimal and the search is over.
A maximisation over whole numbers has an LP relaxation whose optimum is $54$, and a known integer plan worth $50$. Fill in what is known.
| Value | |
|---|---|
| The integer optimum is at most | |
| The integer optimum is at least | |
| The gap still open |
The relaxation's optimum is $37$ and a known integer plan is worth $29$. Give the interval the integer optimum must lie in.
This task has no paper form; do it on a device.
Maximise $x$ subject to $2x \le 17$, with $x \ge 0$. Complete both answers.
The relaxation gives the value r, and the best whole-number value is i.
A relaxation returns a plan with $x = 7$ and a half, in a model with several variables and constraints. Is rounding it a safe way to get an integer answer?
The constraint is $2x \le 7$ and the relaxation gives $x = 7/2$. Work out $2x$ for each rounding.
| The value of $2x$ | |
|---|---|
| Rounded up to $4$ | |
| Rounded down to $3$ |
Maximise $x$ subject to $2x \le 25$, with $x$ a non-negative whole number. What is the optimum?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A maximisation over whole numbers has an LP relaxation whose optimum is $38$, and a known integer plan worth $34$. Fill in what is known.
| Value | |
|---|---|
| The integer optimum is at most | |
| The integer optimum is at least | |
| The gap still open |
You can use a relaxation as a bound on an integer optimum and say why its solution may not be rounded. Say in your own words why the relaxation's optimum is always at least the integer optimum.
7. Your turn: a relaxation gives $37.6$ for an integer-valued objective, and a known plan is worth $37$. What can you conclude?, step 2