Package org.ddolib.ddo.core.mdd

Class LinkedDecisionDiagram<T>

java.lang.Object
org.ddolib.ddo.core.mdd.LinkedDecisionDiagram<T>
Type Parameters:
T - the type of state used in the problem modeled by this decision diagram
All Implemented Interfaces:
DecisionDiagram<T>
public final class LinkedDecisionDiagram<T> extends Object implements DecisionDiagram<T>
This class implements a decision diagram as a linked structure (linked MDD).

Each node in the diagram is represented by a Node object, and edges between nodes represent decisions made during the problem-solving process. This class supports the compilation of exact, relaxed, and restricted decision diagrams using various heuristics and dominance rules.

The main responsibilities of this class include:

  • Building the decision diagram layer by layer from an initial state.
  • Managing exact and relaxed cutsets of nodes.
  • Applying restrictions and relaxations to limit layer width.
  • Computing local bounds and fast lower bounds.
  • Exporting the decision diagram to DOT format for visualization.
  • Interfacing with caches to optimize repeated computations.

  • Constructor Summary

    Constructors
    Constructor
    Description
    LinkedDecisionDiagram(CompilationConfig<T> config)
    Creates a new linked decision diagram.

  • Method Summary

    Modifier and Type
    Method
    Description
    Optional<Set<Decision>>
    bestSolution()
    Returns the set of decisions representing the best solution found in this MDD.
    Optional<Double>
    bestValue()
    Returns the value of the best solution found in this decision diagram, if any.
    void
    compile()
    Compiles the decision diagram according to the configuration: Exact, relaxed, or restricted compilation type. Layer-wise variable ordering and heuristics. Application of relaxations or restrictions based on width limits. Construction of the DOT graph if export or debugging is enabled. Optional caching of thresholds for faster branch-and-bound computations.
    Iterator<SubProblem<T>>
    exactCutset()
    Returns an iterator over the nodes in the exact cutset, transformed into subproblems.
    String
    exportAsDot()
    Exports the compiled decision diagram in DOT format.
    boolean
    isExact()
    Returns whether the decision diagram is exact.
    double
    minLowerBound()
    Returns the minimum lower bound of expanded nodes of the MDD during the LNS compilation.
    boolean
    relaxedBestPathIsExact()
    Checks whether the best path found in a relaxed MDD consists entirely of exact nodes.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • LinkedDecisionDiagram

      public LinkedDecisionDiagram(CompilationConfig<T> config)
      Creates a new linked decision diagram.
      Parameters:
      config - The configuration object containing problem parameters, heuristics, relaxation operators, dominance checkers, and compilation settings.

  • Method Details

    • compile

      public void compile()
      Compiles the decision diagram according to the configuration:
      • Exact, relaxed, or restricted compilation type.
      • Layer-wise variable ordering and heuristics.
      • Application of relaxations or restrictions based on width limits.
      • Construction of the DOT graph if export or debugging is enabled.
      • Optional caching of thresholds for faster branch-and-bound computations.
      Specified by:
      compile in interface DecisionDiagram<T>

    • minLowerBound

      public double minLowerBound()
      Returns the minimum lower bound of expanded nodes of the MDD during the LNS compilation.
      Specified by:
      minLowerBound in interface DecisionDiagram<T>
      Returns:
      a double, minimum lower bound of expanded nodes of the MDD for the LNS.

    • isExact

      public boolean isExact()
      Returns whether the decision diagram is exact.
      Specified by:
      isExact in interface DecisionDiagram<T>
      Returns:
      true if the MDD is exact, false if relaxed/restricted nodes exist

    • bestValue

      public Optional<Double> bestValue()
      Returns the value of the best solution found in this decision diagram, if any.
      Specified by:
      bestValue in interface DecisionDiagram<T>
      Returns:
      an Optional containing the best value or empty if no solution exists

    • bestSolution

      public Optional<Set<Decision>> bestSolution()
      Returns the set of decisions representing the best solution found in this MDD.
      Specified by:
      bestSolution in interface DecisionDiagram<T>
      Returns:
      an Optional containing the set of decisions in the best solution, or empty if no solution exists

    • exactCutset

      public Iterator<SubProblem<T>> exactCutset()
      Returns an iterator over the nodes in the exact cutset, transformed into subproblems.
      Specified by:
      exactCutset in interface DecisionDiagram<T>
      Returns:
      iterator of subproblems in the exact cutset

    • relaxedBestPathIsExact

      public boolean relaxedBestPathIsExact()
      Checks whether the best path found in a relaxed MDD consists entirely of exact nodes.
      Specified by:
      relaxedBestPathIsExact in interface DecisionDiagram<T>
      Returns:
      true if the best path contains only exact nodes, false otherwise

    • exportAsDot

      public String exportAsDot()
      Exports the compiled decision diagram in DOT format.
      Specified by:
      exportAsDot in interface DecisionDiagram<T>
      Returns:
      a string containing the DOT representation of the MDD