TODO: Make BranchAndPrice multi threaded
- Dominant language
- Java
- Stars
- 75
- Forks
- 39
- PR merge metrics
- No merged PRs in 30d
Description
Currently, the nodes in the Branch-and-Price tree (AbstractBranchAndPrice.java, frameworks.columnGeneration package)are solved one by one. To take advantage of modern CPUs, functionality should be added to allow these nodes to be solved in parallel. This can be realized by rewriting the method public void runBranchAndPrice(long timeLimit). Some worker threads having access to the queue containing the BAPNodes can take nodes one by one and solve them.
- Synchronization is obviously required to access the data fields in AbstractBranchAndPrice.java.
- Ideally, when a node is solved, the other worker threads are informed about the results. If for example a better integer solution is found, computations in a node may be interrupted based on the bound of the node.
Issues which have to be taken care off:
-GraphManipulator.java: for efficiency reasons, there's currently only one master problem and pricing problem. When processing a node, the master problem and pricing problem are modified automatically to reflect the problem represented by the node, i.e. the branching decisions modify the state of the master/pricing problems. Solving multiple nodes in parallel would require duplications of the master and pricing problems.
-SimpleBAPLogger.java needs to be rewritten: logging becomes more difficult. Logging messages from various nodes being solved in parallel may not become tangled up.
-bapNodeComparators: it must be guaranteed that the tree is processed in a consistent order, thereby having a deterministic solve procedure, each time an instance is solved with the exact same settings.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in AbstractBranchAndPrice.java with runBranchAndPrice(long timeLimit), then read GraphManipulator.java, SimpleBAPLogger.java, and the bapNodeComparators. Define how worker threads share and interrupt node processing, how master and pricing problems are duplicated, how logging remains separate, and how deterministic tree order is preserved.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100