Class BranchAndBound

java.lang.Object
topics.branchandbound.utils.BranchAndBound
Direct Known Subclasses:
AgentsTasks, EightPuzzle, RectanglesPlacement, RectanglesPlacementTestTime, StringInterleavingGenerator
public abstract class BranchAndBound extends Object

Branch and Bound Execution Engine

An abstract base class that provides the core algorithmic framework for solving combinatorial optimization problems using the Branch and Bound paradigm.

This engine manages the state space tree explicitly using a custom priority queue (Heap) to implement a Best-First Search strategy. It actively tracks the global upper bound to prune sub-optimal branches systematically.

Author:
vicegd

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected Node
    bestNode
    The node representing the optimal valid configuration discovered during execution.
    protected int
    globalUpperBound
    The global upper bound metric used to prune paths mathematically incapable of yielding a better outcome than the currently discovered optimal solution.
    protected Heap
    nodeHeap
    The priority queue managing the active, unexplored nodes in the state space tree.
    protected Node
    rootNode
    The origin state of the problem.

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    branchAndBound(Node initialNode)
    Executes the primary 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 Heap nodeHeap
      The priority queue managing the active, unexplored nodes in the state space tree.

    • bestNode

      protected Node bestNode
      The node representing the optimal valid configuration discovered during execution.

    • rootNode

      protected Node rootNode
      The origin state of the problem.

    • globalUpperBound

      protected int globalUpperBound
      The global upper bound metric used to prune paths mathematically incapable of yielding a better outcome than the currently discovered optimal solution.

  • Constructor Details

    • BranchAndBound

      protected BranchAndBound()
      Initializes the fundamental memory structures required for the execution engine.

  • Method Details

    • branchAndBound

      public void branchAndBound(Node initialNode)
      Executes the primary Branch and Bound systemic loop.

      It continuously extracts the most promising state, expands its children, updates the optimal benchmark if a leaf solution is reached, and prunes branches that violate the bounding constraints.

      Parameters:
      initialNode - The starting mathematical state of the problem environment.

    • 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.