Integers and the Relaxation - Integer Programming & Branch-and-Bound

Integer programming keeps the same linear inequalities but restricts the decision variables to lattice points. The LP relaxation drops that restriction, giving a fast upper bound for a max problem. This lesson shows why the relaxed optimum can be exact arithmetic and still not be an integer answer.

highlighted = computed this step

Relax integrality

Dropping the integer restriction gives the LP point (6/5, 8/5) with z=22/5. Why: the relaxed problem is easier and can only improve a max bound.

z_{LP}=22/5

Not an integer answer

The point (6/5, 8/5) is fractional, so it is not a valid IP solution. Why: an upper bound is not the same thing as a feasible integer point.

x^*_{LP}\notin \mathbb{Z}^{2}

Integer target

The integer optimum will be (0, 2) with z=4. Why: branch-and-bound has to close the gap between the LP bound and the integer answer.

z_{IP}=4

Diagram note

The red point is the LP relaxation optimum; integer feasibility is a stricter rule. Pixel positions are rounded for layout; every number shown is exact.

\text{LP bound first, integer proof later}