A Branch-and-Cut Example
The integer programming problem
is illustrated in the figure.
The feasible integer points are marked.
The linear programming relaxation (or LP relaxation)
is obtained by ignoring the integrality restrictions
and is indicated by the polyhedron contained in the solid lines.
A branch-and-cut approach first solves the linear programming
relaxation, giving the point
), with value
. There is now a choice: should the LP relaxation be
improved by adding a cutting plane, for example,
should the problem be divided into two by splitting on a variable?
If the algorithm splits on
, two new problems are obtained:
The optimal solution to the original problem will be the better of the
solutions to these two subproblems.
The solution to the linear programming relaxation of
is , with value .
This solution is integral, so it solves , and
becomes the incumbent best known feasible solution.
The LP relaxation of
has optimal solution , with value .
This point is nonintegral, so it does not solve ,
and it must be attacked further.
Assume the algorithm
uses a cutting plane approach and adds the inequality
This is a valid inequality, in that it is satisfied by every integral
point that is feasible in . Further, this
inequality is violated by , so it is a cutting plane.
The resulting subproblem is
The LP relaxation of has
optimal solution , with value .
Notice that the optimal value for this modified relaxation
is larger than the value of the incumbent solution.
The value of the optimal integral solution to the second subproblem
must be at least as large as the value of the relaxation.
Therefore, the incumbent solution
is better than any feasible integral solution for ,
so it actually solves the original problem.
The progress of the algorithm is illustrated below.
Notice that the cutting plane introduced in the second subproblem
is not valid for the first subproblem. This inequality can be modified
to make it valid for the first subproblem by using a lifting