Originally posted by: 90WP_Grégory_Marlière

Dear all,

My objective is to synchronise the presence of sets of Intervals.

 

I noticed that I have not the same propagation when:

- I link the presence of the concerned intervals to a bool variable (bad propagation of the intervals values)

 

IloBoolVar* pres=new IloBoolVar(*_env);

_model->add( *pres == IloPresenceOf(*_env,(*_actIntervals)[idx1]]));

_model->add( *pres == IloPresenceOf(*_env,(*_actIntervals)[idx2]]));

_model->add( *pres == IloPresenceOf(*_env,(*_actIntervals)[idx3]]));

...

 

- I directly link the presence of intervals pair by pair (better propagation)

_model->add(IloPresenceOf(*_env, (*_actIntervals)[idx1]) == IloPresenceOf(*_env,(*_actIntervals)[idx2]) );

_model->add(IloPresenceOf(*_env, (*_actIntervals)[idx2]) == IloPresenceOf(*_env,(*_actIntervals)[idx3]) );

...

 

I'd like to understand why the result is not the same and the best practices in order to be able to conceive better models. 

 

Note: the intervals have IloStartAtEnd constraints between them and that's what I would like to be best propagated on the startmin and max values.

 

Thank you for your informations,

Grégory

#CPOptimizer
#DecisionOptimization

Originally posted by: PhilippeLaborie

Hi Gregory,

The propagation is indeed much better with the second model that directly uses the presence status from the intervals and do not introduce additional boolean variables.

The reason for that is that binary constraints on the presence status of interval variables (like: presenceOf(x)==presenceOf(y)) are recognized and aggregated by the CP Optimizer engine into a 2-SAT network in order to perform stronger inference. If you want more detail, this is explained in the following article [1]. So, the right way to model your problem is indeed by posting constraints presenceOf(x)==presenceOf(y) (or any other binary constraints like implications presenceOf(x)=>presenceOf(y) if needed) and this will propagate well, in particular with precedence constraints (as explained in the article).

[1] P. Laborie, J. Rogerie . Reasoning with Conditional Time-intervals. Proc. 21th International FLAIRS Conference (FLAIRS 2008). http://www.aaai.org/Papers/FLAIRS/2008/FLAIRS08-126.pdf

#CPOptimizer
#DecisionOptimization

Originally posted by: 90WP_Grégory_Marlière

Thank you very much for your answer and your very interesting paper.

So, in the same way, is there a preferable implementation than an IloAllowedAssignments on boolean variables which represent the presence of intervals?

 

Regards,

Grégory Marlière

 

#CPOptimizer
#DecisionOptimization

Originally posted by: PhilippeLaborie

I would say that it depends on what your "allowed assignment" table represents. If you can formulate the same constraint with only binary constraints between presence (pi==pj, pi==!pj, pi=>pj, pi=>!pj, !pi=>pj) then it will propagate better. You may also consider using the "alternative" constraint to say that there are several (alternative) ways to achieve something.

Philippe

#CPOptimizer
#DecisionOptimization