Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

Parallel Formulations of Depth-First Branch-and-Bound

• Parallel formulations of depth-first branch-and-bound search (DFBB) are similar to those of DFS.

• Each processor has a copy of the current best solution. This is used as a local bound.

• If a processor detects another solution, it compares the cost with current best solution. If the cost is better, it broadcasts this cost to all processors.

• If a processor's current best solution path is worse than the globally best solution path, only the efficiency of the search is affected, not its correctness.