Package org.ddolib.ddo.core.solver

Class ExactSolver<T>

java.lang.Object
org.ddolib.ddo.core.solver.ExactSolver<T>
Type Parameters:
T - the type of state used by the problem
All Implemented Interfaces:
Solver
public final class ExactSolver<T> extends Object implements Solver
Solver that compiles a single exact decision diagram (MDD) to find the optimal solution.

Warning: Using only exact MDDs can consume a significant amount of memory. It is recommended to use this solver for small instances or for testing your model. For larger instances or more advanced strategies, consider using SequentialSolver.

This solver constructs the MDD in a single pass:

  • Initializes the root subproblem from the initial state.
  • Compiles the MDD using exact node expansion without any width restriction.
  • Optionally uses dominance rules and caching to prune redundant subproblems.
  • Extracts the best solution and value from the compiled MDD.
  • Can export the MDD in DOT format if enabled.

  • Constructor Details

    • ExactSolver

      public ExactSolver(ExactModel<T> model)
      Creates a fully-configured ExactSolver instance.
      Parameters:
      model - The DdoModel containing all necessary parameters and heuristics to configure the solver, including the problem, relaxation, ranking, variable heuristic, lower bound, dominance checker, caching, and verbosity settings.

  • Method Details

    • minimize

      public Solution minimize(Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)
      Minimizes the problem by compiling an exact decision diagram (MDD).

      The method performs the following steps:

      • Initializes the root subproblem with the initial state.
      • Configures the compilation parameters for an exact MDD.
      • Compiles the MDD and optionally prunes using dominance and caching.
      • Extracts the best solution and value.
      • Optionally exports the MDD in DOT format.
      Specified by:
      minimize in interface Solver
      Parameters:
      limit - a predicate that may be used to limit the search based on statistics
      onSolution - a callback invoked when a solution is found
      Returns:
      statistics about the search process, including the best value found

    • bestValue

      public Optional<Double> bestValue()
      Returns the value of the best solution found so far.
      Specified by:
      bestValue in interface Solver
      Returns:
      an Optional containing the best solution value or empty if none was found

    • bestSolution

      public Optional<Set<Decision>> bestSolution()
      Returns the best solution found so far as a set of decisions.
      Specified by:
      bestSolution in interface Solver
      Returns:
      an Optional containing the best solution or empty if none was found