All Classes and Interfaces
Class
Description
Absolute value constraint
An abstract search method that can be used concurrently: it is stoppable and can be work-stealed.
Abstract class the most of the constraints
should extend.
An abstract search method, implementing all the parts needed, but the search method itself.
Represents a scheduling activity, i.e., an interval variable that consumes an amount of resource over time.
AllDifferent constraint ensuring that all expressions in
x take pairwise distinct values.Arc Consistent AllDifferent Constraint
Forward Checking AllDifferent Constraint.
Alternative Constraint with cardinality:
Enforces that if the interval a is present, then c intervals from the array alt must be present and synchronized
with a.
Exclusive alternative between intervals.
Constraint that enforces a
CumulFunction to remain within bounds
at every point overlapping the execution of at least one interval.Among constraint.
Among constraint ensuring that exactly
count expressions in x take a value in values.Domain Consistency Filtering for AtLeastNValue constraint.
Forward Checking filtering for the AtLeastNValue constraint.
A very simple ModelProxy which is not thread-safe.
A Binary Knapsack constraint ensures that the total load
is equal to the sum of the weights of the selected items.
The
BinPacking constraint ensures that a set of items with given weights
are packed into bins such that each bin's total weight respects a given capacity constraint.BinPacking constraint.
This class provides algorithms for the Bin Packing.
Bitset abstract class
Commercial-solver-style black-box search orchestrator for modeling-level CP and scheduling problems.
Configuration for exhaustive DFS/FDS phase.
Strategy used to choose which decision variables are frozen in each LNS
restart.
Snapshot of an
IntervalVar in an incumbent solution.Configuration for LNS improvement phase.
Configuration for restart-based feasibility phase.
Logging granularity for phase execution.
Upper-bound cardinality constraint ensuring that each value
v in 0..array.length - 1
appears at most array[v] times in x.Forward Checking Cardinality (Upper Bound) Constraint.
Lower-bound cardinality constraint ensuring that each value
v in 0..array.length - 1
appears at least array[v] times in x.Forward Checking Cardinality (Lower Bound) Constraint.
Hamiltonian Circuit Constraint with a successor model
Hamiltonian circuit constraint ensuring that the successor array forms a single Hamiltonian circuit
visiting all nodes
0..successor.length - 1.A concrete constraint that can be used by a concrete model
A base class for some "Layer models" that can locally override some methods
but redirect everything else to a bottom layer.
Conflict-driven adaptive branching strategy (
dom/wdeg + Last-Conflict +
objective-polarity / phase-saving / solution-guided value selection + primary/secondary variable tiering).Constants used in the MaxiCP library
StateManager that will store
the state of every created elements
at each
Copier.saveState() call.Implementation of
State with copy strategyImplementation of
StateInt with copy strategyImplementation of
StateLong with copy strategyImplementation of
StateMap with copy strategyArc Consistent AllDifferent Constraint with Costs
Implementation of the Global Cardinality Constraint with Costs from the paper
Boolean variable, that can be used as a 0-1 IntVar.
Interface implemented by every Constraint
CP implementation of a Cumulative Function
A fixed set variable that contains a specific set of values.
CP implementation of a Flat Cumulative Function
TODO
TODO
Provides a view of a CPIntervalVar that is delayed by a fixed offset value.
Implementation of a variable
with a
SparseSetDomain.A view on a variable of type
a*xA view on a variable of type
x+oA view on a variable of type
-xCP implementation of a Minus Cumulative Function (
left - right).CP implementation of a Plus Cumulative Function (
left + right).CP implementation of a Pulse Cumulative Function
A set variable is a variable that represents a set of integers from an original universe set.
Implementation of a set variable.
CP implementation of a Step at End Cumulative Function
CP implementation of a Step at Start Cumulative Function
CP implementation of a Sum Cumulative Function.
Cumulative constraint on a sequence variable (
CPSeqVar), ensuring that the total resource consumption
of active activities along the sequence never exceeds a given capacity.Cumulative scheduling constraint ensuring that at any point in time, the total resource demand
of overlapping activities does not exceed the resource capacity
capa.Modeling-level cumulative constraint on a sequence variable (
SeqVar), ensuring that the total load
of active activities along the sequence never exceeds capacity.Cumulative constraint with sum decomposition (very slow).
Represents a Cumulative Function as described in
The Cumulative Scheduling Problem (CuSP)
consists in scheduling a set tasks that share a resource with a fixed capacity.
This class should be used to implement custom constraints.
capacitated vehicle routing, with time windows
DARP
Model for the Dial-A-Ride Problem (DARP) using sequence variables.
Dial-A-Ride problem
Data related to a node in the DARP problem
Walks the full constraint / expression graph of a
ModelDispatcher
and collects candidate decision variables (IntExpression and IntervalVar).Implemented by constraints and expression nodes that know which of their
sub-expressions play an "index / choice" role and are therefore candidate
decision variables for search and LNS.
Object that allows to retrieve
in a constraint the changes of the domain
of a variable from one call to the
Constraint.propagate
to the next.Depth-First Search Branch and Bound implementation
A DFSListener that records the search tree in a Tree structure.
Disjunctive scheduling constraint ensuring that no two activities overlap in time.
Distance constraint on a sequence variable (
CPSeqVar), maintaining the total travel distance
between consecutive visited nodes in the sequence.Modeling-level distance constraint on a sequence variable (
SeqVar), maintaining the total travel
distance between consecutive visited nodes in the sequence.Expression x / y
Integer Constraint x / y = z (all variables)
Element Constraint modeling
array[y] = zElement1DDC constraint
Element Constraint over an array of variables, modeling
array[y] = z.Element Constraint modeling
matrix[x][y] = zConstraint enforcing that the end of an interval variable comes after or at a given integer variable:
end(interval) >= var when interval is present.Enforces that interval A ends at interval B end if B is present
and that interval B ends at interval A end if A is present
Enforces that interval A ends at interval B start if B is present
and that interval B starts at interval A end if A is present
Constraint enforcing that the end of an interval variable comes before or at a given integer variable:
end(interval) <= var when interval is present.Constrains interval A to end before or at the end of interval B.
Constrains interval A to end before or at the start of interval B if both are present.
Equality constraint between two integer variables
x = y.The Eternity II puzzle is an edge-matching puzzle which
involves placing 256 square puzzle pieces into a 16 by 16 grid,
constrained by the requirement to match adjacent edges.
Excludes a node from a sequence
Constraint excluding a node from a sequence variable (
SeqVar) so that it is not visited.An expression, that can be integer, boolean, or a sequence
Constraint enforcing that a boolean expression
expr evaluates to true (1).Modeling factory providing static helper methods to create model dispatchers, objectives,
symbolic integer/boolean/cumulative expressions, and high-level modeling constraints.
Failure-Directed Search (FDS) for scheduling and integer problems with CP variables.
Failure-Directed Search (FDS) for scheduling problems with modeling-layer interval variables.
Flexible Jobshop Instances from
https://github.com/SchedulingLab/fjsp-instances/
Format:
First line:
Then one line per job: and then, for each operation,
and for each machine, a pair
.
Flat Elementary Cumul Function
The Flexible Job Shop Problem (FJSP) is an extension of the classical Job
Shop Scheduling Problem.
The Flexible Job Shop Problem (FJSP) is an extension of the classical Job
Shop Scheduling Problem.
Selects which decision-variable indices are frozen for one LNS restart.
Checker for the generalized cumulative constraint.
Generalized Cumulative Constraint using Timetabling
TODO Refer paper once published
Generalized Cumulative Constraint using Timetabling
TODO Refer paper once published
Sweep-line filtering algorithm for the Generalized Cumulative constraint enforcing a maximum capacity bound.
Sweep-line filtering algorithm for the Generalized Cumulative constraint enforcing a minimum capacity bound.
Algorithms and Graph interface
Directed graph API
Fragment selector that keeps variables from the same array together.
PGLNS-inspired selector: keep low-impact vars fixed and relax high-impact ones.
Inserts a node into a sequence
Interface for integer domain implementation.
Domain listeners are passed as argument
to the
IntDomain modifier methods.Gives the end of an
IntervalVarGives the end of an
IntervalVar or a given value if the interval is not presentGives the length of an
IntervalVarGives the length an
IntervalVar or a given value if the interval is not presentGives the start of an
IntervalVarGives the start of an
IntervalVar or a given value if the interval is not presentConstraint linking the end time of an interval variable
var to an integer variable end.Constraint linking the end time of an interval variable
var to an integer variable end
when var is present, or fixing end to a default value when var is absent.Constraint linking the length (duration) of an interval variable
var to an integer variable length.Constraint linking the length (duration) of an interval variable
var to an integer variable length
when var is present, or fixing length to a default value when var is absent.Constraint linking the start time of an interval variable
var to an integer variable start.Constraint linking the start time of an interval variable
var to an integer variable start
when var is present, or fixing start to a default value when var is absent.The Inventory Scheduling Problem was introduced in the paper:
Minimizing makespan on a single machine with release dates and inventory constraints
Morteza Davari, Mohammad Ranjbar, Patrick De Causmaecker, Roel Leus
European Journal of Operational Research 2020
InversePerm is a constraint that enforces that one permutation is the inverse of another.
Reified constraint enforcing
boolVar <=> end(intervalVar) >= var when intervalVar is present.Reified constraint enforcing
boolVar <=> end(intervalVar) <= var when intervalVar is present.Reified is end before start constraint
Reified is end before start constraint
Reified temporal ordering constraint with transition times.
Reified equality constraint
Reified equality constraint
Constraint that enforces a boolean variable to be true if a value is included in a set.
Reified less or equal constraint.
Reified is less or equal constraint
b <=> x <= y.Reified logical or constraint
Reified constraint enforcing
boolVar <=> start(intervalVar) <= var when intervalVar is present.Reified is end before start constraint
Reified is start before start constraint
Constraint that enforces a boolean variable is
true if one set is a subset of another set.
The JobShop Problem.
The JobShop Problem.
Constraint fixing the length of an interval variable to a given constant value.
Less or equal constraint between two variables
Constraint enforcing that a cumulative function
function never exceeds limit
over its horizon.Global lexicographic ordering constraint between two vectors x and y:
enforces
x <=_lex y (when strict == false) or x <_lex y (when strict == true).Lexicographic ordering constraint enforcing
x <=_lex y (or x <_lex y if strict is true).Lightweight Binary Knapsack constraint enforcing
load = sum_i items[i] * weights[i]
using bound reasoning on the required and possible loads.Branching combinator
that ensures that that the alternatives created are always within the
discrepancy limit.
The Magic Series problem.
The Magic Square problem.
The Magic Square problem.
The Magic Square problem.
Maximization objective function
Maximum Constraint
Compute and Maintain a Maximum Matching
in the variable-value graph
Max Independent Set Problem of a graph:
Given a graph, find the largest set of vertices such that no two vertices in the set are adjacent.
Minimum-cost maximum-flow algorithm using successive shortest augmenting paths with potentials.
Minimization objective function
Objective to minimize a sum of variables following
the approach described in the paper:
Variable Objective Large Neighborhood Search:
A practical approach to solve over-constrained problems (ICTAI 2013, Pierre Schaus)
Difference between two Cumul Functions.
A class that allows to create symbolic models
Convenience entry points for running
BlackBoxSearch from the modeling layer.Configuration object used by optimization solves.
Configuration object used by feasibility solves.
Maintains the current model and proxies calls to it.
Maintains the current model and proxies calls to it.
Generic, problem-independent structural analyzer for a constraint model.
Constraint x * b = y where b is a boolean variable
Multiplication Constraint x * c = z where c is a constant
Multiplication Constraint x * y = c
Multiplication Constraint x * y = z (all variables)
Negative table constraint ensuring that the tuple of values assigned to
x does not match
any forbidden tuple in array.Implementation of Compact Table for Negative Table algorithm described in
A constraint that does nothing.
NoOverlap constraint, ensures that a set of interval variables do not overlap in time.
Disjunctive scheduling constraint ensuring that no two present intervals in
intervals overlap in time.Bound Consistency filtering for the NoOverlap constraint
Bound Consistency filtering for the NoOverlap constraint
Binary NoOverlap constraint enforcing that two interval variables
A and B
do not overlap in time when both are present.Binary NoOverlap constraint with transition times enforcing that two interval variables
A and B
do not overlap and respect minimum setup/transition times transitionTimeAB (when A precedes B)
and transitionTimeBA (when B precedes A) when both are present.Left-to-right global filtering algorithms for the
NoOverlap constraint
(Overload Checking, Detectable Precedences, Not-Last, and Edge-Finding),
based on Petr Vilim's PhD thesis (2008).Channels a
CPSeqVar with an array of CPIntervalVar and enforces
a no-overlap with minimum transition times between consecutive intervals.A global constraint that enforces a permutation (ordering) of interval variables
with minimum transition times, using set-variable-based propagation for stronger
filtering than the binary decomposition
NoOverlapWithPositionDecomposition.Modeling-level constraint for no-overlap with position variables.
A constraint that enforces a permutation (ordering) of interval variables,
typically used for routing/scheduling problems such as TSP or job sequencing.
Constraint forbidding a node from being inserted immediately between a given predecessor and successor
in a sequence variable (
CPSeqVar).Constraint forbidding
node from being inserted immediately between prev and after
in a sequence variable (SeqVar).Not Equal constraint between two variables
Constraint that enforces that the first set variable is not a subset of the second set variable.
The N-Queens problem.
The N-Queens problem.
The N-Queens problem solved with Embarassingly Parallel Search (EPS).
The N-Queens problem.
The N-Queens problem.
The N-Queens problem.
The N-Queens problem.
Nurse scheduling problem.
Objective object to be used
in the
AbstractSearchMethod.optimize(Objective)
for implementing the branch and bound depth first search.Logical or constraint
x1 or x2 or ... xnPerfect Square Problem
The problem is to fully cover a big square with different smaller ones, with no overlap between them
Sum of two Cumul Functions.
Precedence constraint on a sequence variable (
CPSeqVar), ensuring that a given list of nodes
appears in the specified relative order within the sequence.Precedence constraint on a sequence variable (
SeqVar), ensuring that the given nodes
appear in the specified relative order if visited in the sequence.Constraint enforcing that an interval variable
intervalVar must be present.RCPSP-CPR model (Modeling layer).
RCPSP-CPR model.
Representation of a cumulated Profile
data structure as a contiguous sequence of
Profile.Rectangle
built from a set of Profile.Rectangle using a sweep-line algorithm.Representation of a cumulated Profile data structure as a contiguous sequence of
Profile.Rectangle
built from a set of Profile.Rectangle using a sweep-line algorithm.Represents a rectangle which is part of the
Profile datastructurePulse Elementary Cumul Function.
The Quadratic Assignment problem.
The Quadratic Assignment problem.
Legacy LNS fragment selection: each decision variable is frozen independently.
Rank Branching
Rank Branching for Modeling Layer
Resource Constrained Project Scheduling Problem.
Resource Constrained Project Scheduling Problem.
Imposes that the sequence defined
by the provided orderedSequence where the relaxed nodes
have been removed is a subsequence of the provided sequence variable.
Requires a node in a sequence, forcing the node to be visited
Require a node to be visited within a
SeqVarFeasibility search phase based on repeated DFS restarts with persistent conflict learning.
Tarjan's algorithm to find strongly connected components (SCCs) in a directed graph.
Large Neighborhood Search (LNS) improvement phase for scheduling and hybrid scheduling+integer models.
Constructive and exhaustive scheduling search phase for models containing
IntervalVars.Factory for search procedures.
Statistics collected during the
execution of
AbstractSearchMethod.solve() and
AbstractSearchMethod.optimize(Objective)Status of the nodes
Sequential Search combinator that linearly
considers a list of branching generator.
Sequence-based ranking search inspired by
Rank.Constraint that links the cardinality of a set variable to an integer variable.
Interface for set domain implementation.
SetDomain listeners are passed as argument
to the
SetDomain modifier methods.Set Times Branching
!!!
Ship Loading Problem.
Implementation of Compact Table for Short Table algorithm described in
A Single Machine with Inventory Constraints (SMIC) problem consists
of scheduling a set of J of n jobs split into in two:
- the loading jobs J+ and
- the unloading jobs J-.
A Single Machine with Inventory Constraints (SMIC) problem consists
of scheduling a set of J of n jobs split into in two:
- the loading jobs J+ and
- the unloading jobs J-.
A Single Machine with Inventory Constraints (SMIC) instance.
The Send-More-Money problem.
Soft Global Cardinality Constraint.
Sorted constraint, x is sorted in y according to permutation o
Sorted constraint:
y is the sorted version of x with
position permutation o (i.e.Span Constraint:
Enforces that if the interval span is present, then it begins with the first interval intervals from the array alt and ends with the latest.
Span constraint between intervals.
Implementation of a domain with a sparse-set
The problem is to schedule an even number n of teams over n/2 periods and n - 1 weeks,
under the following constraints:
- Each team must play against every other team
- A team plays exactly one game per week
- A team can play at most twice in the same period
- Each team must play against every other team
- A team plays exactly one game per week
- A team can play at most twice in the same period
The problem is to schedule an even number n of teams over n/2 periods and n - 1 weeks,
under the following constraints:
- Each team must play against every other team
- A team plays exactly one game per week
- A team can play at most twice in the same period
- Each team must play against every other team
- A team plays exactly one game per week
- A team can play at most twice in the same period
Square Constraint x * x = y
Stable Marriage problem:
Given n women and n men, where each woman (resp. man) has
ranked each man (resp. woman) with a unique number between 1 and n
in order of preference (the lower the number, the higher the preference),
say for summer internships, match the women and men such that
there is no pair of a woman and a man who would both prefer to be
matched with each other than with their actually matched ones.
Constraint fixing the start time of an interval variable to a given constant value.
Constraint enforcing that the start of an interval variable comes after or at a given integer variable:
start(interval) >= var when interval is present.Constraint enforcing that an interval variable starts at or after a given time
start.Enforces that interval A starts at interval B end if B is present
and that interval B ends at interval A start if A is present
Enforces that interval A starts at interval B start if B is present
and that interval B starts at interval A start if A is present
Constraint enforcing that the start of an interval variable comes before or at a given integer variable:
start(interval) <= var when interval is present.Boolean variable that represents if an interval is executed before a given value
Constrains interval A to start before or at the end of interval B if both are present.
Constrains interval A to start before or at the start of interval B.
Object that wraps a reference
and can be saved and restored through
the
StateManager.saveState() / StateManager.restoreState()
methods.A StateEntry is aimed to be
stored by a StateManager to revert some state
Object that wraps an integer value
that can be saved and restored through
the
StateManager.saveState() / StateManager.restoreState()
methods.Implementation of an interval that can saved and restored through
the
StateManager.saveState() / StateManager.restoreState()
methods.A sparse-set that lazily switch
from a dense interval representation
to a sparse-set representation
when a hole is created in the interval.
Object that wraps an integer value
that can be saved and restored through
the
StateManager.saveState() / StateManager.restoreState()
methods.The StateManager exposes
all the mechanisms and data-structures
needed to implement a depth-first-search
with reversible states.
A generic map that can revert its state
with
StateManager.saveState() / StateManager.restoreState()
methods.Class to represent a bit-set that can be saved and restored through
the
StateManager.saveState() / StateManager.restoreState()Set implemented using a sparse-set data structure
that can be saved and restored through
the
StateManager.saveState() / StateManager.restoreState()
methods.Generic Stack that can be saved and restored through
the
StateManager.saveState() / StateManager.restoreState()
methods.Tri-partition sparse-set data structure
that can be saved and restored through
the
StateManager.saveState() / StateManager.restoreState()
methods.Steel is produced by casting molten iron into slabs.
Step at End Elementary Cumul Function.
Step at Start Elementary Cumul Function
Exception that is thrown to stop
the execution of
AbstractSearchMethod.solve(), AbstractSearchMethod.optimize(Objective)Object that can be saved by the
Copier.Ensures that only one Hamiltonian circuit appears in the provided successor variables.
SubCircuit constraint ensuring that the successor array forms at most one circuit
while nodes with
successor[i] == i are self-loops not part of the circuit.Links two
CPSeqVar, ensuring a subsequence appears within a super sequenceConstraint ensuring that the sequence
sub is a subsequence of main
(all nodes visited in sub are visited in main in the same relative order).Constraint that enforces that one set variable is a subset of another set variable.
Sum Constraint
Sum of one or more Cumul Functions.
Positive table constraint ensuring that the tuple of values assigned to
x belongs to
the set of allowed tuples in array.Implementation of Compact Table algorithm described in
Data Structure described in
Global Constraints in Scheduling, 2008 Petr Vilim, PhD thesis
See The thesis.
Data Structure described in
Global Constraints in Scheduling, 2008 Petr Vilim, PhD thesis
See The thesis.
Implementation of
State with trail strategyStateManager that will lazily store
the state of state object
at each
Trailer.saveState() call.Implementation of
StateInt with trail strategyImplementation of
StateInt with trail strategyImplementation of
StateMap with trail strategyLinks a
CPSeqVar with time windows, enforcing that visits happen during valid timeframes.Modeling-level constraint linking a sequence variable (
SeqVar) with visit time expressions,
transition distances, and service durations.Tree structure for visualizing search trees (e.g., backtracking algorithms).
Tree node containing logical data (not layout).
Immutable pair
Layout node: wraps a Node with its calculated horizontal position.
Traveling salesman problem.
Traveling salesman problem.
Traveling salesman problem.
Traveling salesman problem.
Traveling Salesman Problem with Time Windows (TSPTW) using a position-based routing model.
A TSP with Time Windows instance.
Traveling Salesman Problem with Time Windows (TSPTW) using a scheduling model
with interval variables and a noOverlap constraint with position variables.
Traveling Salesman Problem with Time Windows (TSPTW) using a sequence variable model.
The Traveling Salesman Problem with Time Windows (TSPTW) is a variation of
the classic Traveling Salesman Problem (TSP) in which each city must
be visited within a specific time interval.
Traveling Salesman Problem with Time Windows (TSPTW) using a successor-based routing model.
Traveling Salesman Problem with Time Windows (TSPTW) using a successor-based routing model.
An extension of the default XCallback parser that provides default decompositions for the most complex constraints.
Competition-oriented CLI for XCSP3 instances.