AddNoOverlap with Optional Intervals

An optional interval is a scheduling interval whose existence is governed by a Boolean variable $p_i,$ called its presence literal. When $p_i = \text{True},$ the interval is present and occupies the half-open window $[s_i, e_i)$ on the resource; when $p_i = \text{False},$ the interval is absent and contributes nothing to the schedule.

The AddNoOverlap constraint, applied to a list of intervals on a single machine, now requires only that any two present intervals be non-overlapping:

$$p_i \land p_j \;\Longrightarrow\; (e_i \le s_j) \;\lor\; (e_j \le s_i).$$

Absent intervals impose no restriction. Adding optional intervals to a model can therefore never turn a feasible schedule into an infeasible one — it only enlarges the search space.

For example, consider three optional intervals on one machine:

• $A$: $[2, 5),$ presence $p_A$
• $B$: $[4, 7),$ presence $p_B$
• $C$: $[6, 9),$ presence $p_C$

The assignment $p_A = T,\ p_B = F,\ p_C = T$ is feasible: the only present intervals are $A$ and $C,$ and $5 \le 6,$ so they don't overlap. The assignment $p_A = T,\ p_B = T,\ p_C = F$ is infeasible because $A$ and $B$ are both present and overlap on $[4, 5).$