Branch and Cut

In many applications, the bounding operation is accomplished using the tools of linear programming (LP), a technique first described in full generality by Hoffman and Padberg [20]. This general class of algorithms is known as LP-based branch and bound. Typically, the integrality constraints of an integer programming formulation of the problem are relaxed to obtain a LP relaxation, which is then solved to obtain a lower bound for the problem. In [29], Padberg and Rinaldi improved on this basic idea by describing a method of using globally valid inequalities (i.e., inequalities valid for the convex hull of integer solutions) to strengthen the LP relaxation. They called this technique branch and cut. Since then, many implementations (including ours) have been fashioned around the framework they described for solving the Traveling Salesman Problem.

Figure 4.1: Bounding in the branch and cut algorithm

As an example, let a combinatorial optimization problem $\hbox{\em CP} = (E, {\cal F})$ with ground set $E$ and feasible set ${\cal F} \subseteq 2^E$ be given along with a cost function $c \in {\bf R}^E$. The incidence vectors corresponding to the members of ${\cal F}$ are sometimes specified as the the set of all incidence vectors obeying a (relatively) small set of inequalities. These inequalities are typically the ones used in the initial LP relaxation. Now let ${\cal P}$ be the convex hull of incidence vectors of members of ${\cal F}$. Then we know by Weyl's Theorem (see [28]) that there exists a finite set ${\cal L}$ of inequalities valid for ${\cal P}$ such that

$${\cal P} = \{x \in {\bf R}^n: ax \leq \beta\;\;\forall\;(a, \beta) \in {\cal L}\}.$$ (4.1)

The inequalities in ${\cal L}$ are the potential cutting planes to be added to the relaxation as needed. Unfortunately, it is usually difficult, if not impossible, to enumerate all of inequalities in ${\cal L}$ or we could simply solve the problem using linear programming. Instead, they are defined implicitly and we use separation algorithms and heuristics to generate these inequalities when they are violated. In Figure 4.1, we describe more precisely how the bounding operation is carried out in branch and cut.

Figure 4.2: Branching in the branch and cut algorithm

Once we have failed to either prune the current subproblem or separate the current fractional solution from ${\cal P}$, we are forced to branch. The branching operation is accomplished by specifying a set of hyperplanes which divide the current subproblem in such a way that the current solution is not feasible for the LP relaxation of any of the new subproblems. For example, in a combinatorial optimization problem, branching could be accomplished simply by fixing a variable whose current value is fractional to 0 in one branch and 1 in the other. The procedure is described more formally in Figure 4.2. Figure 4.3 gives a high level description of the generic branch and cut algorithm.

Figure 4.3: Description of the generic branch and cut algorithm

In the remainder of the manual, we often use the term search tree. This term derives from the common representation of the list of subproblems as the nodes of a graph in which each subproblem is connected only to its parent and its children. Storing the subproblems in such a form is an important aspect of our global data structures. Since the subproblems correspond to the nodes of this graph, they are sometimes be referred to as nodes in the search tree or simply as nodes. The root node or root of the tree is the node representing the initial subproblem.