Overview | Group | Tree | Graph | Deprecated | Index | Concepts |
Basic interval variables |
Intensity and size and forbidden values |
Expressions over Interval Variables |
Display of interval variable domain |
Informally speaking, an interval variable represents an interval of time during which something happens (a task or an activity is carried out) and whose position in time is an unknown of the scheduling problem. An interval is characterized by a start value, an end value and a size. An important additional feature of interval variables is the fact that they can be optional; in other words, one can decide not to consider them in the solution schedule. This concept is crucial in applications that present at least some of the following features:
More formally, an interval variable a is a variable whose domain dom(a) is a subset of
An interval variable is said to be fixed if its domain is reduced to a singleton, i.e., if denotes a fixed interval variable:
Absent interval variables have special meaning. Informally speaking, an absent interval
variable is not considered by any constraint or expression on interval variables that it is involved in.
For example, if an absent interval variable is used in a noOverlap
constraint, the constraint
will behave as if the interval was never specified to the constraint. If an absent interval variable
a is used in a precedence constraint between interval variables a and b this
constraint does not impact interval variable b. Each constraint specifies how it handles absent interval
variables.
In this document, the semantics of constraints defined over interval variables is described by the properties that fixed intervals must have in order the constraint to be true. If a fixed interval is present and such that = [s, e), we will denote s() its integer start value s, e() its integer end value e and l() its positive integer length defined as e()-s(). The presence status x() will be equal to 1. For a fixed interval that is absent, x() = 0 and the start, end, and length are undefined.
Until a solution is found it may not be known whether an interval will be present or not. In this case we say that the interval is optional. To be precise, an interval is said to be absent when dom(a) = {}, present when dom(a) and optional in all other cases.
The start and end of an interval variable must be in [IloIntervalMin..IloIntervalMax]
.
All constraints involving interval variables cannot be used in logical constraints of CP Optimizer (see operator!, operator||) except for the presence constraint. The reason is that any logical constraint involving interval variables must be captured by the presence Boolean value on the interval handled by the presenceOf constraint. The constraints having this limitation are precedence constraints, constraints forbidStart, forbidEnd, forbidExtent and constraints on groups of interval variables such as span, synchronize and alternative.
Sometimes the intensity of “work” is not the same during the whole interval. For example let’s consider a worker who does not work during weekends (his work intensity during weekends is 0%) and on Friday he works only for half a day (his intensity during Friday is 50%). For this worker, 7 man-days work will span for longer than just 7 days. In this example 7 man-days represent what we call the size of the interval: that is, the length of the interval would be if the intensity function was always at 100%.
To model such situations, you can specify a range for the size of an interval variable and an integer stepwise intensity function whose step bounds are integer F (see Piecewise linear and stepwise functions in CP Optimizer). For a fixed present interval the following relation will be enforced at any solution between the start, end, size sz of the interval and the integer granularity G (by default, the intensity function is expressed as a percentage so the granularity G is 100):
The length of the interval will be at least long enough to cover the work requirements given by the interval size, taking into account the intensity function. However, any over-estimation is always strictly less than one work unit.
If no intensity is specified, it is assumed to be the constant full intensity function (t, F(t) = 100%) so in that case sz(a) = l(a). Note that the size is not defined for absent intervals.
Important: The intensity step function F is a stepwise function with integer values and is not allowed to exceed the granularity (100 by default).
Figure 2 depicts an interval variable of size 14 and an associated intensity function. A valid solution is represented where the interval starts at 10 and ends at 27. In this case,
It may be necessary to state that an interval cannot start, cannot end, or cannot overlap a set of fixed dates. CP Optimizer provides the following constraints for modeling it. Let a denote a fixed interval and F an integer stepwise function.
More formally:
This section shows how to create numerical expressions from interval variables. These expressions can be used to:
Integer expressions startOf, endOf, lengthOf, and sizeOf provide access to the different attributes of an interval variable. However special care must be taken for optional intervals: in this case an integer value absVal must be specified which represents the value of the expression when the interval is absent. If this value is omitted, it is assumed to be 0.
Numerical expressions (startEval, endEval, lengthEval, sizeEval) allow you to evaluate a piecewise linear function (see Piecewise linear and stepwise functions in CP Optimizer) on a given bound of an interval. Like for the above expressions, a numerical value absVal can be specified that represents the value of the expression when the interval is absent. If this value is omitted, it is assumed to be 0.
Let denote a fixed interval variable. The semantics of these expressions are given in Table 2.
The domain of an interval variable is displayed as shown in this example:
A1[0..1: 10..990 -- (5..10)5..990 --> 25..1000]
After the name of the interval variable (here A1
), the first range (here 0..1) represents
the domain of the Boolean presence status of the interval variable. Thus 0..1 represents an optional
interval variable whose status has still not been fixed: 0 for an absent interval variable and 1 for a present interval variable.
The remaining fields describe the position of the interval variable, it is omitted if the interval variable is absent as this information is not relevant in this case. Thus, an absent interval variable is displayed as:
A1[0]
When the interval variable is possibly present:
Note that the second range may be omitted in case the size and length of the interval variable are necessarily equal.
When the values are fixed, the ranges min..max are replaced by a single value. For instance, the following display represents a fixed interval variable of size 5 that is present, starts at 10 and ends at 35:
A1[1: 10 -- (5)25 --> 35]