Package org.ddolib.ddo.core

Class SubProblem<T>

java.lang.Object
org.ddolib.ddo.core.SubProblem<T>
Type Parameters:
T - the type representing the state of the problem
public final class SubProblem<T> extends Object
Represents a residual optimization problem (subproblem) derived from the decomposition of an original problem during the compilation or search process.

A SubProblem corresponds to a portion of the global problem that must be solved in order to complete the resolution of the original optimization task. Subproblems are typically created from nodes located in the exact cutsets of relaxed decision diagrams and encapsulate the remaining computation required from that point onward.

Each subproblem maintains:

  • The current state of the problem at its root,
  • The cumulative objective value up to that state,
  • A lower bound lb estimating the best achievable value below it, and
  • The path of decisions taken to reach this subproblem.
These attributes allow the solver to estimate, compare, and prioritize subproblems when exploring the decision space.

  • Constructor Summary

    Constructors
    Constructor
    Description
    SubProblem(T state, double value, double lb, Set<Decision> path)
    Constructs a new SubProblem instance with its associated state, accumulated value, lower bound, and decision path.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    equals(Object obj)
    Compares this subproblem to another for equality.
    double
    f()
    Computes and returns the f-value of this subproblem, defined as the sum of its current objective value and its lower bound.
    int
    getDepth()
    Returns the depth of this subproblem, corresponding to the number of decisions taken from the root to reach it.
    double
    getLowerBound()
    Returns the lower bound on the global objective that can be achieved by solving the remainder of the problem through this subproblem.
    Set<Decision>
    getPath()
    Returns the path (partial assignment) of decisions that led to this subproblem.
    T
    getState()
    Returns the root state associated with this subproblem.
    double
    getValue()
    Returns the cumulative objective value at the root of this subproblem.
    int
    hashCode()
    Returns the hash code of this subproblem, derived from its root state.
    String
    statistics()
    Returns a string summarizing key statistics about this subproblem, including its objective value, lower bound, and depth in the decision diagram.
    String
    toString()
    Returns a human-readable representation of this subproblem, including its value, lower bound, f-value, depth, and state.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • SubProblem

      public SubProblem(T state, double value, double lb, Set<Decision> path)
      Constructs a new SubProblem instance with its associated state, accumulated value, lower bound, and decision path.
      Parameters:
      state - the root state of this subproblem
      value - the objective value corresponding to the longest path reaching this subproblem
      lb - a lower bound on the optimal value reachable when solving through this subproblem
      path - the sequence of decisions (partial assignment) leading from the root to this subproblem

  • Method Details

    • getDepth

      public int getDepth()
      Returns the depth of this subproblem, corresponding to the number of decisions taken from the root to reach it.
      Returns:
      the depth of the subproblem

    • getState

      public T getState()
      Returns the root state associated with this subproblem.
      Returns:
      the root state

    • getValue

      public double getValue()
      Returns the cumulative objective value at the root of this subproblem.
      Returns:
      the current objective value

    • getLowerBound

      public double getLowerBound()
      Returns the lower bound on the global objective that can be achieved by solving the remainder of the problem through this subproblem.
      Returns:
      the lower bound on the objective

    • f

      public double f()
      Computes and returns the f-value of this subproblem, defined as the sum of its current objective value and its lower bound.

      This metric is often used to prioritize subproblems in branch-and-bound or decision diagram exploration.

      Returns:
      the f-value (value + lower bound) of this subproblem

    • getPath

      public Set<Decision> getPath()
      Returns the path (partial assignment) of decisions that led to this subproblem.
      Returns:
      the set of decisions representing the path

    • statistics

      public String statistics()
      Returns a string summarizing key statistics about this subproblem, including its objective value, lower bound, and depth in the decision diagram.
      Returns:
      a formatted string of subproblem statistics

    • hashCode

      public int hashCode()
      Returns the hash code of this subproblem, derived from its root state.
      Overrides:
      hashCode in class Object
      Returns:
      the hash code

    • equals

      public boolean equals(Object obj)
      Compares this subproblem to another for equality. Two subproblems are considered equal if they share the same root state.
      Overrides:
      equals in class Object
      Parameters:
      obj - the object to compare with
      Returns:
      true if both subproblems have the same state, false otherwise

    • toString

      public String toString()
      Returns a human-readable representation of this subproblem, including its value, lower bound, f-value, depth, and state.
      Overrides:
      toString in class Object
      Returns:
      a formatted string describing this subproblem