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 ammount of resource over time.
Arc Consistent AllDifferent Constraint
Algorithm described in
"A filtering algorithm for constraints of difference in CSPs" J-C.
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
Domain Consistency Filtering for 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
Phase-based black-box search orchestrator for modeling-level CP problems.
Configuration for exhaustive DFS/FDS phase.
Strategy used to choose which decision variables are frozen in each LNS
restart.
Configuration for LNS improvement phase.
Configuration for restart-based feasibility phase.
Logging granularity for phase execution.
Hamiltonian Circuit Constraint with a successor model
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.
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
CP implementation of a Plus Cumulative Function
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 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 all candidate decision variables declared by
DecisionVarsProvider nodes.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.
Expression x / y
Integer Constraint x / y = z (all variables)
Element Constraint modeling
array[y] = zElement1DDC constraint
Element Constraint modeling
matrix[x][y] = zEnforces 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
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.
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
An expression, that can be integer, boolean, or a sequence
Failure-Directed Search (FDS) for scheduling problems with interval variables.
Failure-Directed Search (FDS) for scheduling problems with modeling-layer interval variables.
Flat Elementary Cumul Function
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
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 presentTODO
TODO
TODO
TODO
TODO
TODO
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 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 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.
Less or equal constraint between two variables
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.
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.
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)
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.
Bound Consistency filtering for the NoOverlap constraint
Bound Consistency filtering for the NoOverlap constraint
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.
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.
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.
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.
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
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.
Links two
CPSeqVar, ensuring a subsequence appears within a super sequenceConstraint that enforces that one set variable is a subset of another set variable.
Sum Constraint
Sum of one or more Cumul Functions.
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.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.