Optional Intervals and Presence Literals

An optional interval is an interval variable that may or may not be scheduled. Each optional interval carries a Boolean presence literal $p \in \{0, 1\}$:

• If $p = 1$, the interval is present, and its variables must satisfy the usual size relation $\text{start} + \text{size} = \text{end}$.
• If $p = 0$, the interval is absent, and is ignored by every constraint involving it.

We denote an optional interval by the tuple $I = (s, d, e, p)$, where $s$ is the start, $d$ is the size, $e$ is the end, and $p$ is the presence literal.

The defining rule of an optional interval is

$$p = 1 \;\Longrightarrow\; s + d = e.$$

When $p = 0$, the start, size, and end variables may still take any values in their domains, but those values have no effect on the rest of the model.

For example, suppose $s \in [0, 6]$, $d \in [2, 4]$, $e \in [0, 10]$, $p \in \{0, 1\}$. Then:

• $(s, d, e, p) = (1, 3, 4, 1)$ is valid: $p = 1$ and $1 + 3 = 4$. $\checkmark$
• $(s, d, e, p) = (1, 3, 5, 1)$ is invalid: $p = 1$ but $1 + 3 \neq 5$. $\times$
• $(s, d, e, p) = (1, 3, 5, 0)$ is valid: $p = 0$, so the relation $s + d = e$ need not hold. $\checkmark$