Overview | Group | Tree | Graph | Deprecated | Index | Concepts |

Interval variable sequencing in CP Optimizer

Interval sequence variables

An *interval sequence variable* is defined on a set of interval variables *A*. Informally speaking,
the value of an interval sequence variable represents a total ordering of the interval variables
of *A*. Note that any absent interval variables are not considered in the ordering.

More formally, an **interval sequence variable** *p* on a set interval variables *A* represents
a decision variable whose possible values are all the permutations of the intervals of *A*.
Let be a set of fixed intervals and *n* denote
the cardinality of .
A permutation π of is a
function π :
{ } [1, *n*]
such that if we denote length(π) = |{, *x*()}| the number
of present intervals:

Note that the sequence alone does not enforce any constraint on the relative position of
interval end-points. For instance, an interval variable *a* could be sequenced before an interval
variable *b* in a sequence *p* without any impact on the relative position between the start/end
points of *a* and *b* (*a* could still be fixed to start after the end of *b*). This is because different
semantics can be used to define how a sequence constrains the positions of intervals. We will
see later how the *noOverlap* constraint implements one of these possible semantics.

The following constraints are available on sequence variables:

*first(p, a)*states that if interval*a*is present, it will be the first interval of the sequence*p*.*last(p, a)*states that if interval*a*is present, it will be the last interval of the sequence*p*.*before(p, a, b)*states that if both intervals*a*and*b*are present,*a*will appear before*b*in the sequence*p*.*prev(p, a, b)*states that if both intervals*a*and*b*are present then*a*will be just before*b*in the sequence*p*. In other words, it will appear before*b*and no other interval will be sequenced between*a*and*b*in the sequence.

The formal semantics of these basic constraints are given in Table 3.

