Topic
  • 2 replies
  • Latest Post - ‏2014-01-23T17:39:37Z by davidoff
davidoff
davidoff
51 Posts

Pinned topic splitting disjoint intervals into consecutive sets of intervals

‏2014-01-22T23:27:40Z |

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

 

Attachments

Updated on 2014-01-23T13:12:52Z at 2014-01-23T13:12:52Z by davidoff
  • PhilippeLaborie
    PhilippeLaborie
    68 Posts
    ACCEPTED ANSWER

    Re: splitting disjoint intervals into consecutive sets of intervals

    ‏2014-01-23T08:44:21Z  

    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

  • PhilippeLaborie
    PhilippeLaborie
    68 Posts

    Re: splitting disjoint intervals into consecutive sets of intervals

    ‏2014-01-23T08:44:21Z  

    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

  • davidoff
    davidoff
    51 Posts

    Re: splitting disjoint intervals into consecutive sets of intervals

    ‏2014-01-23T17:39:37Z  

    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

    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]);     
        }