The Linear Relaxation and Its Bound

A fractional optimum can be an excellent bound and a useless plan. Both facts matter, and confusing them is the most expensive error in integer programming.

This is the central idea of integer programming and also the site of its most common error. The relaxation is easy to solve and its answer is sitting right there, so the temptation to round it and move on is strong. That instinct is wrong often enough, and quietly enough, to be worth dismantling carefully.

The bound itself is informative. It states how much better any plan could possibly be, which is frequently enough to stop searching, and it refutes claimed solutions that are too good to be true.

This unit assumes you know what integrality does to a program and can classify the terminal outcomes of a linear program.

The bound is only useful if you know what to do with it. Three reported outcomes, and what each licenses.

Case 1: relaxation $100$, integer solution found at $104$.

The gap is $4$, or $4\mathrm{\%}$. Every integer-feasible point costs at least $100$, so no plan beats $104$ by more than $4$. Whether to keep searching is now a business question rather than a mathematical one: if $4$ units is immaterial, stop.

Case 2: relaxation $100$, integer solution found at $100$.

The gap is zero, so $100$ is optimal and the search is over. This happens whenever the relaxation's optimum is already integral, and for some problem classes it happens always: a transportation problem with integer supplies and demands has an integral optimal vertex, so its relaxation solves the integer problem outright.

Case 3: relaxation $100$, someone reports an integer solution at $97$.

The report is wrong. Every integer-feasible point is relaxation-feasible, so no integer solution can beat the relaxation's optimum for a minimisation. Either the claimed point violates a constraint, or the objective was computed differently, or the relaxation was solved incorrectly. You know this without examining how the number was produced, which is what makes the bound a genuine check.

---

Now the error the bound invites. Relaxation optimum $x=(2.6,1.4)$, capacity constraint $x_1\le 2$.

Rounding $x_1$ to $3$ violates the capacity outright: infeasible, not merely suboptimal.

Rounding $x_1$ down to $2$ stays feasible, but there is no reason the best integer plan has $x_2=1$. The constraints binding at $(2.6,1.4)$ need not bind at the integer optimum, so the whole shape of the solution can differ. Rounding produces a candidate to evaluate, never an answer to adopt.

What to take from a relaxation, stated as a rule. A number to compare against, and a place to start branching. Not a plan.

The linear relaxation of an integer program is the same program with every integrality restriction dropped. A binary restriction $x_j\in \{0,1\}$ relaxes to $0\le x_j\le 1$; the bounds survive, the integrality does not.

Write $z_{\text{IP}}^{\ast }$ for the integer optimum and $z_{\text{LP}}^{\ast }$ for the relaxation's.

The bound. Let $F$ be the relaxation's feasible set and $F\cap {\mathbb{Z}}^I$ the integer program's. The second is contained in the first, so optimising over the first can only do at least as well. For a minimisation

and for a maximisation the inequality reverses. Either way the relaxation is optimistic: it promises at least what the integer program can deliver.

The integrality gap. $|z_{\text{IP}}^{\ast }-z_{\text{LP}}^{\ast }|$. Small means the bound is informative; large means it says little, and how the model was written, loose linking bounds especially, affects which you get.

Three valid inferences.

1. Relaxation infeasible $\Rightarrow$ integer program infeasible, since its feasible set is a subset.
2. Relaxation's optimum happens to be integral $\Rightarrow$ it solves the integer program: feasible there, and attaining a value the integer program cannot beat.
3. Any claimed integer solution better than $z_{\text{LP}}^{\ast }$ is impossible.

One invalid inference. That rounding the relaxation's solution gives the integer optimum, or even a feasible point. Neither follows.

And the converse of (1) fails. A feasible relaxation implies nothing: the polyhedron may contain no integer point at all.

Take

The relaxation. Drop integrality. The binding constraints meet where $6x_1+4x_2=24$ and $x_1+2x_2=6$. From the second, $x_1=6-2x_2$; substituting, $36-12x_2+4x_2=24$, so $-8x_2=-12$ and $x_2=1.5$, giving $x_1=3$. The relaxed optimum is $(3,1.5)$ with value $15+6=21$.

The bound. This is a maximisation, so $z_{\text{LP}}^{\ast }=21$ is an upper bound: no integer plan can exceed $21$.

The integer optimum. Checking feasible whole-number points near the region's boundary: $(4,0)$ gives $24\le 24$ and $4\le 6$, feasible, value $20$. $(2,2)$ gives $12+8=20\le 24$ and $2+4=6\le 6$, feasible, value $18$. $(3,1)$ gives $18+4=22\le 24$ and $3+2=5\le 6$, feasible, value $19$. The best is $(4,0)$ with value $20$.

The gap. $21-20=1$. A tight bound, so had we found $(4,0)$ first, we would have known immediately that at most $1$ was left on the table.

What rounding would have given. $(3,1.5)$ rounds to $(3,2)$: check . Infeasible. Rounding down to $(3,1)$ is feasible with value $19$, worse than the true optimum of $20$, which required increasing $x_1$ rather than adjusting $x_2$.

Problem. A solver has been running on an integer minimisation for twenty minutes. It reports: relaxation optimum $z_{\text{LP}}^{\ast }=4820$, best integer solution found so far $z=4910$. The team asks whether to let it run overnight.

Goal. Say what is known, what is not, and what advice follows.

Relevant principle. The relaxation bounds the integer optimum optimistically; the incumbent bounds it pessimistically. Together they bracket it.

Step 1: the direction of the bound. Minimisation, so the relaxation is a lower bound: $z_{\text{IP}}^{\ast }\ge 4820$. No integer plan costs less than $4820$.

