Package org.ddolib.ddo.core.mdd

Interface DecisionDiagram<T>

Type Parameters:
T - the type representing the problem state at a given layer in the diagram
All Known Implementing Classes:
LinkedDecisionDiagram
public interface DecisionDiagram<T>
Defines the abstraction of a reusable Decision Diagram (DD) used to model and solve combinatorial optimization problems.

A decision diagram is a layered graph-based representation of the solution space of a problem. Depending on how it is compiled, the DD can be:

  • Exact — representing all feasible solutions of the original problem (no relaxation);
  • Relaxed — merging nodes to reduce the diagram width, potentially omitting some constraints while preserving valid lower or upper bounds on the optimal value.

This interface defines the basic operations available on a compiled DD, including: triggering compilation, accessing the best value or solution, iterating over nodes in the cutset, and exporting the structure for visualization.

  • Method Summary

    Modifier and Type
    Method
    Description
    Optional<Set<Decision>>
    bestSolution()
    Returns the sequence of decisions leading to the best solution represented in this DD.
    Optional<Double>
    bestValue()
    Returns the value of the best solution represented in this decision diagram, if it exists.
    void
    compile()
    Triggers the compilation of the decision diagram according to the configuration parameters provided by the user (e.g., width, relaxation, variable heuristic, etc.).
    Iterator<SubProblem<T>>
    exactCutset()
    Provides an iterator over the nodes belonging to the exact cutset of the diagram.
    String
    exportAsDot()
    Exports the compiled decision diagram as a Graphviz-compatible DOT formatted string.
    boolean
    isExact()
    Indicates whether the compiled decision diagram is exact.
    double
    minLowerBound()
     
    boolean
    relaxedBestPathIsExact()
    Checks whether the best path found in the relaxed decision diagram is exact.

  • Method Details

    • compile

      void compile()
      Triggers the compilation of the decision diagram according to the configuration parameters provided by the user (e.g., width, relaxation, variable heuristic, etc.).

      The compilation builds the layered graph structure that encodes the feasible (or relaxed) state space of the problem. Depending on the configuration, this process may yield either an exact or a relaxed DD.

    • isExact

      boolean isExact()
      Indicates whether the compiled decision diagram is exact.

      An exact DD represents the full solution space of the original problem, meaning that the best path in the DD corresponds exactly to the true optimal solution.

      Returns:
      true if the compiled DD is exact; false if it is relaxed

    • bestValue

      Optional<Double> bestValue()
      Returns the value of the best solution represented in this decision diagram, if it exists.

      For a relaxed DD, this corresponds to a bound (lower or upper depending on the problem formulation). For an exact DD, it is the exact optimal value.

      Returns:
      an Optional containing the best objective value, or an empty Optional if no solution is available

    • bestSolution

      Optional<Set<Decision>> bestSolution()
      Returns the sequence of decisions leading to the best solution represented in this DD.

      The returned solution corresponds to the path in the diagram that achieves the best (lowest or highest) objective value. If the DD is relaxed, the returned set may not correspond to a fully feasible solution.

      Returns:
      an Optional containing the set of Decision objects defining the best solution, or an empty Optional if none exists

    • exactCutset

      Iterator<SubProblem<T>> exactCutset()
      Provides an iterator over the nodes belonging to the exact cutset of the diagram.

      The exact cutset is the set of subproblems (nodes) that exactly represent the state space at a specific layer, usually the last layer before relaxation or completion. It can be used to guide recomputation, heuristic extensions, or incremental compilation.

      Returns:
      an Iterator over the SubProblem elements forming the exact cutset

    • relaxedBestPathIsExact

      boolean relaxedBestPathIsExact()
      Checks whether the best path found in the relaxed decision diagram is exact.

      This can occur when the relaxation did not alter the structure along the optimal path, meaning the computed best value is equal to the true optimum even though the DD is relaxed.

      Returns:
      true if the relaxed best path corresponds to an exact feasible solution; false otherwise

    • exportAsDot

      String exportAsDot()
      Exports the compiled decision diagram as a Graphviz-compatible DOT formatted string.

      This method is typically used for visualization or debugging purposes. The resulting DOT string can be rendered using Graphviz tools (e.g., dot, neato, or web-based renderers).

      Returns:
      a String containing the DOT representation of the compiled decision diagram

    • minLowerBound

      double minLowerBound()