LP Relaxation

The LP relaxation of an integer program is obtained by removing integrality restrictions.

Definition

If an ILP contains:

its LP relaxation replaces this with a continuous constraint, usually:

or:

If a binary variable appears:

its relaxation is:

Why It Is Useful

The LP relaxation is easier to solve than the ILP.

It can give:

• a bound on the best possible integer objective value
• insight into which constraints are important
• a starting point for integer algorithms
• a warning that the integer problem may be hard

Bounds from Relaxation

For a maximization ILP, the LP relaxation gives an upper bound on the integer optimum.

For a minimization ILP, the LP relaxation gives a lower bound on the integer optimum.

This happens because the relaxed feasible set contains all integer feasible points and possibly more.

Rounding Warning

Rounding a relaxed solution is not guaranteed to work.

Example: if the constraint is:

then the relaxed point $(0.75,0.75)$ is feasible, but rounding to $(1,1)$ gives:

which is infeasible.

Tight Relaxation

A relaxation is strong when its solution is close to the integer optimum.

A weak relaxation gives a bound that is far from the true integer optimum.

Checklist

Use LP relaxation to understand the ILP, but do not treat a fractional solution as a valid integer solution.

See Also

• Integer Linear Programming
• Integer Variables
• Binary Variables
• Knapsack Problem

Exam checkpoint

For ILP questions, state clearly which variables are integer or binary. Do not use the LP relaxation answer as the integer answer unless it is already integral.