Branch-and-bound

At each level, a choice is made that leads to the remaining posibilities. $/C_i$ means ``without" $C_i$. Consequently the tree is representing problems such as $N$ queens and travelling salesman. Some problems such as alpha-beta search don't reduce in this way.

The load balancing aspects for branch-and-bound algorithms make its parallelization difficult, the primary difficultly being that the usual assumption requires no a priori information about the likely location of the search target.

The usual technique for eliminating subtrees from the search is called ``pruning". A cut-off or bounding function is required to bound the possible outcomes of the subtree. Use of the bounding function allows elimination of whole subtrees without having to search through them.

However the bounding function usually requires a comparison across a number of subtrees. Since a parallel implementation may already have a processor search within a subtree, the search computations are wasted if it is found (subsequently but in parallel) that the subtree cannot possibly lead to a better solution.

Pruning is inherently sequential.

A node in the tree that is not a leaf node and has not had all of its children searched is called a live node.

A node which is having its children searched is being expanded.

A node with all its children explored is called dead.

Branch and bound uses a queue of live nodes and proceeds to expand each node, adding new nodes to queue as they are found.

Several issues make the paralellization of branch and bound complicated.

We already know that pruning requires communication between all processors in order to ensure subtrees are not unnecessarily searched.

The size of the subtree may not be known in advance.

The queue is a shared data structure.

To avoid the problems of a centralized queue, one could distribute the queue among processors and have them broadcast better nodes (for pruning purposes) to each other at intervals.

If a priority queue is required then parallel insertion using a parallel search (as explained earlier) can be used to insert new subtree nodes into the queue.