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.

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

^{2}) 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.