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(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

  • Method Details

    • get

      public Runnable[] get()
      The FDS branching strategy, implementing the Supplier<Runnable[]> interface.

      This method implements the core FDS algorithm from Algorithm 1 in the paper. At each branching point:

      1. Select the applicable choice with the best (lowest) rating.
      2. Skip waiting and resolved choices.
      3. Return two branches: the better-rated branch first (heading into conflict).
      If all initial choices are resolved but variables remain unfixed, additional choices are generated dynamically.
      Specified by:
      get in interface Supplier<Runnable[]>
      Returns:
      array of branching closures, or EMPTY if all tasks are fixed