General Branch and Bound Method

Our general technique for branch and bound algorithms involves modeling the solution space as a tree and then traversing the tree exploring the most promising subtrees first. This is continued until either there are no subtrees into which to further break the problem, or we have arrived at a point where, if we continue, only inferior solutions will be found. A general algorithm for branch and bound searching is presented in figure 1.

Figure 1 - General Branch and Bound Searching

Let's examine this technique more closely and find out what is needed to solve problems with the branch and bound method using the chromatic number and knapsack algorithms from the 'Intelligent Search' section of this chapter.

We need first to define the objects that make up the original problem and possible solutions to it.

• Problem instances. For the knapsack problem this would consist of two lists, one for the weights of the items and one for their values. Also we need an integer for the knapsack capacity. For chromatic numbers (or graph coloring), this is just a graph that could be presented as an adjacency matrix, or better yet, an adjacency edge list.
• Solution tree. This must be an ordered edition of the solution search space, possibly containing partial and infeasible solution candidates as well as all feasible solutions as vertices. For knapsack we built a depth-first search tree for the associated integer programming problem with the objects ordered by weight. In the chromatic number solution tree we presented partial graph colorings with the first k nodes colored at level k. These were ordered so that if a node had a particular color at a vertex, then it remained the same color in the subtree.
• Solution candidates. For knapsack, a list of the items placed in the knapsack will suffice. Chromatic numbering involves a list of the colors for each vertex in the graph. But, it is a little more complex since we use partial solutions in our search, so we must indicate vertices yet to be colored in the list.

An essential rule to be followed in defining solution spaces for branch and bound algorithms is the following.

If a solution tree vertex is not part of a feasible solution, then the subtree for which it is the root cannot contain any feasible solutions.

This rule guarantees that if we cut off search at a vertex due to unfeasibility, then we have not ignored any optimum solutions.

Now, we present the definitions for bounds used in the above algorithm.

Lower bound at a vertex. The smallest value of the objective function for any node of the subtree rooted at the vertex.

Upper bound at a vertex. The largest value of the objective function for any node of the subtree rooted at the vertex.

For chromatic number we used the number of colors for the lower bound of a partial or complete solution. The lower bound for knapsack vertices was the current load, while the upper bound was the possible weight of the knapsack in the subtree.

Next we must have the following methods (or algorithms) which operate upon and help us to analyze the objects.

• Feasible solution checker. For knapsack, we merely insure that the sum of the weights of the items in the knapsack is no more than its capacity. Chromatic numbering involves checking to see if any two adjacent vertices are the same color.
• Objective function. For knapsack, sum the values of the items in the knapsack. For chromatic numbers, count the colors.
• Lower bound function. For knapsack and chromatic number, this is just the objective function.
• Upper bound function. For knapsack this was the lower bound plus the sum of the weights that could be added. Chromatic numbers did not have a useful upper bound function since a minimum was optimal.

At this point complexity should be mentioned. Computing these for the knapsack problem is easy because they all involve summing the weights. A good strategy is to record the knapsack loads as each vertex in the search tree is visited so that the objective and upper bound functions require one addition and the feasibility check utilizes one comparison.

Chromatic numbering involves more work when solution candidates are checked for feasibility. In the worst case, all of the graph edges must be examined, and this possibly requires O(n²) steps. One way to reduce this a little is to use partial solutions where the children of a vertex have one more node colored than their parent.

Let us now turn our attention to two interrelated topics: solution space design and searching the space. Creative designers build a space that can be searched without too much complexity - either in the bounding computations or in the space required to hold the solution candidates under consideration and those about to be considered. Some helpful techniques are the following.

• Design a solution space that contains a subset of the entire solution space that includes an optimum solution.
• Use a depth-first strategy so that only a small portion of the search tree needs to be stored at any stage.
• Make the feasibility checks and bound computations cumulative so that time is minimized.
• Order the children of each vertex so that the most promising solutions are examined first.
• Use a good approximation to the optimum solution as the initial best solution

Our last note involves correctness. Two things must be shown. First, an optimum solution exists in the solution space tree. And secondly, the optimum solution is found by the branch and bound search algorithm.