The Linear Relaxation and Its Bound

Drop the integrality restriction and an integer program becomes a linear program that can actually be solved. Its optimal value is a bound on the integer optimum, never worse, in a direction fixed by whether you are minimising or maximising, and that bound is the foundation of every serious integer method. What the relaxation does not give you is the answer: rounding its solution is not generally valid, and often not even feasible.

Definition

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 \leq x_{j} \leq 1$ .

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

The bound. Every feasible point of the integer program is feasible for the relaxation, since the relaxation has strictly fewer restrictions. Optimising over a larger set can only do better or equally well, so for a minimisation

z_{LP}^{*} \leq z_{IP}^{*},

and for a maximisation the inequality reverses. The relaxation is optimistic: it promises at least as much as the integer program can deliver.

The gap. The difference $| z_{IP}^{*} - z_{LP}^{*} |$ is the integrality gap. A small gap means the bound is informative; a large one means it says little.

Three inferences the bound licenses.

If the relaxation is infeasible, the integer program is infeasible, its feasible set is a subset.
If the relaxation's optimal solution happens to be integral, it solves the integer program: it is feasible there and attains a value the integer program cannot beat.
The bound rules out claimed integer solutions better than $z_{LP}^{*}$ , which makes it a check as well as a guide.

What it does not license. Rounding. A rounded relaxation solution may be infeasible, and when feasible it may be far from optimal. Neither failure is rare.

Formal statement

For $min {c^{T} x : x \in F \cap Z^{I}}$ with relaxation $min {c^{T} x : x \in F}$ : since $F \cap Z^{I} \subseteq F$ , $z_{LP}^{*} \leq z_{IP}^{*}$ . Maximisation reverses. Integrality gap $= | z_{IP}^{*} - z_{LP}^{*} |$ .

Assumptions and scope

The bound's direction follows from the objective sense. For a minimisation the relaxation is a lower bound; for a maximisation an upper bound. Applying the minimisation statement to a maximisation inverts the conclusion.
An infeasible relaxation proves the integer program infeasible. The converse fails: a feasible relaxation says nothing, since the polyhedron may contain no integer point at all.
An integral relaxation solution solves the integer program. This is a fortunate case rather than a method, and it cannot be arranged.
Rounding a relaxation solution is not a valid solution method. The rounded point may be infeasible, and where feasible it may be far from the integer optimum.
A loose bound in a linking constraint weakens the relaxation and makes the gap larger. How a model is written affects how useful its relaxation is, which is why tight formulations matter.

Forms this is expressed in

The same content in several forms. Each makes something visible that the others leave implicit, so moving between them is part of understanding the topic rather than a presentation choice.

geometric

The relaxation bounds, and rounding does not reach, the integer optimum

The relaxation bounds, and rounding does not reach, the integer optimum

The relaxation of $max 5 x_{1} + 4 x_{2}$ subject to $6 x_{1} + 4 x_{2} \leq 24$ and $x_{1} + 2 x_{2} \leq 6$ shown as a shaded polygon with every feasible integer point marked. Four points are singled out. The relaxed optimum is the fractional corner $(3, 1.5)$ with value $21$ , which bounds the integer problem from above. The best integer point is $(4, 0)$ with value $20$ , so the integrality gap is $21 - 20 = 1$ . Rounding the relaxed solution down gives $(3, 1)$ , which is feasible but worth only $19$ ; rounding up gives $(3, 2)$ , which lies outside the polygon and is infeasible. Neither rounding reaches the true integer optimum, which is why rounding is not a method.

The relaxation drawn against the integer points it is meant to bound. The shaded polygon is the feasible set once integrality is dropped; the marked lattice points are the only plans the integer program may actually choose.

The relaxation's optimum sits at a corner of the polygon, and that corner is generally not a lattice point. The distance between its value and the best lattice value is the gap, and it is why the bound is optimistic rather than attainable.

The picture also shows why rounding is not a method: the nearest lattice point to a fractional corner may lie outside the polygon altogether, and the true integer optimum can sit in a different direction entirely.

Worked material

Example

A bound, a gap, and an inference

Take

max 5 x_{1} + 4 x_{2} subject to 6 x_{1} + 4 x_{2} \leq 24, x_{1} + 2 x_{2} \leq 6, x_{1}, x_{2} \geq 0 and integer .

The relaxation. Drop integrality. The binding constraints meet where $6 x_{1} + 4 x_{2} = 24$ and $x_{1} + 2 x_{2} = 6$ . From the second, $x_{1} = 6 - 2 x_{2}$ ; substituting, $36 - 12 x_{2} + 4 x_{2} = 24$ , so $- 8 x_{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_{LP}^{*} = 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 \leq 24$ and $4 \leq 6$ , feasible, value $20$ . $(2, 2)$ gives $12 + 8 = 20 \leq 24$ and $2 + 4 = 6 \leq 6$ , feasible, value $18$ . $(3, 1)$ gives $18 + 4 = 22 \leq 24$ and $3 + 2 = 5 \leq 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 $18 + 8 = 26 > 24$ . 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}$ .

Non-example

What the bound does not establish

Not established: that the bound is attainable. $z_{LP}^{*} = 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 \leq x \leq 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.

Contrast

A bound is not an answer

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 $6 (3) + 4 (2) = 26 > 24$ . 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.

Common errors

Common misconception

The integer optimum is found by solving the linear relaxation and rounding its solution to the nearest whole numbers, so the relaxation effectively solves the problem.

The Linear Relaxation and Its Bound

Assumptions and scope

Forms this is expressed in

Worked material

A bound, a gap, and an inference

What the bound does not establish

A bound is not an answer

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history