Module org.maxicp
Package org.maxicp.search

Class FDSModeling

java.lang.Object
org.maxicp.search.FDSModeling
All Implemented Interfaces:
Supplier<Runnable[]>
public class FDSModeling extends Object implements Supplier<Runnable[]>
Failure-Directed Search (FDS) for scheduling problems with modeling-layer interval variables.

This is the modeling-layer adaptation of FDS, working with IntervalVar and ModelProxy instead of CPIntervalVar and CPSolver.

This search algorithm is designed for a broad class of scheduling problems. Instead of guiding the search towards possible solutions, FDS drives the search into conflicts in order to prove that the current branch is infeasible. Choices that fail the most are preferred (first-fail principle applied also to branch ordering).

The algorithm works with binary choices:

  • Presence choice: whether an optional interval variable is present or absent.
  • Start time choice: whether startOf(v) ≤ t or startOf(v) > t (domain splitting).
  • Length choice: whether length(v) ≤ l or length(v) > l (domain splitting).

Reference: Vilím, P., Laborie, P., Shaw, P. (2015). Failure-directed Search for Constraint-based Scheduling. CPAIOR 2015.

Author:
pschaus

  • Constructor Details

    • FDSModeling

      public FDSModeling(IntervalVar... intervals)
      Creates a Failure-Directed Search for the given interval variables.
      Parameters:
      intervals - the interval variables to decide

    • FDSModeling

      public FDSModeling(IntervalVar[][] intervals)
      Creates a Failure-Directed Search for the given 2D matrix of interval variables.
      Parameters:
      intervals - the 2D array of interval variables to decide

    • FDSModeling

      public FDSModeling(double alpha, IntervalVar... intervals)
      Creates a Failure-Directed Search for the given interval variables.
      Parameters:
      alpha - decay factor for rating updates (typical: 0.9 to 0.99)
      intervals - the interval variables to decide

    • FDSModeling

      public FDSModeling(double alpha, IntervalVar[][] intervals)
      Creates a Failure-Directed Search for the given 2D matrix of interval variables.
      Parameters:
      alpha - decay factor for rating updates (typical: 0.9 to 0.99)
      intervals - the 2D array of interval variables to decide

    • FDSModeling

      public FDSModeling(IntExpression... intExpressions)
      Creates a Failure-Directed Search for integer expressions.

    • FDSModeling

      public FDSModeling(IntExpression[][] intExpressions)
      Creates a Failure-Directed Search for a 2D matrix of integer expressions.

    • FDSModeling

      public FDSModeling(double alpha, IntExpression... intExpressions)
      Creates a Failure-Directed Search for integer expressions.

    • FDSModeling

      public FDSModeling(double alpha, IntExpression[][] intExpressions)
      Creates a Failure-Directed Search for a 2D matrix of integer expressions.

    • FDSModeling

      public FDSModeling(IntervalVar[] intervals, IntExpression... intExpressions)
      Creates a Failure-Directed Search for mixed interval and integer decisions.

    • FDSModeling

      public FDSModeling(IntervalVar[][] intervals, IntExpression... intExpressions)
      Creates a Failure-Directed Search for mixed 2D interval and integer decisions.

    • FDSModeling

      public FDSModeling(double alpha, IntervalVar[][] intervals, IntExpression... intExpressions)
      Creates a Failure-Directed Search for mixed 2D interval and integer decisions.

    • FDSModeling

      public FDSModeling(double alpha, IntervalVar[] intervals, IntExpression... intExpressions)
      Creates a Failure-Directed Search for mixed interval and integer decisions.

  • Method Details

    • resetLevel

      public void resetLevel()
      Resets the depth base level to the current solver level while keeping learned choice ratings.

    • get

      public Runnable[] get()
      Specified by:
      get in interface Supplier<Runnable[]>