Package org.ddolib.modeling

Interface LnsModel<T>

Type Parameters:
T - the type of state used in the problem
All Superinterfaces:
Model<T>
public interface LnsModel<T> extends Model<T>
Interface representing a model for Large Neighborhood Search (LNS) problems.

This interface extends Model and provides default implementations and configuration options specifically for LNS-based search algorithms.

Key responsibilities of an LnsModel include:

  • Providing the underlying Problem instance.
  • Specifying a FastLowerBound for efficient lower bound estimation.
  • Optionally providing a DominanceChecker to prune dominated states.
  • Providing heuristics such as StateRanking and WidthHeuristic to guide search.
  • Supporting optional configuration of LNS parameters like initial solution, destruction probability, and width.

Default implementations:

Configuration methods allow creating modified copies of the model with custom parameters:

Example usage:

 LnsModel model = new MyLnsModel()
     .fixWidth(20)
     .setInitialSolution(mySolution)
     .setProbability(0.3);

This interface is intended for use with Solvers.minimizeLns(LnsModel, java.util.function.Predicate, java.util.function.BiConsumer) or similar LNS solvers.

  • Method Details

    • ranking

      default StateRanking<T> ranking()
      Returns the state ranking heuristic used to guide the search. Default implementation returns a neutral ranking (all states equal).
      Returns:
      the state ranking

    • widthHeuristic

      default WidthHeuristic<T> widthHeuristic()
      Returns the width heuristic used for tree exploration. Default is FixedWidth with width 10.
      Returns:
      the width heuristic

    • exportDot

      default boolean exportDot()
      Indicates whether to export the search tree to DOT format. Default is false.
      Returns:
      true if DOT export is enabled, false otherwise

    • restrictStrategy

      default ReductionStrategy<T> restrictStrategy()
      Returns the strategy used to restrict the search neighborhood.
      Returns:
      the reduction strategy

    • stateDistance

      default StateDistance<T> stateDistance()
      Returns a measure of distance between two states. Default returns 0 for all states.
      Returns:
      the state distance

    • initialSolution

      default int[] initialSolution()
      Returns the initial solution to start the search from. Default is null (no initial solution).
      Returns:
      the initial solution as an array of variable assignments

    • probability

      default double probability()
      Returns the probability used to destruct parts of the solution in LNS. Default is 0.2.
      Returns:
      destruction probability

    • useLNS

      default boolean useLNS()
      Indicates whether LNS should be used. Default is true.
      Returns:
      true if LNS is enabled, false otherwise

    • fixWidth

      default LnsModel<T> fixWidth(int width)
      Returns a copy of this model with a fixed search width.
      Parameters:
      width - the width to fix
      Returns:
      a new LnsModel with the specified width

    • setInitialSolution

      default LnsModel<T> setInitialSolution(int[] solution)
      Returns a copy of this model with a specified initial solution.
      Parameters:
      solution - the initial solution
      Returns:
      a new LnsModel using the given initial solution

    • setProbability

      default LnsModel<T> setProbability(double proba)
      Returns a copy of this model with a specified destruction probability.
      Parameters:
      proba - the probability to use in LNS
      Returns:
      a new LnsModel with the specified probability