Back to the on-screen lesson ·
What the LP relaxation proves, the integrality gap as a property of the formulation, and how to read a solver's gap report.
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 direction an LP relaxation bounds in for a maximisation and for a minimisation, compute an integrality gap and express it as a percentage, and read a solver's incumbent-and-bound report as a bracket around an unknown optimum. You will also be able to explain why two correct formulations of the same problem can have very different bounds, and why the gap is a diagnostic about the model rather than about the solver.
From lesson 5: the relaxation is an upper bound on a maximisation, and rounding is not a method. From lesson 13: a bound on an unknown optimum is a certificate. This lesson makes those two into the working tool of unit 4 — the number that lets a search discard regions it has never looked inside.
The linear relaxation of an integer program is the same model with $x_j \in \mathbb{Z}$ replaced by $x_j \in \mathbb{R}$. Its feasible set contains every integer solution and more, so optimising over it cannot do worse:
| Objective | Relaxation gives |
|---|---|
| maximisation | an upper bound |
| minimisation | a lower bound |
The direction flips with the objective and getting it backwards is this unit's commonest slip.
The integrality gap is the difference between the relaxation's value and the integer optimum. It measures how much the relaxation is lying by, and it is a property of the formulation: two models with identical integer solutions can have very different gaps, and the one with the smaller gap is the one that solves.
Why a bound is worth so much. A search that has found an integer solution worth $B$ knows the optimum is at least $B$. A relaxation of some subproblem valued at $R \le B$ says nothing in that subproblem beats $B$ — so the entire subproblem can be discarded without examining a single point in it. The search terminates not by running out of possibilities but by running out of possibilities worth examining.
Reading a solver's gap. A run in progress reports two numbers: the incumbent (best integer solution so far) and the bound (best relaxation value over the unexplored tree). The gap between them, usually as a percentage, is what remains unproved. A run stopped at a $1\%$ gap has produced a solution provably within $1\%$ of optimal, which for almost any real decision is a finished answer.
Another way: picture
A thermometer with the unknown optimum somewhere inside. The incumbent pushes one end up as better solutions are found; the bound pushes the other end down as subproblems are ruled out. The search finishes when the two ends meet — or when what is left between them stops mattering.
Another way: steps
To use a relaxation:
Two models of the same fixed-charge problem, with the same integer solutions:
Weak. $\sum_j x_j \le M \sum_j y_j$ with $M$ the total capacity — one aggregated linking constraint.
Strong. $x_j \le u_j y_j$ for each $j$ — one linking constraint per facility.
The integer solutions are identical. But in the relaxation the weak version lets a single tiny fractional $y$ unlock capacity everywhere, so its bound is far above the truth; the strong version ties each facility's usage to its own $y$ and its bound is much closer.
Same answers, different bounds, and the difference between a model that solves in a minute and one that does not finish. This is why "disaggregate the constraints" is standard advice, and why the first thing to do with a slow integer model is to look at its relaxation rather than at the solver's settings.
The direction. Upper bound for maximisation, lower for minimisation. Write down which you are doing before reading the number.
Reading the bound as the answer. It is what the optimum cannot exceed. Reporting it as the optimum overstates by exactly the gap.
Ignoring the incumbent. Without a feasible integer solution there is nothing to prune against, and the search has to go deep before it can discard anything. A quick heuristic solution early is worth a great deal for this reason alone.
Chasing the last percent. Most of a run's time usually goes on the final fraction of the gap. Whether that matters is a question about the decision, not about the solver, and it is worth asking before the run rather than after.
A slow integer run invites the thought that the solver is inadequate, and the number that would settle it is sitting right there. If the relaxation's value is close to the integer optimum, the formulation is strong and the search will prune well; if it is far above, no solver can prune, because there is nothing to prune with. The remedy in that case is modelling work — tighter big-M constants, disaggregated linking constraints, added valid inequalities — and not a faster machine or a different solver. The first diagnostic on any slow integer model is therefore: solve the relaxation, compare it to the best known integer solution, and look at the gap.
An assignment problem: match $n$ workers to $n$ jobs at least cost, with binary $x_{ij}$.
An integer program on the face of it.
Solve the relaxation with $0 \le x_{ij} \le 1$. The answer comes back with every $x_{ij}$ equal to $0$ or $1$ — integral without being asked.
The relaxation's answer is already integral.
So it is the integer optimum, with a zero integrality gap. This is not luck: the assignment polytope has integer vertices, a property called total unimodularity, and lesson 25 is about which problems have it. Where they do, the integer program is a linear program wearing a disguise.
Some integer problems are secretly easy.
After ten seconds: incumbent $118$, bound $140$. Gap $22$, about $19\%$. The optimum is somewhere in $[118, 140]$.
Early: a wide bracket.
After two minutes: incumbent $131$, bound $134$. Gap $3$, about $2.3\%$. Both ends have moved — a better solution was found and subproblems were pruned.
Both ends move.
After an hour: incumbent $131$, bound $131.4$, gap $0.3\%$. The incumbent has not improved in fifty-eight minutes and is probably optimal; what the run is doing is proving it. Whether that hour is worth spending is a question about the decision, and stopping now yields a plan provably within $0.3\%$.
Finding and proving are different jobs.
Minimisation, so the relaxation is a lower bound: the optimum is at least $84$.
Direction first.
The incumbent is feasible, so the optimum is at most $91$. The optimum lies in $[84, 91]$, a gap of $7$, about $8\%$ of the incumbent.
So the plan in hand costs at most $8\%$ more than the best possible. Whether to keep searching depends on what $8\%$ is worth here — and notice that this judgement can be made now, before the search finishes, which is the practical value of the whole apparatus.
A maximisation has relaxation value $30$ and integer optimum $27$. What is the integrality gap?
Answer:
For a *minimisation* integer program, is the LP relaxation's value above or below the integer optimum?
| Has a feasible set containing the integer set | Relaxation supplies a lower bound | Relaxation supplies an upper bound | Is also feasible for the relaxation | |
|---|---|---|---|---|
| LP relaxation | ||||
| Minimisation objective | ||||
| Maximisation objective | ||||
| Every integer-feasible point |
A search has an incumbent worth $68$ and a bound of $74$. What is the gap as a percentage of the incumbent?
Answer:
A knapsack's fractional optimum is $21$ and every value is a whole number. What is the largest integer value that is still possible?
Answer:
A maximisation has relaxation value $30$ and integer optimum $27$. What is the integrality gap?
Answer:
A search has an integer solution worth $20$ and the relaxation bound has fallen to $20$. What follows?
| Shows the optimum is at least $20$ | Shows the optimum is at most $20$ | Zero | Optimality is proved; stop searching | |
|---|---|---|---|---|
| Feasible integer solution worth $20$ | ||||
| Relaxation bound of $20$ | ||||
| Difference between incumbent and bound | ||||
| Search status |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A search has an incumbent worth $55$ and a bound of $56$. What is the gap as a percentage of the incumbent?
Answer:
You can compute and read a gap, say which way a bound goes, and use it to judge a formulation. Next: the search that the bound makes possible.
9. Your turn: a minimisation has bound $84$ and incumbent $91$. What can be said?, step 3