Package org.ddolib.modeling

Interface DdoModel<T>

Type Parameters:
T - the state type
All Superinterfaces:
Model<T>
All Known Implementing Classes:
ExactModel
public interface DdoModel<T> extends Model<T>
Defines the interface for a Dynamic Decision Diagram Optimization (DDO) model.

A DdoModel extends the generic Model interface by providing methods related to relaxation, ranking, width control, and frontier management. It serves as the foundation for implementing algorithms that construct and explore decision diagrams dynamically (e.g., exact or approximate methods).

This interface provides several default behaviors, which can be overridden to customize model evaluation, search strategy, or diagram generation.

Responsibilities

  • Provide the problem relaxation used for node evaluation (relaxation()).
  • Define the ranking strategy between states (ranking()).
  • Control the diagram’s width through heuristics (widthHeuristic()).
  • Specify how to maintain and update the frontier (frontier()).
  • Indicate optional behaviors like caching (useCache()) or exporting the structure (exportDot()).

  • Method Details

    • relaxation

      Relaxation<T> relaxation()
      Returns the relaxation of the model used to evaluate the nodes or layers of the decision diagram.

      The relaxation defines a simplified or approximate version of the problem, which helps bound the objective function or guide the search.

      Returns:
      the Relaxation object associated with this model

    • ranking

      default StateRanking<T> ranking()
      Returns the ranking function used to order states within a layer.

      The default implementation imposes no specific order (always returns 0), meaning all states are considered equal in priority. Override this method to implement problem-specific ranking heuristics.

      Returns:
      a StateRanking comparator between states

    • widthHeuristic

      default WidthHeuristic<T> widthHeuristic()
      Returns the width heuristic controlling the maximum number of nodes per layer.

      The default implementation uses a fixed width of 10.

      Returns:
      a WidthHeuristic instance controlling diagram width

    • frontier

      default Frontier<T> frontier()
      Returns the frontier management strategy used to store and expand the current layer of the decision diagram.

      The default implementation creates a SimpleFrontier based on ranking() and uses CutSetType.LastExactLayer as the cut set.

      Returns:
      a Frontier instance defining the search frontier

    • useCache

      default boolean useCache()
      Indicates whether caching should be used during the diagram construction.

      Caching stores intermediate results to avoid redundant computations. By default, caching is disabled.

      Returns:
      true if caching is enabled, false otherwise

    • exportDot

      default boolean exportDot()
      Indicates whether the generated decision diagram should be exported to a DOT file (Graphviz format).

      This feature allows visualization of the structure of the generated decision diagram for debugging or analysis purposes. By default, export is disabled.

      Returns:
      true if DOT export is enabled, false otherwise

    • relaxStrategy

      default ReductionStrategy<T> relaxStrategy()
      Strategy to select which nodes should be merged together on a relaxed DD.

    • restrictStrategy

      default ReductionStrategy<T> restrictStrategy()
      Strategy to select which nodes should be dropped on a restricted DD.

    • stateDistance

      default StateDistance<T> stateDistance()

    • useLNS

      default boolean useLNS()

    • fixWidth

      default DdoModel<T> fixWidth(int width)
      Returns a copy of this model but with a fixed width.
      Parameters:
      width - The maximum width of the diagram.
      Returns:
      A copy of this model but with a fixed width.

    • setCutSetType

      default DdoModel<T> setCutSetType(CutSetType type)
      Returns a copy of this model by changing the CutSetType.
      Parameters:
      type - The new cutset type.
      Returns:
      A copy of this model by changing the CutSetType.

    • useCache

      default DdoModel<T> useCache(boolean b)
      Returns a copy of this model by enabling or disabling the cache.
      Parameters:
      b - Whether the cache must be used.
      Returns:
      A copy of this model by enabling or disabling the cache.

    • disableDominance

      default DdoModel<T> disableDominance()
      Description copied from interface: Model
      Returns a copy of this model but without dominance.
      Specified by:
      disableDominance in interface Model<T>
      Returns:
      A copy of this model but without dominance.

    • disableLowerBound

      default DdoModel<T> disableLowerBound()
      Description copied from interface: Model
      Returns a copy of this model but without FastLowerBound.
      Specified by:
      disableLowerBound in interface Model<T>
      Returns:
      A copy of this model but without FastLowerBound.

    • toExactModel

      default ExactModel<T> toExactModel()
      Convert this model into a model for the exact solver.
      Returns:
      a model usable by an ExactModel