Class BranchAndBoundThreads

java.lang.Object
topics.branchandbound.utils.threads.BranchAndBoundThreads
Direct Known Subclasses:
RectanglesPlacementTestTimeThreads, RectanglesPlacementThreads
public abstract class BranchAndBoundThreads extends Object

Concurrent Branch and Bound Execution Engine

An abstract base class providing the core algorithmic framework for solving combinatorial optimization problems using a multithreaded Branch and Bound paradigm.

This engine manages the state space tree explicitly using a concurrent priority queue. It dispatches a specified number of worker threads that collaboratively explore the state space, sharing a globally visible upper bound to systematically prune sub-optimal branches across all execution contexts.

Author:
vicegd

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected static Node
    bestNode
    The node representing the optimal valid configuration discovered globally across all threads.
    protected static int
    globalUpperBound
    The global upper bound metric used to prune paths mathematically incapable of yielding a better outcome.
    protected static HeapThreads
    nodeHeap
    The concurrent priority queue managing the active, unexplored nodes in the state space tree.
    protected static Node
    rootNode
    The origin state of the problem environment.

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    BranchAndBoundThreads()
    Initializes the concurrent memory structures required for the execution engine.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    branchAndBound(Node initialNode, int numberOfThreads)
    Executes the multithreaded Branch and Bound systemic loop.
    Node
    getBestNode()
    Retrieves the node encapsulating the mathematically optimal path or configuration.
    Node
    getRootNode()
    Retrieves the foundational starting state of the problem.
    void
    printSolutionTrace()
    Extracts and logs the complete topological lineage of the optimal path, detailing every state transition from the root node to the final solution leaf.

    Methods inherited from class Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • nodeHeap

      protected static HeapThreads nodeHeap
      The concurrent priority queue managing the active, unexplored nodes in the state space tree.

    • bestNode

      protected static volatile Node bestNode
      The node representing the optimal valid configuration discovered globally across all threads. Marked as volatile to ensure immediate visibility across CPU caches.

    • rootNode

      protected static Node rootNode
      The origin state of the problem environment.

    • globalUpperBound

      protected static volatile int globalUpperBound
      The global upper bound metric used to prune paths mathematically incapable of yielding a better outcome. Marked as volatile to guarantee thread-safe visibility.

  • Constructor Details

    • BranchAndBoundThreads

      protected BranchAndBoundThreads()
      Initializes the concurrent memory structures required for the execution engine.

  • Method Details

    • branchAndBound

      public void branchAndBound(Node initialNode, int numberOfThreads)
      Executes the multithreaded Branch and Bound systemic loop.
      Parameters:
      initialNode - The starting mathematical state of the problem environment.
      numberOfThreads - The total number of concurrent worker threads to dispatch.

    • getRootNode

      public Node getRootNode()
      Retrieves the foundational starting state of the problem.
      Returns:
      The root node of the execution tree.

    • getBestNode

      public Node getBestNode()
      Retrieves the node encapsulating the mathematically optimal path or configuration.
      Returns:
      The best discovered node, or null if no valid solution exists.

    • printSolutionTrace

      public void printSolutionTrace()
      Extracts and logs the complete topological lineage of the optimal path, detailing every state transition from the root node to the final solution leaf.