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.

As an example, let a combinatorial optimization problem with

The inequalities in 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 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.

Once we have failed to either prune the current subproblem or separate the current fractional solution from , 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.

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.

2010-03-24