CPSC 449, A short intro to branch-and-bound based search

Branch-and-bound algorithms are a special case of and-tree-based search methods (for complete definitions, see this document. Note that it can only be accessed from within the UofC network and there might be some computers that for some reason are not recognized as being in this network, but using our wireless network works.). They are used to find optimal combinations of a group of decisions. More precisely, they assume that a solution to a given problem instance needs to provide a particular choice for each of the decisions in the group. The combined choices have to fulfill all hard constraints and we are looking for the solutions(s) with optimal value regarding a so-called objective function (which is often defined using soft constraints and penalties for violating them).

The general idea of branch-and-bound is to create a search tree that reflects the possible choices one by one, making sure that all possible solutions are covered when a node of the tree is subdivided into its successor nodes. Such a node usually represents the concrete choice for a subset of the decisions and the direct successor nodes represent all possible choices for one additional decision (not in the set of the parent node). Each successor node represents exactly one of the choices. This explains the "branch" of branch-and-bound.

The "bound" part deals with closing nodes. Naturally, a node with concrete choices for a subset of decisions that do not fulfill the hard constraints is immediately closed so that the potential subtree below it is not explored. But branch-and-bound algorithms also use a so-called bound function fbound that tries to predict how good the best solution below a node can, at best, be. If the fbound-value of a node is worse than the objective function value of the best solution found so far, this node can be closed, since below it can be no better solution than the best one already known. Naturally, for this to work, the fbound function needs to approximate the objective function in such a way that for a solution (i.e. all decisions are made) the values are the same and for a partial solutions (i.e. a node with some decisions not made) the value of fbound is better than or equal to the best solution that contains the partial solution.

Usually, the fbound function is also important for the search control of a branch-and-bound based search system. Such a search control has to decide which of the non-closed leaf nodes of the current tree should be expanded and which decision out of those that are not in the subset of decisions of this node should be used to create the successor nodes. To use fbound to close nodes, a valid solution is needed, so that a search control should try to find one as quickly as possible. This means selecting nodes in a depth-first fashion. After a first solution is available, many search controls select nodes based on their fbound-value.

For selecting the particular decision that is used to extend a node, the type of constraints that the problem uses is of quite some influence and what is a good heuristic for one type can be bad for another. In general, it is a good idea to select the decision that is the most constrained, i.e. has the least number of choices that are not immediately leading to nodes that should be closed. The nexessary tiebreakers then have to be based on knowledge about the different constraints.