Package org.ddolib.acs.core.solver

Class ACSSolver<T>

java.lang.Object

org.ddolib.acs.core.solver.ACSSolver<T>

Type Parameters:

T - The type representing a state in the problem.

All Implemented Interfaces:

Solver

public final class ACSSolver<T>
extends Object
implements Solver

Implementation of an Anytime Column Search (ACS) solver for decision diagram-based optimization problems.

The solver uses a combination of a lower bound, dominance rules, and variable heuristics to explore the search space efficiently. It maintains open and closed lists of subproblems organized by depth (columns) and attempts to minimize the objective function while keeping track of the best known solution (incumbent).

Features:

• Maintains a frontier of subproblems using a priority queue at each column.
• Applies a FastLowerBound to prune subproblems unlikely to improve the incumbent.
• Optionally uses DominanceChecker to avoid exploring dominated states.
• Supports variable selection heuristics through VariableHeuristic.
• Can report search statistics and provide the best solution found at any time.

See Also:

• Solver
• Problem
• FastLowerBound
• VariableHeuristic
• DominanceChecker
• AcsModel

Constructor Summary

Constructors

Constructor	Description
ACSSolver(AcsModel<T> model)	Constructs an ACS solver with all required and optional components provided via an AcsModel.

Method Summary

Modifier and Type	Method	Description
Optional<Set<Decision>>	bestSolution()	Returns the set of decisions corresponding to the best solution found, if any.
Optional<Double>	bestValue()	Returns the value of the best solution found, if any.
Solution	minimize(Predicate<SearchStatistics> limit, BiConsumer<int[],SearchStatistics> onSolution)	Minimizes the problem using the ACS strategy.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.ddolib.common.solver.Solver

constructSolution

Constructor Details

ACSSolver

public ACSSolver(AcsModel<T> model)

Constructs an ACS solver with all required and optional components provided via an AcsModel.

Mandatory parameters:

• Problem implementation
• FastLowerBound implementation
• VariableHeuristic implementation

Optional parameters:

• DominanceChecker implementation
• VerbosityLevel for debug/logging

Parameters:

model - Provides all parameters needed to configure the solver

Method Details

minimize

public Solution minimize(Predicate<SearchStatistics> limit,
 BiConsumer<int[],SearchStatistics> onSolution)

Minimizes the problem using the ACS strategy.

Specified by:

minimize in interface Solver

Parameters:

limit - a predicate to stop the search based on current SearchStatistics

onSolution - a consumer invoked on each new solution found (solution array and statistics)

Returns:

final SearchStatistics of the search

bestValue

public Optional<Double> bestValue()

Returns the value of the best solution found, if any.

Specified by:

bestValue in interface Solver

Returns:

Optional containing the value of the best solution or empty if none found

bestSolution

public Optional<Set<Decision>> bestSolution()

Returns the set of decisions corresponding to the best solution found, if any.

Specified by:

bestSolution in interface Solver

Returns:

Optional containing the set of Decision objects or empty if none found