Efficient OR-Tools equivalent of the CPO "alternative" constraint

[Sycropane]

Hello,

In a context of scheduling, I am look for an efficient (in the sense "uses as many Or-Tools global constraints as possible") way to model the CPO "alternative" constraints. This constraint has the following behavior :

• Let X be an optional interval var (let x be the boolean of its presence/absence, "presence" corresponding to "1")
• Let Yi be a set of optional interval vars (let yi be the boolean variables of their presence/absence)
• alternative(X,Yi) is a constraint that ensures that {X is "present"} if and only if {exactly one interval is "present" in the Yi intervals and its start and end dates are synchronized with those of X}

How would you do it without efficiently ? Is there a direct and algorithmically optimized way to do it in Or-Tools CP-SAT solver ? Or should we simply rely on a "x = sum over i {yi}" and then on synchronization constraints conditioned by x with some BigM ?

Thank you !

[lperron]

This is not an issue. I moved it to discussions

[lperron]

Just look at the flexible jobshop python example.

Note, it does not use big-M as the solver naturally understands half reified constraints.

[lperron]

Now, you can go a bit deeper and look at the jobshop_sat.cc examples.
In particular, you can decide to share the start, and end variables between the main interval and its copies.

By default, as it is simpler, each copy has its own variables. Then you use the performed literal to enforce the synchronization between the main interval and the selected copy.

The sharing approach forces you to be very careful on the constraints between copies, as they need to be protected by the performed status of these copies.

At this point, it is unclear which version is faster.

[Sycropane]

Waw thanks this is very clear. I would have thought the sharing of the start and end variables would naturally have been the fastest method, especially on instances with a lot of alternatives per task, but I guess I’ll have to try the two approaches on my particular application and see. I’ll provide feedback here if I manage to achieve properly these tests.