Originally posted by: davidoff

Hello , I try to gather consecutive intervals into consecutive subset of intervals

Suppose I have 3 fixed non-optional consecutive disjoint intervals T1=[2,5) , T2 = [10,11), T3=[20,26)

I want to model some optional intervals W1,W2,W3 whose value could be finally :

W1=[2,5), W2=[10,11), W3=[20,26), or

W1=[2,5), W2=[10,26), or

W1=[2,11), W2=[20,26), or

W1=[2,26)

Basically, in the solution, the active Wj are consecutive disjoint intervals that spans a set of consecutive Ti, and all the Ti intervals are spanned with the Wj

I found a way to do that with stateFunction associated with a chronological set of "work" intervals Wj followed by "idle" intervals Yj. I constraint the Idle function to be in the state 1 for every hole between the Ti, and each Yj is also associated with the same state synchronized with the hole.

Reversely, I have an other stateFunction "Active" that is in state 1 for every Ti and also in state 1 for every Wj. Nevertheless , begin of Wj and end of Wj are synchronized separately with the state function so that an interval Wj will be authorized to join more than one working interval.

Finally, I use a cumul function to force that for any Ti, the cumul function of W is 1.

The model works fine but I'm surprized that I get more than one solution when I set the parameter "force" to 1. This parameter forces the two holes Y1 and Y2 to be present between T1 and T2 for Y1 , T2 and T3 for Y2. In this situation, when I display all the informations about decision variables and stateFunction, I get exactly the same results but the nextSolution iterates several times.

Besides, I'm wondering if they are simpler model for this problem.

Thanks
David

Originally posted by: PhilippeLaborie

Hello David,

I think your idea of using state functions is good. The idea is to synchronize the holes Yi between intervals Wi, Wi+1with the fixed holes between the T_j. Do you really need 2 state functions? If you use 1 stateFunction with fixed value: 1 over the T_j and aligned value 0 between the T_j, then if you state the idle intervals Y_i requires aligned state 0, it seems to me that would be enough. I'm assuming length of optional intervals Y_i is the min length of holes between the T_j and Y_i is constrained to start at the end of Wi and end at the start of Wi+1. Of course, you need constraints presenceOf(Wi)==presenceOf(Yi) and presenceOf(Wi+1)=>presenceOf(Wi). Maybe the second state function can help as a redundant constraint, indeed.

Now, about your second question. Enumerating solutions in scheduling is a bit tricky. First, you should make sure (like for search on integer variables) that your are using DepthFirst search type and that you are using a single worker. But even in these conditions, if you are using interval variables, it may be that the same solution is generated twice. If you really need to iterate over solutions without any duplicate, the best would be to filter identical solutions yourself.

Hope it helps,

Philippe

Originally posted by: davidoff

Thanks Philippe

Your idea works very well indeed. It generates the same set of solutions, with less duplicates .

Your idea

**************** Final solution ********************
<2 5><10 11><20 26>
<2 5><10 26>
<2 11><20 26>
<2 26>
 ! ----------------------------------------------------------------------------
 ! Search terminated normally, 53 solutions found.
 ! Number of branches     : 130
 ! Number of fails        : 12
 ! Total memory usage     : 2.1 MB (1.8 MB CP Optimizer + 0.3 MB Concert)
 ! Time spent in solve    : 0.18s (0.18s engine + 0.00s extraction)
 ! Search speed (br. / s) : 693.3
 ! ----------------------------------------------------------------------------

My implementation

**************** Final solution ********************
<2 5><10 11><20 26>
<2 5><10 26>
<2 11><20 26>
<2 26>
 ! ----------------------------------------------------------------------------
 ! Search terminated normally, 149 solutions found.
 ! Number of branches     : 310
 ! Number of fails        : 6
 ! Total memory usage     : 2.5 MB (1.9 MB CP Optimizer + 0.6 MB Concert)
 ! Time spent in solve    : 0.35s (0.35s engine + 0.00s extraction)
 ! Search speed (br. / s) : 862.6
 ! ----------------------------------------------------------------------------

Curiously, I improved the performances using the following relations between W and Y chain :

   if(true){ //better performances
         forall(j in 2 .. n){
             presenceOf(W[j]) => presenceOf(W[j-1]);
             presenceOf(W[j]) => presenceOf(Y[j-1]);
           }     
           forall(j in 2 .. n-1){
             presenceOf(Y[j]) => presenceOf(Y[j-1]);
             presenceOf(Y[j]) => presenceOf(W[j+1]);
           }   
   }else{  //less good
           forall(j in 2 .. n)
             presenceOf(W[j]) => presenceOf(W[j-1]);
           forall(j in 1 .. n-1)
             presenceOf(W[j]) == presenceOf(Y[j]);     
    }