The sequence variable also allows the association of a fixed integer type with each interval variable
in the sequence. In particular, these integers are used by the *noOverlap* constraint (see below) and the *typeOfNext*/*Prev*
integer expressions (see below).
*T(p, a)* denotes the fixed integer type of interval variable *a* in the sequence variable *p*.

The constraints involving interval variables and interval sequence variables cannot be used in logical constraints of CP
Optimizer (see operator!, operator||). The reason is that any logical constraint involving interval variables
must be captured via the presence Boolean value on the interval handled by the *presenceOf* constraint.
The constraints having this limitation are the ordering constraints on a sequence (first, last, previous and before) and the
*noOverlap* constraint.

No overlap constraint

The **noOverlap** constraint on an interval sequence variable *p* states that the sequence defines
a chain of non-overlapping intervals, and any interval in the chain is constrained to end before
the start of the next interval in the chain. This constraint is typically useful for modeling
disjunctive resources.

More formally, the condition for a permutation value π for sequence *p* to satisfy the
*noOverlap* constraint is defined as:

A sequence variable together with a no-overlap constraint using it are illustrated in Figure 4.

If a transition distance matrix *M* is specified, it defines the minimal distance that must
separate two consecutive intervals in the sequence. Two versions of the constraint
are available: one that enforces the transition distance between each interval and its next interval in the sequence
(*Next*), and the other that enforces the transition distance between
each interval and all its successors in the sequence (*After*).

More formally, if *T(p,a)* denotes the integer type of interval *a* in the sequence variable *p*:

Note that if the transition matrix *M* satisfies the triangular inequality, the semantics of the
two versions of the constraint and
are the same. If *M* does
not satisfy the triangular inequality,
constraint is stronger than
.

Same-sequence and same-common-subsequence constraints

The **sameSequence** and **sameCommonSubsequence** constraints are binary constraints
on a pair of sequence variables and . These constraints state that the relative position
of some related subsets of interval variables is the same in both sequences: typically, if *a* is
before *b* in sequence then the interval related to
*a* is before the interval related to *b* in
sequence . Here are two examples of use-cases where these constraints are useful:

- First in/first out and no-bypass constraints. In some physical systems like trains on a
single line railway or items on a conveyor belt, bypassing is not possible and items
must enter and exit a given section of the system in the same order. If entering
and exiting the sections or the junctions of the system is modeled by two related interval
variables, those constraints can be modeled by
*sameSequence*constraints (or*sameCommonSubsequence*constraints if the items do not follow the same path) on the sequences of entering and exiting intervals. A classical example of such a constraint is the permutation flow-shop scheduling problem. - Scenario-Based approaches for scheduling with uncertainties. In presence of uncertainties
(for instance, uncertain activity durations) one may be interested in building
sequences of activities on unary resources that optimize some robustness or statistical
criterion (for instance the expected makespan). A scenario is a sub-model that defines a
particular realization of the uncertainties in the environment. As one must find robust
sequences that optimize some criterion over all scenarios, the different sequences of a
given unary resource across all scenarios are linked with
*sameSequence*constraints.

A constraint *sameCommonSubsequence*()
is defined on two sequence variables (defined on a set of interval
variables ) and (defined on a
set of interval variables ) with two arrays of interval variables
and of identical size and such
that . The constraint states that the sub-sequences defined by
and by only considering the pairs of
present intervals () are identical modulo the mapping between
intervals
and .

For instance, let's suppose sequence variable defined on interval
variables *{a,b,c,d,e,f}* and sequence variable defined on interval
variables *{u,v,w,x,y,z}* with a constraint *sameCommonSubsequence*(,
,*[a,c,d,e,f],[u,w,v,x,y]*). Assuming in a solution, interval
variables *d* and *y* are absent while all the other interval variables are present. The pair
of permutations *=(c,f,a,e,b)* and
*=(w,v,u,x)* satisfies the *sameCommonSubsequence* constraints.
Indeed if one only considers pairs of present intervals, the mapping maps
*[a,c,e]* with *[u,w,x]*. Subsequence of over
*{a,c,e}* is *(c,a,e)*, subsequence of over
*{u,w,x}* is *(w,u,x)* and one can see that the two subsequences are the same modulo the
mapping.

More formally, let *n* denote the size of both interval variable arrays
and . The condition for permutations and
of sequencing variables and
to satisfy constraint
*sameCommonSubsequence*()
is defined as:

A constraint *sameSequence*() is defined on two sequence
variables of identical size (defined on a set of interval variables
) and (defined on a set of interval
variables ) with two arrays of interval variables
and that are an ordering of sets
and . The constraint states that sequences
and are identical modulo a mapping between intervals
and . A *sameSequence*
constraint is stronger than a *sameCommonSubsequence*
constraint; it additionally imposes that arrays and
contain all the definition intervals
of their relative sequence variables and that the presence status of mapped interval variables
and is the same.

More formally, let *n* denote the size of both sequence variables. The condition for permutations
and of the sequence variables
and to satisfy constraint
*sameSequence*() is defined as:

when parameters and are omitted in the definition of the above constraints, we assume and are the definition intervals of and , following the order of definition of interval variables in the sequence.

Expressions for getting the type of a next/prev interval

Two integer expressions are available to get the type of the interval that is next (resp. previous)
to a given interval variable *a* in a sequence *p*. When interval *a* is absent or is the
last (resp. first) interval of the sequence, specific values can be provided for these integer
expressions.

More formally, let π be the permutation value of a fixed sequence variable *p*, and
be the value
of a fixed interval variable *a* in the fixed sequence variable *p*.

If is present and is not the last interval in π, we denote the unique interval that is next to in π.

If is present and is not the first interval in π, we denote the unique interval that is previous to in π.

Expressions for getting the bounds of next/previous interval

Integer expressions *startOfNext*, *endOfNext*, *lengthOfNext*, *sizeOfNext*,
*startOfPrev*, *endOfPrev*, *lengthOfPrev*, and *sizeOfPrev* provide access to
the different attributes of the interval that is next (resp. previous) to a given interval variable *a*
in a sequence *p*. When interval *a* is absent or is the last (resp. first) interval of the
sequence, specific values can be provided for these integer expressions.

The semantics of these expressions are given in the table below.