Cutting Planes

LP relaxation

An inequality that is

• satisfied by all

feasible integer points

• not satisfied by the

optimal solution to the LP

(“chops off LP optimum”)

Separation Problem

zLP

Previous slide

Next slide

Back to first slide

View graphic version