Back to SYMPHONY Home Page

Branch and Cut

Branch and cut is a specific implementation of branch and bound that was first suggested in the seminal work on the subject by Padberg and Rinaldi [19] for solving the well-known Traveling Salesman Problem. Since then, many implementations (including ours) have been fashioned after their ideas. In branch and cut, the bounding operation is accomplished using the tools of linear programming. Typically, the integrality constraints of an integer programming formulation of the problem are relaxed to obtain a linear programming (LP) relaxation and then this formulation is strengthened by adding cutting planes, i.e. inequalities valid for the convex hull of solutions to the original problem.

  

Figure 1: Bounding in the branch and cut algorithm

For 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 usually 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 [18]) 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, 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 entire generic branch and cut algorithm.

  

Figure 3: Description of the generic branch and cut algorithm

In the remainder of the paper, we will sometimes refer to the search tree. This term is derived from the useful practice of viewing the list of subproblems processed during the algorithm as the nodes of a graph in which each subproblem is connected to its parent. This graph is known as the search tree. 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 first node from which all others descend.