Branch-and-bound is the name of a well-known algorithm for solving combinatorial optimization problems. Let P be a problem for which we want to find a least-cost solution from among Nfeasible...

Branch-and-bound is the name of a well-known algorithm for solving combinatorial optimization problems. Let P be a problem for which we want to find a least-cost solution from among Nfeasible solutions. The number N is assumed to be so large as to preclude exhaustive enumeration. In branch-and-bound we think of the N feasible solutions as the leaves of a giant tree. Each node on a path from root to leaf represents a partial solution obtained by extending the partial solution represented by its parent. Starting with the empty solution at the root, the algorithm generates all of the root's descendants. Expansion then continues from the node with least cost and the process is repeated. When the cost of a partial solution exceeds a certain bound, that node is no longer a candidate for expansion. Search continues until a leaf is reached and there are no more nodes to be expanded. This leaf represents a least-cost solution. Show how this algorithm can be made to run in parallel on an MIMD computer.