Branch, Cut, and Price

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 [17]. 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 [27], 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 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 [26]) 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}\}.$$ (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 1, we describe more precisely how the bounding operation is carried out in branch and cut.

Figure 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 2. Figure 3 gives a high level description of the generic branch and cut algorithm.

Figure 3: Description of the generic branch and cut algorithm

As with cutting planes, the columns of $A$ can also be defined implicitly if $n$ is large. If column $i$ is not present in the current matrix, then variable $x_i$ is implicitly taken to have value zero. The process of dynamically generating variables is called pricing in the jargon of linear programming, but can also be viewed as that of generating cutting planes for the dual of the current LP relaxation. Hence, LP-based branch and bound algorithms in which the variables are generated dynamically when needed are known as branch and price algorithms. In [5], Barnhart, et al. provide a thorough review of these methods.

When both variables and cutting planes are generated dynamically during LP-based branch and bound, the technique becomes known as branch, cut, and price (BCP). In such a scheme, there is a pleasing symmetry between the treatment of cuts and that of variables. We will further examine this symmetry later in the manual. For now, however, it is important to note that while branch, cut, and price does combine ideas from both branch and cut and branch and price (which are very similar to each other anyway), combining the two techniques requires much more sophisticated methods than either one requires on its own. This is an important idea that is at the core of our design.

In the remainder of the manual, we will 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 will 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.