Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only
Back to discussions
Expand all | Collapse all

How to make slots all different ? - Timetabling problem

  • 1.  How to make slots all different ? - Timetabling problem

    Posted Wed January 01, 2014 02:10 PM

    Originally posted by: Esin


    Hi, I need serious and urgent help about my course timetabling problem.

     * I have an array  for patterns that  each element has a different size. For first element, 1,5 and 10 are slots of this pattern which I can't define.

    When I call patterns([1][3]) I can get 10. And since I set array as int patterns[pattern][5] , it fulfills the array as [1,5,10,0,0]  and so on. 

    My problem is; decision varible x has to be assigned to a pattern in this array(from 1 to 7 ) for each course but, all slots for these courses must be different from each other for no conflicts.

    I need the slots of patterns that assingned to each courses should be all different.

    patterns= [

    [1,5,10]
    [5]
    [2]
    [3,4]
    [10,11]
    ];

    Therefore I try to use these decision variable in subject to part as

    allDifferent( all(c in courses, p in pattern )  patterns [x[c]][p] );

    But since it reads my pattern as [1,5,10,0,0] and [5,0,0,0,0]... I got "patterns [x[c]][p]" unlimited warning. 

    Because 0s can not be different in this condition. But I couldn't say that do it for all variables that not equal to 0. 

    How can I do it ?

    If it is not possible for allDifferent how can I replace that  ?

    Programme does not allow me to use my decision variable in allDifferent input, is that somehow possible ?

    for ex: 

    allDifferent( all(i in abcd,j in courses : (i>(x[j]-1) * 5) && (i<(x[j]* 5+1)) && (patternler[i] != 0) )
    patterns[i]);

    which x is decision variable and patterns[i] is an array 

     

    Correct assignment of x should be 3,1,4 after this constraint but it is 2,1,4 now.

     

    I'm adding and attaching my  files. 

    Can you please give me an advice ? 

    Thank you for your time. 

    DAT

    nbcourse = 3;

    nbpatterns = 7;
    nbmaxslot =5; 
    hour= [1,3,2] ;
    patternsize =[3,1,1,2,2]; 
     
    patterns = [
    [1,5,10]
    [3]
    [2]
    [3,4]
    [10,11]
    ];
     

    MOD

    using CP;
     
    int nbcourse = ...;
    int nbpatterns = ...;
    int nbmaxslot= ...;
     
    range courses = 1..nbcourse;
    range pattern = 1..nbpatterns;
    range maxslot = 1..nbmaxslot;
     
    int patternsize[pattern]=...;
    int hour[courses]= ...;
    int patterns[pattern][maxslot]= ...;
     
    dvar int x[courses] in pattern;
     
    execute {
      cp.param.FailLimit=100;
      cp.param.timeLimit=30;
    }
     
    subject to {
    allDifferent (x);
     
    forall (i in courses){
      hour[i] == patternsize[x[i]];}
      
     
    allDifferent( all(c in courses, p in maxslot ) 
    patterns [x[c]][p] );

    }


    #CPOptimizer
    #DecisionOptimization


  • 2.  Re: timetabling problem and allDifferent Method

    Posted Wed January 01, 2014 05:38 PM

    Originally posted by: Esin


    Hi again,

    I changed the last constraint above but it still does not work.

    I am new  and I couldn't  debug my code, therefore I have a guess about where the problem is.

    I would be appraciated if you tell me how to debug step by step. (Sorry I couldn't find in topics)

    About my guess, this model can not find any values.With my last constraint which try to make all elements of patterns array, 

    I used forall but I am not sure if I used it in correct manner. In second line I used a condition, to do it just elements that not equal to zero. But if element is equal to zero, does it block all the others or not ? How can I fix it ?

    Names of variables could be different but this is the exact same problem with my first message. 

     forall(j in courses){
       forall(n in dersinslotlari:patternler[j,n] !=0){
          forall(k in courses:k>j){
           forall(m in dersinslotlari){
              patternler[dersler[j],n]!= patternler[dersler[k],m];
            }
          }
       }
      }

    MOD

    using CP;

    //int nbpools = ...;
    int nbcourses = ...;
    range courses = 1..nbcourses;
    int nbpatterns = ...;
    range patterns = 1..nbpatterns;
    int dersinslotsayisi= ...;
    range dersinslotlari = 1..dersinslotsayisi;
    int nbslots = ...;
    int patternuzunluk[patterns]=...;
    int saat[courses]= ...;
    int patternler[patterns, dersinslotlari]=...;
     
    dvar int dersler[courses] in patterns;
     
    subject to{
      
      allDifferent(all(i in courses) dersler[i]);
      
      forall (i in courses){
        saat[i]==patternuzunluk[ dersler[i]];
    }  
      forall(j in courses){
       forall(n in dersinslotlari:patternler[j,n] !=0){
          forall(k in courses:k>j){
           forall(m in dersinslotlari){
              patternler[dersler[j],n]!= patternler[dersler[k],m];
            }
          }
       }
      }
    }
     

    DAT

    nbcourses = 3;

    nbpatterns = 5;
    nbslots = 40;
    dersinslotsayisi = 5; 
    //pool=[1,2,3];
    saat = [1,3,2] ;
    patternuzunluk=[3,1,1,2,2];
    patternler = [
    [1,5,10]
    [5]
    [2]
    [3,4]
    [10,11]
    ];

     


    #CPOptimizer
    #DecisionOptimization


  • 3.  Re: timetabling problem and allDifferent Method

    Posted Thu January 02, 2014 04:11 AM

    Originally posted by: Esin


    I want to ask again, to constract my model I need to use my decision variable in allDifferent or forall input  as a condition in constraints.

    It is obviously illegal. But I need this information for my constraint. 

    Can you help me to find an alternative way ? 

    I am sorry, I  am sending messages over and over again, but I am kind of desperate because of this model..

     


    #CPOptimizer
    #DecisionOptimization


  • 4.  Re: timetabling problem and allDifferent Method

    Posted Thu January 02, 2014 10:11 AM

    Originally posted by: Philippe_Refalo


    Esin, 
     
    If I understand well, at least all the x variables must be different. But you have more constraints due to slots appearing in several patterns. A possible (not tested) way to go is to use count constraints to count the occurrences of each pattern pi :
     
    ui  = count([x1, ..., xn], pi) where ui is a 0-1 variable.
     
    These constraints state the alldifferent constraint on x1...xn variables.
     
    But you need to add  this:
     
    for every slot a, let P be the set of patterns containing slot a, the sum of ui, such that pi is in P must be less ot equal to 1.
     
    This ensures that a slot is taken once. There might be stronger formulation but I believe this should do the job.  
     
    Philippe

    #CPOptimizer
    #DecisionOptimization


  • 5.  Re: timetabling problem and allDifferent Method

    Posted Sat January 04, 2014 07:16 AM

    Originally posted by: Esin


    Thank you Philippe, 

    I get the idea, I am trying to do it. 

    Also, when I expand the data with more courses and patterns, It will become infeasible to use each slot for once. (Because there are only 40 slots which is the product of 8 hours per day and 5 days per week ) 

    I have to change it as a soft constraint just like we do in goal programming (assingnin some punishments on every conflict and minimize the punishment )

    Are there any special method to do that, or am I have to do it in that way ? 

     Maybe If I can do what you suggested, sum of slots must be less or equal to 2 that may work with large data .

     Now I have to work hard on it  :)


    #CPOptimizer
    #DecisionOptimization


  • 6.  Re: How to make slots all different ? - Timetabling problem

    Posted Sat January 04, 2014 05:16 PM

    Originally posted by: Esin


    Hello again,

    I am trying to do that but getting some syntax errors, How can I fix them ? 

    MOD

    using CP;

    int nbcourses = ...;
    int nbpatterns = ...;
    int nbmaxslot = ...;
    int nbslots = ...;
     
    range courses = 1..nbcourses;
    range pattern = 1..nbpatterns;
    range maxslot = 1..nbmaxslot;
    range slots=1..nbslots;
     
    //int slotlist[slots]=...;
    int patternsize[pattern]=...;
    int hour[courses]= ...;
    int patterns[pattern,maxslot]=...;
     
    dvar int x[courses] in pattern;
    //dvar int y[slots]in 0..2; 
     
    subject to{
      
      allDifferent(all(i in courses) x[i]);
      
      forall (i in courses){
        hour[i]==patternsize[x[i]];
      }
     
    //forall (s in slots){
    //sum(i in courses)count((j in maxslot)patterns[x[i]][j],s))==y[s]<=1;
    //forall (s in slots){
      //sum(i in courses)(count(j in maxslot) patterns[x[i]][j],s )<=1 ;
      
      forall (s in slots){
      sum(i in courses)(count(j in maxslot) patterns[x[i]][j],s )<=1 ;
    }
    }

     

    DAT

    nbcourses = 3;

    nbpatterns = 5;
    nbslots = 40;
    nbmaxslot = 5; 
    //slotlist=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40];
    hour = [1,2,3]; //each course needs a pattern which has that much slot
    patternsize=[1,2,3,3,3];
    patterns = [
    [1]
    [4,5]
    [4,7,8]
    [1,2,3]
    [14,15,16]
    ];
     

    #CPOptimizer
    #DecisionOptimization


Related Content