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

Interval variables in CP Optimizer

Basic interval variables |

Intensity and size and forbidden values |

Expressions over Interval Variables |

Display of interval variable domain |

Basic interval variables

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:

- optional activities (operations, tasks) that can be left unperformed (with an impact on the cost) : typical examples are externalized, maintenance, or control tasks,
- activities that can execute on a set of alternative resources (machines, manpower) with possibly different characteristics (speed, calendar) and compatibility constraints,
- operations that can be processed in different temporal modes (for instance in series or in parallel),
- alternative modes for executing a given activity where each mode specifying a particular combination of resources,
- alternative processes for executing a given production order where a process being specified as a sequence of operations requiring resources,
- hierarchical description of a project as a work-breakdown structure with tasks decomposed into sub-tasks, part of the project being optional (with an impact on the cost if unperformed), etc.

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:

- interval is
**absent**: = ; or - interval is
**present**: = [*s*,*e*)

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*.

Intensity and size and forbidden values

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.

**Forbidden start constraint**: The constraint*forbidStart(**, F)*, states that whenever the interval is present, it cannot start at a value*t*where*F(t)*= 0.**Forbidden end constraint**: The constraint*forbidEnd(**, F)*, states that whenever the interval is present, it cannot end at a value*t*where*F(t - 1)*= 0.**Forbidden extent constraint**: The constraint*forbidExtent(**, F)*, states that whenever the interval is present, it cannot overlap a point*t*where*F(t)*= 0.

More formally:

Expressions over Interval Variables

This section shows how to create numerical expressions from interval variables. These expressions can be used to:

- define a term for the cost function and
- connect interval variables to integer and floating point expressions.

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.

Display of interval variable domain

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:

- the first range in the remaining fields represents the domain of the interval start
- the second range (between parentheses) represents the domain of the interval size
- the third range represents the domain of the interval length
- the fourth and last range represents the domain of the interval end

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]