Package org.ddolib.ddo.core.cache

Interface Cache<T>

Type Parameters:
T - the type representing the problem states stored in the cache
All Known Implementing Classes:
SimpleCache
public interface Cache<T>
Defines the abstraction of a cache mechanism used to prune and reduce the search space during the compilation or exploration of a Decision Diagram (DD).

The cache stores thresholds associated with subproblems encountered during the search. These thresholds represent bounds (on value or feasibility) that can be reused to avoid re-exploring equivalent or dominated states in subsequent iterations or at different depths of the DD.

By maintaining and comparing thresholds, the cache helps:

  • Prevent redundant computation on subproblems already explored with better or equivalent objective values.
  • Accelerate convergence of relaxed DDs by reusing partial results.
  • Reduce memory footprint by discarding obsolete layers.

This interface defines the operations required for cache initialization, lookup, update, and cleanup at various layers of the decision diagram.

See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    clear(int n)
    Clears cache data up to a specified depth.
    void
    clearLayer(int depth)
    Removes all thresholds associated with states at the specified depth.
    SimpleCache.Layer<T>
    getLayer(int depth)
    Retrieves the cache layer associated with the specified depth.
    Optional<Threshold>
    getThreshold(T state, int depth)
    Retrieves the threshold currently associated with a given state and depth.
    void
    initialize(Problem<T> problem)
    Initializes the cache for use with the specified problem instance.
    default boolean
    mustExplore(SubProblem<T> subproblem, int depth)
    Determines whether the given subproblem must still be explored, based on the information currently stored in the cache.
    void
    updateThreshold(T state, int depth, Threshold threshold)
    Updates the threshold associated with a given state at a given depth.

  • Method Details

    • mustExplore

      default boolean mustExplore(SubProblem<T> subproblem, int depth)
      Determines whether the given subproblem must still be explored, based on the information currently stored in the cache.

      This method checks if there exists a Threshold in the cache associated with the same state and depth. If such a threshold exists and its stored value is better or equal than the subproblem’s current value, the subproblem may be safely skipped.

      Parameters:
      subproblem - the subproblem being considered for expansion in the DD
      depth - the current depth (layer index) in the DD
      Returns:
      true if the subproblem should still be explored; false if it can be pruned using cached thresholds

    • initialize

      void initialize(Problem<T> problem)
      Initializes the cache for use with the specified problem instance.

      This method is typically called once before the DD compilation begins. It prepares the internal data structures to store thresholds for the given problem states and layers.

      Parameters:
      problem - the problem instance for which the cache will be used

    • getLayer

      SimpleCache.Layer<T> getLayer(int depth)
      Retrieves the cache layer associated with the specified depth.

      Each layer maintains the thresholds of all states encountered at a specific depth of the decision diagram.

      Parameters:
      depth - the depth (layer index) of the DD
      Returns:
      the SimpleCache.Layer object containing thresholds for the specified layer

    • getThreshold

      Optional<Threshold> getThreshold(T state, int depth)
      Retrieves the threshold currently associated with a given state and depth.
      Parameters:
      state - the state whose threshold is being requested
      depth - the depth (layer) where the state resides
      Returns:
      an Optional containing the corresponding Threshold if present, or an empty Optional otherwise

    • updateThreshold

      void updateThreshold(T state, int depth, Threshold threshold)
      Updates the threshold associated with a given state at a given depth.

      The threshold is updated only if the new value is an improvement (e.g., higher for maximization or lower for minimization problems) over the one currently stored in the cache.

      Parameters:
      state - the state whose threshold is to be updated
      depth - the depth (layer index) in the DD
      threshold - the new threshold to associate with the state

    • clearLayer

      void clearLayer(int depth)
      Removes all thresholds associated with states at the specified depth.

      This operation is useful to reclaim memory once a DD layer has been fully processed or when restarting a computation from a specific level.

      Parameters:
      depth - the depth (layer index) to clear

    • clear

      void clear(int n)
      Clears cache data up to a specified depth.

      This operation removes cached thresholds from the beginning of the DD up to (and possibly including) the specified layer index, depending on the implementation.

      Parameters:
      n - the depth up to which to clear the cache