Step 2: the incumbent. A feasible integer solution costing $4910$ has been found, so $z_{\text{IP}}^{\ast }\le 4910$. The optimum is at worst this.

Step 3: bracket the optimum.

Step 4: the gap. At most $90$, which is $90/4910\approx 1.8\mathrm{\%}$ of the incumbent. Whatever the true optimum is, the plan in hand is within $1.8\mathrm{\%}$ of it.

Step 5: the advice. It depends on what $90$ is worth, not on how long the solver has run. If the units are pounds on a weekly schedule, an overnight run to chase at most £90 is poor value. If they are thousands of pounds recurring on an annual contract, the same 90 is worth roughly 50 times more and a night of computing is cheap against it. The bound converts a computational question into a business one, which is its real usefulness.

Step 6: what is not known. Whether $4910$ is optimal. The gap may close because the solver finds a better plan, or because the bound rises as the search proves regions empty. A gap of $90$ does not mean $90$ is available. The true optimum could be $4910$ exactly, with the whole gap being slack in the bound.

Check on a wrong reading. Someone concluding "the optimum is $4820$, so we are losing $90$" has mistaken the bound for an achievable value. Nothing establishes that any integer plan attains $4820$; frequently none does.

Not established: that the bound is attainable. $z_{\text{LP}}^{\ast }=4820$ says no integer plan does better. It does not say any integer plan achieves it, and usually none does.

Not established: feasibility of the integer program. A relaxation with a perfectly good optimum tells you nothing about whether any integer point exists. The polyhedron $2\le x\le 2.5$ is non-empty and contains no integer at all.

Not valid: rounding as a method. In the worked example above, rounding $(3,1.5)$ to $(3,2)$ gives an infeasible point, and rounding down gives a feasible point worse than the optimum. Both failures in one small example.

Not the same as a small gap: a good model. A tight relaxation often reflects how the model was written. Two formulations of the same situation can have identical integer optima and wildly different gaps, and the one with loose linking bounds will be far harder to solve.

Not a valid inference in reverse. Relaxation infeasible proves integer infeasible. Relaxation feasible proves nothing. The implication runs one way only, and asserting the converse is the commonest logical slip here.

Not a bound at all, in the wrong direction. For a maximisation the relaxation is an upper bound. Applying the minimisation statement unchanged concludes that no integer plan does worse, which is both true and useless, and it will be used as though it were the other thing.

The relaxation produces a number and a point. The number is useful; the point usually is not, and keeping them apart is what this unit is for.

The temptation, stated fairly. The relaxation has been solved. Its answer is $(3,1.5)$, and the model needs whole numbers. $1.5$ is halfway between $1$ and $2$, so try $(3,2)$ or $(3,1)$. It feels like tidying rather than guessing.

Why it fails, case one: infeasibility. $(3,2)$ gives . The plan is impossible. Rounding moved the point off the region, and nothing in the rounding step could detect it, you have to go back and check the constraints, which is already more work than rounding pretended to save.

Why it fails, case two: suboptimality. $(3,1)$ is feasible with value $19$. The true integer optimum is $(4,0)$ with value $20$. To find it you must increase $x_1$ past the relaxation's value and decrease $x_2$ to zero. A move rounding will never make, because rounding only adjusts each coordinate to a neighbour.

The structural reason. The continuous and integer optima answer different questions. Which constraints bind at one need not be the ones binding at the other. There is therefore no reason for the integer optimum to be adjacent to the fractional one, and in larger problems they can be far apart in both coordinates and value.

What the bound is actually for. Three things. It limits how good any plan could be, which lets you stop searching with a guarantee. It refutes claimed solutions that beat it. And it guides methods that search properly, branch and bound splits on a fractional variable precisely because the relaxation identified it, then uses the bound to discard whole regions without examining them.

The sentence to carry. The relaxation tells you what you could hope for. It does not tell you what to do.

1. For $max3x_1+2x_2$ subject to $2x_1+x_2\le 7$, $x_1+3x_2\le 9$, $x\ge 0$ integer: solve the relaxation, state the bound with its direction, then find the integer optimum and the gap.

2. In that problem, round the relaxation's solution to nearest and check the result. Report what you find.

3. A minimisation reports a relaxation value of $700$ and an incumbent integer solution of $735$. A colleague says "so we can save $35$". What is wrong with that phrasing?

4. A relaxation is feasible with optimum $12$. What, if anything, follows about whether the integer program has a feasible solution?

5. Two teams model the same situation. Team A uses $M=500$ in its linking constraints, derived from capacity; team B uses $M={10}^6$. Both models are correct. What differs, and why does it matter?

The linear relaxation drops every integrality restriction, with binaries relaxing to the unit interval.

Its optimum bounds the integer optimum optimistically: at or below for a minimisation, at or above for a maximisation. The argument is containment of feasible sets, relaxing only removes restrictions, so the relaxation chooses from a larger menu.

Three inferences follow. An infeasible relaxation proves the integer program infeasible. An integral relaxation solution solves it. Any claimed integer solution beating the bound is impossible. The converse of the first fails: a feasible relaxation proves nothing.

With an incumbent integer solution the two bracket the optimum, and the gap between them says how much is left to gain. That converts a question about how long to keep computing into a question about what the remaining gap is worth.

Rounding is not a method. The rounded point may be infeasible, and where feasible it may be beaten by a plan that rounding could never reach, because the integer optimum need not be adjacent to the fractional one.

A loose bound in a linking constraint widens the gap and makes the program harder. How a model is written determines how much its relaxation is worth.