Package org.ddolib.ddo.core.solver

Class SequentialSolver<T>

java.lang.Object
org.ddolib.ddo.core.solver.SequentialSolver<T>
Type Parameters:
T - The type representing a problem state.
All Implemented Interfaces:
Solver
public final class SequentialSolver<T> extends Object implements Solver
A sequential implementation of a Branch-and-Bound solver based on Multi-valued Decision Diagrams (MDDs).

This solver follows the vanilla version of the algorithm introduced in lecture. It explores subproblems sequentially (one at a time), combining restricted and relaxed MDD compilations to progressively tighten the upper and lower bounds of the optimization problem.

The solver maintains a frontier (priority queue) of unexplored subproblems, ordered by their lower bounds, and stops as soon as the optimality condition is met (i.e., when the best known upper bound is equal to the minimum lower bound in the frontier).

Key ideas:

  • Each subproblem corresponds to a partial decision sequence and a state.
  • The solver compiles a restricted MDD to approximate the feasible region and update the current best solution (upper bound).
  • It then compiles a relaxed MDD to estimate lower bounds and determine which subproblems should be explored next.
  • Subproblems are pruned if their lower bounds exceed the current best solution (upper bound), or if they are dominated according to the provided DominanceChecker.

This sequential solver serves as a reference or baseline implementation.

Usage Notes:

  • This solver is designed for correctness and clarity, not scalability.
  • It is best suited for debugging, small instances, and educational purposes.
  • Set the verbosity level in DdoModel for detailed runtime logging.
See Also:

  • Constructor Details

    • SequentialSolver

      public SequentialSolver(DdoModel<T> model)
      Creates a fully qualified instance. The parameters of this solver are given via a DdoModel
      Parameters:
      model - All the parameters needed to configure the solver.

  • Method Details

    • minimize

      public Solution minimize(Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)
      Description copied from interface: Solver
      Minimizes the objective function according to the solver strategy.
      Specified by:
      minimize in interface Solver
      Parameters:
      limit - a Predicate that can limit or stop the search based on current SearchStatistics
      onSolution - a BiConsumer invoked on each new solution found; receives the solution array and current statistics
      Returns:
      the statistics of the search after completion

    • bestValue

      public Optional<Double> bestValue()
      Specified by:
      bestValue in interface Solver
      Returns:
      the value of the best solution in this decision diagram if there is one

    • bestSolution

      public Optional<Set<Decision>> bestSolution()
      Description copied from interface: Solver
      Returns the set of decisions that lead to the best solution found by this solver, if any.
      Specified by:
      bestSolution in interface Solver
      Returns:
      an Optional containing the set of Decision objects representing the best solution, or empty if no solution exists