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 and integer problems with CP variables.

This search algorithm is designed for a broad class of scheduling and constraint 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).
• Integer choice: whether x ≤ v or x > v (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(double alpha, CPIntervalVar[][] intervals)	Creates a Failure-Directed Search for the given 2D matrix of interval variables.
FDS(double alpha, CPIntervalVar[][] intervals, CPIntVar... intVars)	Creates a Failure-Directed Search for mixed 2D interval and integer decisions.
FDS(double alpha, CPIntervalVar[] intervals, CPIntVar... intVars)	Creates a Failure-Directed Search for mixed interval and integer decisions.
FDS(double alpha, CPIntVar... intVars)	Creates a Failure-Directed Search for integer variables.
FDS(double alpha, CPIntVar[][] intVars)	Creates a Failure-Directed Search for a 2D matrix of integer variables.
FDS(CPIntervalVar... intervals)	Creates a Failure-Directed Search for the given interval variables.
FDS(CPIntervalVar[][] intervals)	Creates a Failure-Directed Search for the given 2D matrix of interval variables.
FDS(CPIntervalVar[][] intervals, CPIntVar... intVars)	Creates a Failure-Directed Search for mixed 2D interval and integer decisions.
FDS(CPIntervalVar[] intervals, CPIntVar... intVars)	Creates a Failure-Directed Search for mixed interval and integer decisions.
FDS(CPIntVar... intVars)	Creates a Failure-Directed Search for integer variables.
FDS(CPIntVar[][] intVars)	Creates a Failure-Directed Search for a 2D matrix of integer variables.

Method Summary

Modifier and Type	Method	Description
Runnable[]	get()	The FDS branching strategy, implementing the Supplier<Runnable[]> interface.
void	resetLevel()	Resets the depth base level to the current solver level while keeping learned choice ratings.

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(CPIntervalVar[][] intervals)

Creates a Failure-Directed Search for the given 2D matrix of interval variables.

Parameters:

intervals - the 2D array of 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

FDS

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

FDS

public FDS(CPIntVar... intVars)

Creates a Failure-Directed Search for integer variables.

FDS

public FDS(CPIntVar[][] intVars)

Creates a Failure-Directed Search for a 2D matrix of integer variables.

FDS

public FDS(double alpha,
 CPIntVar... intVars)

Creates a Failure-Directed Search for integer variables.

FDS

public FDS(double alpha,
 CPIntVar[][] intVars)

Creates a Failure-Directed Search for a 2D matrix of integer variables.

FDS

public FDS(CPIntervalVar[] intervals,
 CPIntVar... intVars)

Creates a Failure-Directed Search for mixed interval and integer decisions.

FDS

public FDS(CPIntervalVar[][] intervals,
 CPIntVar... intVars)

Creates a Failure-Directed Search for mixed 2D interval and integer decisions.

FDS

public FDS(double alpha,
 CPIntervalVar[][] intervals,
 CPIntVar... intVars)

Creates a Failure-Directed Search for mixed 2D interval and integer decisions.

FDS

public FDS(double alpha,
 CPIntervalVar[] intervals,
 CPIntVar... intVars)

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

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