LP Relaxation Bound ILP/MILP

Definition

The same model—without integrality, with all other constraints intact

Start with an integer (or mixed-integer) linear program and remove only the integrality requirement. Keep all linear constraints and bounds. The resulting LP is the LP relaxation.

ILP/MILP:
minimize/maximize cᵀx + dᵀy
subject to A x + B y ≤ b
x ∈ ℤⁿ (some integer/binary)
y ∈ ℝᵐ (continuous)

LP relaxation:
minimize/maximize cᵀx + dᵀy
subject to A x + B y ≤ b
x ∈ ℝⁿ (with bounds like 0 ≤ x ≤ 1 for binaries)

Solving this LP is usually far cheaper than solving the original ILP/MILP, and its objective value is a bound that branch-and-bound uses at the root and at every node.

If you want the basics of variables/constraints first, start with the ILP beginner’s guide.

Geometry

Think “continuous shape” vs “grid points”

In an LP, the feasible region is a convex polytope. In an ILP, you restrict solutions to integer lattice points inside that polytope. The LP relaxation ignores the grid and may choose a fractional corner that the integer model cannot use.

Direction

Which way is “optimistic”?

This is the same logic behind the “best bound” in solver logs and why the root LP bound is so important for pruning in branch-and-bound.

People ask

Why is the LP relaxation bound important for ILP/MILP performance?

Branch-and-bound solves many relaxations. Tight bounds prune large parts of the search tree. Loose bounds are less informative, so the solver must explore many more nodes before it can prove anything.

People ask

What happens if the LP relaxation solution is already integral?

Then the LP relaxation optimum equals the integer optimum, and the solver may prove optimality at the root (no branching). This often occurs in structured network flow/transportation models—try the Transportation Problem calculator if your model is mainly shipping/flow.

People ask

Can I use the LP relaxation bound to estimate solution quality?

Yes. Compare z_IP (your feasible integer objective) to z_LP (the bound). The distance between them hints at the integrality gap (structural looseness). This is closely related to—but not the same as—the optimality gap during a specific run.

Workflow

Do this whenever a model “feels slow” or “gap won’t close”

1. Solve the integer model: run your formulation in the Integer Linear Programming calculator to get a feasible objective (z_IP).
2. Relax integrality: change x ∈ {0,1} to 0 ≤ x ≤ 1, and x ∈ ℤ to x ∈ ℝ (keeping bounds).
3. Solve the relaxation: run the relaxed model in the Linear Programming calculator to get z_LP.

For minimization, z_LP is a lower bound; for maximization, it’s an upper bound. Connect this to solver stopping behavior via optimality gap in MIP.

Concepts

What is the integrality gap?

The integrality gap measures how much better the LP relaxation can be compared to the best integer solution.

IntegralityGap_abs = |z_IP* - z_LP*|
IntegralityGap_rel = |z_IP* - z_LP*| / (|z_IP*| + ε)

Interpretation

Use relaxation tightness as a “difficulty forecast”

When you stop early, combine this structural view with the run-time gap concept in optimality gap in MIP.

Worked example (numeric)

Example 1: a tiny 0–1 ILP and its LP relaxation

minimize   6x1 + 10x2
subject to x1 + 2x2 ≥ 3
x1, x2 ∈ {0,1}

Checking integer combinations shows only (1,1) is feasible, so z_IP* = 16. Relaxing integrality to 0 ≤ x ≤ 1 still forces feasibility only at (1,1) here, so z_LP* = 16. This toy instance has zero integrality gap.

Worked example (advanced)

Example 2: Big-M linking can create unrealistic LP bounds

0 ≤ x ≤ 10,000·y
y ∈ {0,1}

The LP relaxation can set y tiny (e.g., 0.001) while allowing positive x, creating an overly optimistic bound. Fix by deriving the tightest realistic bound (capacity/demand), e.g., 0 ≤ x ≤ 200y.

Common mistakes

Mistake: relaxing binaries but forgetting the 0–1 bounds

Relaxing x ∈ {0,1} means 0 ≤ x ≤ 1, not “x free.” Dropping bounds can make the LP unbounded or meaningless.

Common mistakes

Mistake: mixing up bound direction (min vs max)

For minimization, LP relaxation gives a lower bound. For maximization, it gives an upper bound. If you flip this, you’ll misread how much improvement could still remain.

Tightening

High-ROI improvements (in the order people actually use)

• Tighten variable bounds: smaller ranges strengthen relaxations immediately.
• Replace huge Big-M values: derive the smallest valid M/U from real limits.
• Add strengthening constraints: valid inequalities that cut fractional artifacts but keep all integer-feasible points.
• Reduce symmetry: fewer equivalent solutions improves search.
• Scale coefficients: avoid extreme magnitudes that cause numerical noise.

If you want a model-improvement workflow, use how to model an ILP.

Glossary

Key terms for LP relaxation and bounds

• LP relaxation: the ILP/MILP with integrality dropped, bounds preserved.
• LP relaxation bound: the relaxation objective; a lower bound (min) or upper bound (max) on the integer optimum.
• Integrality gap: structural difference between LP optimum and integer optimum.
• Optimality gap: run-time difference between incumbent and best bound during a solve.