Originally posted by: DavidGravot

Hi

Assume I have a sequence of optional intervals, each of them having a type. In the solution, intervals may eventually overlap

I want to forbid consecutive intervals of same type

Since intervals of different type may eventually overlap, I created artificial intervals of duration 1 starting with the original intervals and with same presence

I created a noOverlap constraint on these intervals with a transition 0 between any types except on the diagonal where the transition time is a big M that practically forbids the transition of the same type

Is it an efficient modeling ? This double the number of intervals and adds a noOverlap that is actually used only to forbid the transition of same type .

Thanks

David

Hi,

to forbid the transition of same type I would try typeOfNext

regards

Originally posted by: DavidGravot

Thanks

Nice idea since it may save the burden of artificial intervals, but I would have then to kind of "simulate" the link between chronological order and sequence type order (which is naturally infered by noOverlap constraint)

Originally posted by: PhilippeLaborie

Hi David,

Yes, if all the starting times are supposed to be different and if you want to forbid consecutive starting times between activities of the same type, the model you propose with unit duration interval variables and large transition times for infeasible transitions is the one to start with. Do not forget that your transition distance matrix must be applied only on direct successors (next interval variables), so you should use a constraint noOverlap(sequence, transitionDistance, onNext=True).

Originally posted by: DavidGravot

I wrote a tiny example for each formulation

using CP;

//initial data
tuple Slot{   int start;      int end;        int station;}
{Slot} slots = {  <10,14,1>,        <12,15,1>,        <13,18,2>};

//transitions   
{int} stations = { s.station | s in slots};
tuple Transition { int station1 ; int station2 ; int duration;};
{Transition} transitions = { <s1, s2, (s1==s2?10000 : 0)> | s1 in stations, s2 in stations};  
        
dvar interval slotsItv[s in slots]  optional in s.start .. s.end size (s.end-s.start);
dvar interval startSlots[s in slots] optional in s.start .. (s.start+1) size 1;

dvar sequence stationsSeq in all(s in slots) startSlots[s] types all(s in slots) s.station;

maximize sum(s in slots) presenceOf(slotsItv[s]);

constraints{
        noOverlap(stationsSeq,transitions);
        forall(s in slots)
          presenceOf(slotsItv[s]) == presenceOf(startSlots[s]);
}

and the second one without noOverlap : 

using CP;

//initial data
tuple Slot{  int start;      int end;        int station;}
{Slot} slots = {       <10,14,1>,        <12,15,1>,        <13,18,2>};

dvar interval itv[s in slots]  optional in s.start .. s.end size (s.end-s.start);
dvar sequence stationsSeq in all(s in slots) itv[s] types all(s in slots) s.station;


maximize sum(s in slots) presenceOf(itv[s]);

constraints{
        forall(s in slots)
          startOf(itv[s]) <=  startOfNext(stationsSeq, itv[s], s.start);
          
        forall(s in slots)
          typeOfNext(stationsSeq, itv[s], s.station+1, s.station+1) != s.station;
}

Both finds the optimal solution of 2 slots, the second one with 26 branches and 11 fails, while the first one has 14 branches and 11 fails