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]
```