coin-or / coin-or/jorlib

TODO: Make BranchAndPrice multi threaded

Open
#2 1 comment 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.