Dynamic parallelization

[ktnr]

Currently, the search is statically parallelized, cp.

TwoStepBranchingProcedure/tsbp/src/BranchAndBound.cpp

Line 242 in 2fa7152

SearchStatus LeftmostActiveOnly::SolveParallelNative()

TwoStepBranchingProcedure/tsbp/src/BranchAndBound.cpp

Line 334 in 2fa7152

SearchStatus LeftmostActiveOnly::SolveParallelTaskflow()

Consider parallelizing the search similar to the following description from CPLEX:

"Search tree

Distributed parallel branch and bound is similar to conventional, shared-memory branch and bound. They differ greatly, however, in their management of the search tree. In a conventional, shared-memory branch and bound, the search tree resides on a single machine, on disk or in shared memory. In contrast, distributed parallel branch and bound literally distributes the search tree across a cluster of machines.

In the CPLEX implementation of distributed parallel branch and bound, the master keeps a number of nodes of the global search tree. If a worker becomes idle, the master sends some of those nodes to that worker. The worker then starts branch and bound on those nodes. However, the worker does not simply solve a node, create some new nodes in doing so, and send them all back to the master. Instead, the worker considers the search tree node received from the master as a new MIP. The worker presolves that MIP and finds an optimal solution for that node using branch and bound. In other words, a worker not only solves a single node; in fact, the worker solves an entire subtree rooted at that node.

While this distributed parallel branch and bound algorithm is running, the master can ask a worker to provide some open nodes (that is, unsolved nodes). The master can then use these nodes to assign work to idle workers. To satisfy such a request from the master, a worker picks a few open nodes from its current tree. Because the current tree in a worker is a subtree of the global tree (indeed, it is the subtree rooted at the node sent to the worker), every node in that subtree is also a node in the global tree."

Also consider using ideas from Shen et al. (2022): Many sequential iterative algorithms can be parallel and (nearly) work-efficient.