Routine overview

The B&B routine is fairly modular. It consists of four main parts:

• The main B&B strategy routine
• The Branch generator
• A branch sorting routine
• The heuristic calculation routine

The blocks interact as sketched in figure 3.1. Of course this presentation of the B&B algorithm is overly simple. Many other routines are involved, some of the major ones are memory handling and target function ($f(\cdot)$) calculation.

Figure 3.1: The branch and bound routine

The responsibilities of the four major blocks are:

B&B strategy

This routine traverses the list of live nodes, calling the branch generator for every live node it encounters. Occasionally it will call the sort algorithm. When this routine runs out of live nodes, the search is complete, and the current best solution is returned as the overall best solution.

Branch generator

The branch generator generates branches for some given live node. If one of the branches turns out to be a final solution, and that solution is better than the currently best, the best solution is updated, and the sort algorithm invoked. The branches which seem promising (based upon the heuristic) are inserted in a pseudo-sorted manner into the list of live nodes. If a branch has a lower estimated cost than the first live node, it's inserted first. Otherwise, the branch is simply inserted as number two in the list of live nodes. This special ordering of new live nodes contributes to the hybrid nature of the search, and places it somewhere between best-first and depth-first. The ordering was experimentally found to be good.

Sorting routine

The sorting routine sorts the list of live nodes after their $h(s)+f(s)$ values, eg. the estimate of what a possible completion of the search thru the live node may cost. If this was called every time a new live node was to be investigated, the search would be a best-first. The fact that the sort algorithm is only called occasionally, makes the search a hybrid between depth-first and best-first.

Heuristic calculation

Calculation of the heuristic $h(s)$. This is the routine that ultimately has required the most time and efforts. Providing a good heuristic in realistic time is not at all simple. Many approaches where tried, some of which are described in chapter 4. The one that made it into the final optimizer, calculates a possible ordering of rows, given some column ordering, and returns the resulting cost as the heuristic.