Originally posted by: AlCPLEX

Hello,

I have a come across something i am not sure to understand :

Those two formulations seem to have different performances (they are coded inside a quite big model i pefer not to rewrite here) :

• formulation 1) presenceOf(intervalA) == (a==1) + (a==2)*(b==1)
• formulation 2) presenceOf(intervalA) == (a==1) || (a==2) && (b==1)

Apparently the first formulation using expression of integers leads to less fails (and better speed) then the second one using booleans.

How is it explainable? At first i thought i might be because the first one was relaxed and not the second one but after turning off relaxation for those two (i unlabelled them and put relaxation option only on labelled ones), it does not seem to be that.

Any Idea? Maybe i am missing something basic here?

Thanks a lot,

Alexis

Originally posted by: GGR

Hi Alexis

Hi Alexis

I think you understand the two formulation are not equivalent. Formulation 1 is more "constraining" (as less solution as it states am exclusive disjunction between the two terms of the left hand side if intervalA is present.

Then It is not a surprised that a more constrained problem is easier to solve in practice fro bib size (or real life) problems. In fact reducing the search space by well selected constraint is a classical technique in combinatorial optimization. This comes from the fact that incumbent from the over constrained problem is eventuality  found faster and can be used as starting point of the original problem.

Hope that helps

Originally posted by: AlCPLEX

Hello GGR, thanks for your quick answer.

To be sure i really understand  :

The formulation 1) is an exclusive disjunction as presenceOf can only take a value in {0,1}, so in the right hand side either "(a==1)" is true or "(a==2)*(b==1)".

Whereas is formulation 2), "(a==1)"  and " (a==2) && (b==1) " could be true as a logical "or" is used.

So the propagation does not realize that in formulation 2) "(a==1)" and " (a==2) && (b==1) " cannot be simultaneously true as the variable "a" can have only one value (and not be equal to 1 and to 2 simultaneously).

As the first formulation is a disjunction and is in general more constraining (though not in this case because of the specific values), the algorithm coded behind propagates better.

Is that it?

Thanks a lot

Originally posted by: PhilippeLaborie

Yes, I think you get it right.

One additional thing: with CP Optimizer you may be able to get an even stronger inference in the engine by creating additional interval variables that correspond to the cases your variables a and b have specific values. For instance if a==1 and a==2 correspond to two different modes for executing your (optional) activity itv, you may create two optional interval variables (say itv1 and itv2) that respectively correspond to a==1 and a==2 and you add a constraint alternative(itv,[itv1,itv2]). This way, the engine will maintain the conditional domain of the interval variables itv1 and itv2 (assuming a==1 and a==2 respectively) and this may lead to stronger propagation. And in many cases, you may even not need the integer variables anymore.

Philippe