Module org.maxicp
Package org.maxicp.search

Class FDS

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

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).

The choices are generated lazily. At each branching point, the best unfixed choice is selected based on FDS ratings. Ratings are updated with exponential decay after each branch is explored, with emphasis on failures (localRating = 0 on failure).

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

Author:
pschaus

  • Constructor Summary

    Constructors
    Constructor
    Description
    FDS(double alpha, CPIntervalVar... intervals)
    Creates a Failure-Directed Search for the given interval variables.
    FDS(CPIntervalVar... intervals)
    Creates a Failure-Directed Search for the given interval variables.

  • Method Summary

    Modifier and Type
    Method
    Description
    Runnable[]
    get()
    The FDS branching strategy, implementing the Supplier<Runnable[]> interface.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • FDS

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

    • FDS

      public FDS(double alpha, CPIntervalVar... 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