Chains of optional intervals

Though there are various methods for modeling a chain of optional interval variables, an efficient method is recommended.

Sometimes it is necessary to model a chain of n optional intervals for which, only the first k (k<=n) will be present where k is an implicit decision of the problem.

For instance, this is useful for modeling a preemptive activity that can be split into at most n parts. In the following sample, there are the additional constraints that each “part” of the activity has specified a minimal (pmin) and a maximal duration (pmax) and that the total duration (size) of the parts must equal the processing time pt of the preemptive activity. Note that when the part i is absent, the value returned by IloSizeOf(part[i]) will be 0 (this is the default value when no argument is passed to the expression), thus it will not be counted in the sum.

IloIntExpr totalSize(env);
IloIntervalVarArray part(env,n);
part[0] = IloIntervalVar(env, pmin, pmax, IloTrue);
totalSize += IloSizeOf(part[0]);
for (IloInt i=1; i < n; i++) {
  part[i] = IloIntervalVar(env, pmin, pmax,IloTrue);
  totalSize += IloSizeOf(part[i]);
  m.add(IloIfThen(env,IloPresenceOf(env,part[i]),IloPresenceOf(env,part[i-1])));
  m.add(IloEndBeforeStart(env,part[i-1],part[i]);
}
m.add(totalSize == pt);

Another example is a set of at most n flexible shifts for a worker with specific constraints on the shift duration and minimal resting time between shifts (see Different uses of the alternative constraint).