Package org.ddolib.ddo.core.frontier

Interface Frontier<T>

Type Parameters:
T - the type representing the problem state stored in each SubProblem
All Known Implementing Classes:
SimpleFrontier
public interface Frontier<T>
Defines the abstraction of a frontier (or open list) used by solvers to manage and prioritize the remaining subproblems that must be explored.

In a Decision Diagram (DD) or branch-and-bound framework, the frontier represents the set of active subproblems—those that have been generated but not yet expanded or solved. Each subproblem corresponds to a node in the search or DD exploration tree.

Implementations of this interface define how the solver selects the next node to explore. The typical behavior is to always extract the most promising node (the one with the highest bound on the objective function) to maximize pruning efficiency.

Contract:

  • Nodes (subproblems) are pushed into the frontier using push(SubProblem).
  • Nodes are extracted in descending order of upper bound value using pop().
  • Implementations must maintain this priority invariant to ensure correct solver behavior.
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    double
    bestInFrontier()
    Returns the current best upper bound among all subproblems stored in the frontier.
    void
    clear()
    Removes all subproblems currently stored in the frontier.
    CutSetType
    cutSetType()
    Returns the type of cut set associated with this frontier.
    default boolean
    isEmpty()
    Checks whether the frontier is empty.
    SubProblem<T>
    pop()
    Extracts and returns the most promising subproblem from the frontier.
    void
    push(SubProblem<T> sub)
    Adds a new subproblem to the frontier for future exploration.
    int
    size()
    Returns the number of subproblems currently stored in the frontier.

  • Method Details

    • push

      void push(SubProblem<T> sub)
      Adds a new subproblem to the frontier for future exploration.

      This method inserts a node into the internal priority structure of the frontier (e.g., a priority queue ordered by the subproblem’s upper bound or heuristic value).

      Parameters:
      sub - the subproblem to be added to the frontier

    • pop

      SubProblem<T> pop()
      Extracts and returns the most promising subproblem from the frontier.

      The solver assumes that subproblems are popped in descending order of upper bound, i.e., the node with the best potential objective value should be returned first.

      If the frontier is empty, this method may return null.

      Returns:
      the subproblem with the highest priority in the frontier, or null if empty

    • clear

      void clear()
      Removes all subproblems currently stored in the frontier.

      This operation resets the internal structure and is typically used when restarting a search or reinitializing the solver.

    • size

      int size()
      Returns the number of subproblems currently stored in the frontier.
      Returns:
      the number of nodes in the frontier

    • cutSetType

      CutSetType cutSetType()
      Returns the type of cut set associated with this frontier.

      The cut set type determines the strategy used to define which nodes belong to the frontier (e.g., CutSetType.LastExactLayer or CutSetType.Frontier). This affects how the solver manages layers during compilation.

      Returns:
      the CutSetType representing the frontier strategy

    • isEmpty

      default boolean isEmpty()
      Checks whether the frontier is empty.

      This default implementation returns true if size() is zero.

      Returns:
      true if the frontier contains no subproblems; false otherwise

    • bestInFrontier

      double bestInFrontier()
      Returns the current best upper bound among all subproblems stored in the frontier.

      The "best" bound depends on the problem type (e.g., maximum upper bound for minimization problems). This method is generally used by the solver to monitor convergence or update global bounds.

      Note: Implementations should throw an exception if this method is called when the frontier is empty.

      Returns:
      the best upper bound value among subproblems in the frontier
      Throws:
      IllegalStateException - if the frontier is empty