Package org.ddolib.modeling

Class Solvers

java.lang.Object
org.ddolib.modeling.Solvers
public class Solvers extends Object
The Solvers class acts as a unified entry point for running different optimization algorithms within the Decision Diagram Optimization (DDO) framework.

It provides static methods to solve problems using various strategies:

  • DDO (Decision Diagram Optimization) — Builds restricted or relaxed decision diagrams layer by layer to approximate or find exact solutions.
  • A* — Uses a best-first search guided by an admissible lower bound heuristic to guarantee optimality.
  • ACS (Anytime Column Search) — An iterative improvement algorithm that progressively refines solutions over time using bounded-width decision diagrams.
  • Anytime Weighted A* - A variant of A* algorithm that progressively refines solution using a weighted heuristic function.
See Also:

  • Constructor Details

    • Solvers

      public Solvers()

  • Method Details

    • minimizeDdo

      public static <T> Solution minimizeDdo(DdoModel<T> model)
      Solves the given model using the DDO (Decision Diagram Optimization) algorithm with default stopping criteria and no solution callback.
      Parameters:
      model - the DDO model to solve
      Returns:
      a solution to the related problem with search statistics summarizing the solver's performance

    • minimizeDdo

      public static <T> Solution minimizeDdo(DdoModel<T> model, Predicate<SearchStatistics> limit)
      Solves the given model using DDO, stopping when the provided limit condition becomes true.
      Parameters:
      model - the DDO model to solve
      limit - a predicate defining the stopping criterion (e.g., max iterations, time limit)
      Returns:
      a solution to the related problem with search statistics summarizing the solver's performance

    • minimizeDdo

      public static <T> Solution minimizeDdo(DdoModel<T> model, BiConsumer<int[],SearchStatistics> onSolution)
      Solves the given model using DDO and triggers a callback each time a new incumbent solution is found.
      Parameters:
      model - the DDO model to solve
      onSolution - callback executed when a new best solution is discovered
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeDdo

      public static <T> Solution minimizeDdo(DdoModel<T> model, Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)
      Core method for solving a DDO model with a custom stop condition and a solution callback.

      It automatically builds the solver configuration from the given model and delegates the actual solving to a SequentialSolver.

      Parameters:
      model - the DDO model to solve
      limit - a predicate defining when the solver should stop
      onSolution - a callback invoked whenever a new best solution is found
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • relaxedDdo

      public static <T> Solution relaxedDdo(DdoModel<T> model)

    • relaxedDdo

      public static <T> Solution relaxedDdo(DdoModel<T> model, Predicate<SearchStatistics> limit)

    • relaxedDdo

      public static <T> Solution relaxedDdo(DdoModel<T> model, BiConsumer<int[],SearchStatistics> onSolution)

    • relaxedDdo

      public static <T> Solution relaxedDdo(DdoModel<T> model, Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)

    • restrictedDdo

      public static <T> Solution restrictedDdo(DdoModel<T> model)

    • restrictedDdo

      public static <T> Solution restrictedDdo(DdoModel<T> model, Predicate<SearchStatistics> limit)

    • restrictedDdo

      public static <T> Solution restrictedDdo(DdoModel<T> model, BiConsumer<int[],SearchStatistics> onSolution)

    • restrictedDdo

      public static <T> Solution restrictedDdo(DdoModel<T> model, Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)

    • minimizeAstar

      public static <T> Solution minimizeAstar(Model<T> model)
      Solves the given model using the A* search algorithm with default parameters.
      Parameters:
      model - the model to solve
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAstar

      public static <T> Solution minimizeAstar(Model<T> model, Predicate<SearchStatistics> limit)
      Solves the given model using A* with a specified stop condition.
      Parameters:
      model - the model to solve
      limit - predicate defining the termination condition
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAstar

      public static <T> Solution minimizeAstar(Model<T> model, BiConsumer<int[],SearchStatistics> onSolution)
      Solves the given model using A* and calls back when new incumbent solutions are found.
      Parameters:
      model - the model to solve
      onSolution - callback triggered for each new best solution
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAstar

      public static <T> Solution minimizeAstar(Model<T> model, Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)
      Core method for solving a model with the A* search algorithm, with custom limit and callback.
      Parameters:
      model - the model to solve
      limit - stopping condition for the search
      onSolution - callback invoked when a new best solution is found
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAcs

      public static <T> Solution minimizeAcs(AcsModel<T> model)
      Solves the given model using the Anytime Column Search (ACS) algorithm.
      Parameters:
      model - the ACS model to solve
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAcs

      public static <T> Solution minimizeAcs(AcsModel<T> model, Predicate<SearchStatistics> limit)
      Solves the given model using ACS, stopping when the limit condition is satisfied.
      Parameters:
      model - the ACS model to solve
      limit - predicate defining the stopping criterion
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAcs

      public static <T> Solution minimizeAcs(AcsModel<T> model, BiConsumer<int[],SearchStatistics> onSolution)
      Solves the given model using ACS and calls the callback when a new incumbent is found.
      Parameters:
      model - the ACS model to solve
      onSolution - callback executed on discovery of a new best solution
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAcs

      public static <T> Solution minimizeAcs(AcsModel<T> model, Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)
      Core method for solving an ACS model with custom stopping condition and solution callback.

      The method configures and delegates the solving process to an ACSSolver.

      Parameters:
      model - the ACS model to solve
      limit - predicate defining the stopping condition
      onSolution - callback invoked when new incumbent solutions are found
      Returns:
      sa solution to the related problem with search statistics summarizing solver's performance

    • minimizeAwAStar

      public static <T> Solution minimizeAwAStar(AwAstarModel<T> model, Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)
      Core method for solving a model with the Anytime Weighted A* search algorithm, with custom limit and callback.
      Parameters:
      model - the model to solve
      limit - stopping condition for the search
      onSolution - callback invoked when a new best solution is found
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAwAStar

      public static <T> Solution minimizeAwAStar(AwAstarModel<T> model)
      Solves the given model using the Anytime Weighted A* (AWA*) algorithm.
      Parameters:
      model - the AWA* model to solve
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAwAStar

      public static <T> Solution minimizeAwAStar(AwAstarModel<T> model, Predicate<SearchStatistics> limit)
      Solves the given model using AWA*, stopping when the limit condition is satisfied.
      Parameters:
      model - the AWA* model to solve
      limit - predicate defining the stopping criterion
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeAwAStar

      public static <T> Solution minimizeAwAStar(AwAstarModel<T> model, BiConsumer<int[],SearchStatistics> onSolution)
      Solves the given model using AWA* and calls the callback when a new incumbent is found.
      Parameters:
      model - the AWA* model to solve
      onSolution - callback executed on discovery of a new best solution
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeExact

      public static <T> Solution minimizeExact(ExactModel<T> model)
      Solves the given model using the Exact DDO algorithm.

      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 minimizeDdo(DdoModel).

      Parameters:
      model - the DDO model to solve
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeExact

      public static <T> Solution minimizeExact(ExactModel<T> model, BiConsumer<int[],SearchStatistics> onSolution)
      Core method for solving an DDO model with solution callback.

      The method configures and delegates the solving process to an ExactSolver.

      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 minimizeDdo(DdoModel, Predicate, BiConsumer) )}.

      Parameters:
      model - the DDO model to solve
      onSolution - callback invoked when new incumbent solutions are found
      Returns:
      a solution to the related problem with search statistics summarizing solver's performance

    • minimizeLns

      public static final <T> Solution minimizeLns(LnsModel<T> model, Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)
      Runs a Large Neighborhood Search (LNS) on the specified model with a given termination condition and a callback for each solution found.
      Type Parameters:
      T - the type of state used in the problem
      Parameters:
      model - the LnsModel describing the problem and search heuristics
      limit - a Predicate on SearchStatistics defining when to stop the search. The search stops when limit.test(stats) returns true.
      onSolution - a BiConsumer called each time a new solution is found. The first argument is the solution (array of variable assignments), and the second argument is the current search statistics.
      Returns:
      the best Solution found during the search

    • minimizeLns

      public static <T> Solution minimizeLns(LnsModel<T> model, BiConsumer<int[],SearchStatistics> onSolution)
      Runs a Large Neighborhood Search (LNS) on the specified model without any termination condition and without processing intermediate solutions.

      Equivalent to calling minimizeLns(LnsModel, Predicate, BiConsumer) with limit always false and an empty callback.

      Type Parameters:
      T - the type of state used in the problem
      Parameters:
      model - the LnsModel describing the problem and search heuristics
      onSolution - a BiConsumer called for each solution found (can be ignored)
      Returns:
      the best Solution found during the search

    • minimizeLns

      public static <T> Solution minimizeLns(LnsModel<T> model, Predicate<SearchStatistics> limit)
      Runs a Large Neighborhood Search (LNS) on the specified model with a termination condition but without processing intermediate solutions.

      Equivalent to calling minimizeLns(LnsModel, Predicate, BiConsumer) with the given limit and an empty callback.

      Type Parameters:
      T - the type of state used in the problem
      Parameters:
      model - the LnsModel describing the problem and search heuristics
      limit - a Predicate on SearchStatistics defining when to stop the search
      Returns:
      the best Solution found during the search