LP Relaxation¶

Definition¶

The LP relaxation of an integer linear program removes its integrality requirements and keeps the objective and all other restrictions. In particular, a binary variable becomes a continuous variable satisfying $0\le x_j\le1$ $1$ .

Interpretation¶

The LP relaxation asks how good the best decision would be if the integer requirements were dropped. It is an ordinary LP, solvable with the graphical method or the simplex method, and as a relaxation it keeps every integer-feasible point. Its optimum therefore bounds the original integer optimum.

A feasible polygon with its integer points, the objective line touching the LP optimum (3.5, 1.25) with value 13, and the integer optimum (3, 1) with value 11.

The shaded polygon is the feasible region of the relaxation, and the filled dots are the integer-feasible points inside it. The objective line $3x_1+2x_2=13$ touches the polygon at the corner $(3.5,1.25)$ , the LP optimum with $z_R=13$ $13$ , while the best lattice point is $(3,1)$ with $z^*=11$ $11$ .

Dropping integrality enlarges the feasible set, so the relaxed optimum $z_{LP}$ is an upper bound on the integer optimum $z_{IP}$ for this maximization.

The bound holds because the relaxation chooses among more points, so it can only do at least as well. Its value is an upper bound for maximization and a lower bound for minimization. If the relaxed optimum happens to be integral, it is feasible for the original problem and no integer point can beat it, so it is integer-optimal. A binary variable keeps its bounds $0\le x_j\le1$ $1$ : dropping them too still gives a relaxation, but its bound can only become weaker.

The LP relaxation is solved at every node of branch-and-bound and is the starting point of the rounding heuristic. A common slip is to report the relaxed value as the integer optimum. It is only a bound, and it need not be close: in the figure it is $13$ against the true $11$ .

Key Results¶

Its value is an upper bound for maximization and a lower bound for minimization.
If a relaxed optimizer satisfies every original integrality restriction, it is also integer-optimal.
Do not drop binary upper bounds when dropping binarity.

Examples¶

In the illustrated model, the relaxed optimum $(3.5,1.25)$ gives value 13. Rounding to $(4,1)$ violates the constraints; $(3,1)$ is feasible and happens to be integer-optimal with value 11. That success does not establish a general rounding rule.

The project-selection relaxation allows $x_3=0.2$ and obtains 3.52 at the root.
An integral relaxed solution such as $(1,0,1,1,0)$ is a feasible candidate for the original project model.

Prerequisites¶

Sources¶

OR Modelling · Week 3

Aliases: linear relaxation, linear programming relaxation, continuous relaxation

Last updated: 20 October 2026 03:02