Originally posted by: PhilippeLaborie
Indeed there is long propagation because you are writing your precedence constraints on integer expressions so there is a slow propagation in your attached model between start2 >= start1-1 and start2 <= start1-2 and as the domain of the expression is very large it will take very long to get to the fix point.
CP Optimizer performs some negative cycle detection on interval variables so I think that you should better directly use precedence constraints on interval variables: startBeforeStart(interval1m, interval2m, -1) and startBeforeStart(interval2m, interval1m, +2). There are two reasons for preferring these precedence constraints:
1- It is easier to deal with the optional status of interval variables: if one of the two intervals is absent the constraint is automatically satisfied
2- It is better handled by the engine as these precedences are aggregated together in a temporal network that implements global algorithms to propagate them (like negative cysle detection)
In general CP Optimizer tries to reformulate things like start2>=start1-1 as precedence constraints but I guess that here, as the intervals are optional (even if in the end, they are present) it is a bit more complex and CP Optimizer cannot perform this reformulation automatically.
If, in your model, I replace your two constraint by:
model.add(IloStartBeforeStart(env, interval1m, interval2m, -1));
model.add(IloStartBeforeStart(env, interval2m, interval1m, +2));
It gives:
! ----------------------------------------------------------------------------
! Minimization problem - 4 variables, 4 constraints
! Problem found infeasible at the root node
! ----------------------------------------------------------------------------
! Search terminated normally, model has no solution.
! Number of branches : 0
! Number of fails : 1
! Total memory usage : 522.3 kB (480.6 kB CP Optimizer + 41.7 kB Concert)
! Time spent in solve : 0.01s (0.01s engine + 0.00s extraction)
# Extraction breakdown : 0.00s concert translation + 0.00s presolve
! Search speed (br. / s) : 0
! ----------------------------------------------------------------------------
This is explained in the User's Manual of CP Optimizer: CP Optimizer>CP Optimizer User's Manual>Designing scheduling models>Specifying precedence relations between interval variables:
Specifying precedence relations between interval variables
Though there are various methods for modeling a precedence between two interval variables, using a precedence constraint is recommended.
When modeling a precedence between two intervals, it is always better to use a precedence constraint (e.g. IloEndBeforeStart) rather than an arithmetical constraint (<=,<,==) between end and start expressions.
Using a precedence constraint avoids difficulties related with the optionality of intervals variables. For instance, IloEndBeforeStart(env,a,b) is generally not equivalent to IloEndOf(a) <= IloStartOf(b). Given the precedence constraint IloEndBeforeStart(env,a,b), if b is absent, then the constraint will be always true and have no impact on a, which is what is usually needed. Given the constraint IloEndOf(a) <= IloStartOf(b), if b is absent, then the constraint IloEndOf(a) <= 0 will be enforced, as 0 is the default value for IloSstartOf(b) when bis absent. The form of a constraint using expressions that is equivalent to the precedence constraint would be IloEndOf(a,IloIntervalMin) <= IloStartOf(b,IloIntervalMax).
Additionally, using a precedence constraint is more effective in the optimizer.
IloIntervalVar a(env);
a.setOptional();
IloIntervalVar b(env);
b.setOptional();
m.add(IloEndBeforeStart(env,a,b));
This model is not equivalent to:
IloIntervalVar a(env);
a.setOptional();
IloIntervalVar b(env);
b.setOptional();
m.add(IloEndOf(a) <= IloStartOf(b));
#CPOptimizer#DecisionOptimization