Branch-and-Cut

John E. Mitchell

$$\begin{array}{lrclr} {\min} & c^T x \\ \mbox{subject to} & ... ...\!\!R^n \\ & x_i && \mbox{integer, } i=1,\ldots,p. \end{array}$$

$L$ is the set of active nodes in the branch-and-cut tree. The value of the best known feasible point for $(ILP)$ is $\bar{z}$, which provides an upper bound on the optimal value of $(ILP)$. Further, $\mbox{{\underline{$z$}}$_{l}$}$ is a lower bound on the optimal value of the current subproblem under consideration. The value of the LP relaxation of the subproblem can be used to update  $\mbox{{\underline{$z$}}$_{l}$}$.

In some situations, a very large number of violated cutting planes are found in Step 5, in which case it is common to sort the cutting planes somehow (perhaps by violation), and add just a subset. The subproblems formed in Step 7 are called child subproblems, with the previous problem $ILP^l$ being the parent subproblem. Usually, the partitioning takes the form of a variable disjunction: $x_i \leq a$ versus $x_i \geq a+1$ for some variable $x_i$ and integer $a$, as in the example.

The relaxations can be solved using any method for linear programming problems. Typically, the initial relaxation is solved using the simplex method. Subsequent relaxations are solved using the dual simplex method, since the dual solution for the relaxation of the parent subproblem is still feasible in the relaxation of the child subproblem. Further, when cutting planes are added in Step 5, the current iterate is still dual feasible, so again the modified relaxation can be solved using the dual simplex method. It is also possible to use an interior point method, and this can be a good choice if the linear programming relaxations are large.

If the objective function and/or the constraints in $(ILP)$ are nonlinear, the problem can still be attacked with a branch-and-cut approach.

Of course, there are several issues to be resolved with this algorithm. These include the major questions of deciding whether to branch or to cut and deciding how to branch and how to generate cutting planes.