Recently, I published blog post introducing the concept of heuristic search, this can be found here. This is a continuation of that post, in which I will discuss linear space search methods, in particular branch and bound.
Linear space search methods involve the exploration of a search tree in a systematic exploration of the solution space for a problem. Often the search tree analysed is considerably larger than the problem graph for the problem itself. These algorithms often consider the search tree nodes as members in a search space. Search trees are designed to be simple to analyse in comparison to their underlying problem graphs due to each node having a unique path between it and the root. This
means that members of the solution space in the search space are paths.
Branch and bound
Branch and bound is a method often used in operational research in order to find solutions to complicated combinatorial optimisation problems. Here, the set of all possible solutions are represented as a tree with the complete set of all possible solutions at the root. Branching refers to the creation of sub-problems, and bounding refers to the dismissal of partial solutions which are worse than the currently found optimal solution. Hence, in order to achieve this, the upper and lower bounds for optimal solutions, U and L, must be calculated at each branch on the tree. In order to apply the branch and bound method to problems with a general solution space, depth first search is used with U and L applied at each stage. Here, the principle of depth first search can be applied, thus creating a branch and bound search tree.
Consider an example where a problem has a solution space representing all possible configurations of a system, and the aim is to find the configuration which minimises some objective function. The branch and bound algorithm progresses by iterating the
following steps at each of a set of predetermined branching points.
- Firstly, the problem is branched using a branching rule specific to the problem in order to produce two or more (usually disjoint) subsets of the solution space.
- Second, a heuristic is used to estimate a lower bound on the value of the objective function for any candidate solution contained in the first branch from the branching point, which is at that point the lowest value for L found. The algorithm then does the same for each of set of solutions for each branch sequentially and determines whether or not its lower bound is greater than the current lowest found lower bound for all branches which have already been checked. If this is the case, then the that branch is pruned and that set of possible solutions discarded.
This results in only a single branch remaining, on which the process can now be repeated so as to repeatedly branch the set of possible solutions until the optimal solution has been found. An advantage of this method is the ability to keep track of the upper bound as well as the lower bound and stop branching when the gap between lower and upper bounds reaches a certain threshold and so solutions can be considered good enough.
[…] selection of heuristic search methods will be outlined in future posts, while a brief overview of some basic search methods can be seen […]