A Branch-and-Cut Example

John E. Mitchell

The integer programming problem

\begin{displaymath} \begin{array}{lrcrclr} \min \quad z\; :=& -6x_1 & - & 5x_2 \... ...eq & 5 \\ &&& x_1,x_2 & \geq & 0, \mbox{ integer}. \end{array}\end{displaymath}

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 \((2\frac{3}{7},3\frac{5}{7}\)), with value \(-33\frac{1}{7}\). There is now a choice: should the LP relaxation be improved by adding a cutting plane, for example, \(x_1+x_2 \leq 5\), or should the problem be divided into two by splitting on a variable?


\begin{picture}(370,430)(-20,-20) \put(0,0){\vector(1,0){370}} \put(0,0){\vector... ...40)(20,0){3}{\circle*{1}} \multiput(240,360)(20,0){1}{\circle*{1}} \end{picture}

If the algorithm splits on ${\mathbf{x_1}}$, two new problems are obtained:

\begin{displaymath} \begin{array}{lrcrclr} \min \quad z\; :=& -6x_1 & - & 5x_2 \... ...hbf{3} \\ &&& x_1,x_2 & \geq & 0, \mbox{ integer}. \end{array}\end{displaymath}

and

\begin{displaymath} \begin{array}{lrcrclr} \min \quad z\; :=& -6x_1 & - & 5x_2 \... ...hbf{2} \\ &&& x_1,x_2 & \geq & 0, \mbox{ integer}. \end{array}\end{displaymath}

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 $(Eg1)$ is \((3,2)\), with value \(-28\). This solution is integral, so it solves $(Eg1)$, and becomes the incumbent best known feasible solution. The LP relaxation of $(Eg2)$ has optimal solution \((2,3.5)\), with value \(-29.5\). This point is nonintegral, so it does not solve $(Eg2)$, and it must be attacked further.


Assume the algorithm uses a cutting plane approach and adds the inequality \({\mathbf{2x_1+x_2\leq 7}}\) to $(Eg2)$. This is a valid inequality, in that it is satisfied by every integral point that is feasible in $(Eg2)$. Further, this inequality is violated by \((2,3.5)\), so it is a cutting plane. The resulting subproblem is

\begin{displaymath} \begin{array}{lrcrclr} \min \quad z\; :=& -6x_1 & - & 5x_2 \... ...hbf{7} \\ &&& x_1,x_2 & \geq & 0, \mbox{ integer}. \end{array}\end{displaymath}

The LP relaxation of $(Eg3)$ has optimal solution \((1.8,3.4)\), with value \(-27.8\). 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 $(Eg3)$, so it actually solves the original problem.


The progress of the algorithm is illustrated below.


\begin{picture}(300,300) \put(150,270){\oval(120,50)} \put(110,280){\makebox(0,0... ...laxation:}} \put(205,20){\makebox(0,0)[bl]{\((1.8,3.4),z=-27.8\)}} \end{picture}

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 technique.


John Mitchell
2009-03-16