Resources

Scheduling a Major Basketball Conference (clp12)

/***************************************************************/
/*                                                             */
/*          S A S   S A M P L E   L I B R A R Y                */
/*                                                             */
/*    NAME: clp12                                              */
/*   TITLE: Scheduling a Major Basketball Conference (clp12)   */
/* PRODUCT: OR                                                 */
/*  SYSTEM: ALL                                                */
/*    KEYS: OR                                                 */
/*   PROCS: CLP, GANTT, SQL                                    */
/*    DATA:                                                    */
/*                                                             */
/* SUPPORT:                             UPDATE:                */
/*     REF:                                                    */
/*    MISC: Example 12 from the CLP Procedure chapter of the   */
/*          Constraint Programming book.                       */
/*                                                             */
/***************************************************************/

/****************************************************************/
/* First, find all possible patterns. Consider only time        */
/* constraints at this point. A pattern should be suitable      */
/* for any team. Do not consider individual teams yet.          */
/****************************************************************/
%macro patterns();

proc clp out=all_patterns findall;
   /* For date 1 to 18. */
   %do j = 1 %to 18;
      var h&j = [0, 1]; /* home */
      var a&j = [0, 1]; /* away */
      var b&j = [0, 1]; /* bye */

      /* A team is either home, away, or bye. */
      lincon h&j + a&j + b&j=1;
   %end;

   /*------------------------------------------------------------*/
   /* Criterion 1 - Mirroring Scheme                             */
   /*------------------------------------------------------------*/
   /* The dates are grouped into pairs (j, j1), such that each   */
   /* team plays the same opponent on dates j and j1.            */
   /* A home game on date j will be an away game on date j1      */
   %do j = 1 %to 18;
      %do j1 = %eval(&j+1) %to 18;
         %if ( &j=1 and &j1=8 ) or ( &j=2 and &j1=9 ) or
             ( &j=3 and &j1=12 ) or ( &j=4 and &j1=13 ) or
             ( &j=5 and &j1=14 ) or ( &j=6 and &j1=15 ) or
             ( &j=7 and &j1=16 ) or ( &j=10 and &j1=17 ) or
             ( &j=11 and &j1=18 ) %then
            lincon h&j = a&j1, a&j = h&j1, b&j = b&j1;;
      %end;
   %end;

   /*------------------------------------------------------------*/
   /* Criterion 2 - Initial and Final Home and Away Games        */
   /*------------------------------------------------------------*/
   /* Every team must play home on at least one of the first three dates. */
   lincon h1 + h2 + h3 >= 1;

   /* Every team must play home on at least one of the last three dates. */
   lincon h16 + h17 + h18 >= 1;

   /* No team can play away on both last two dates. */
   lincon a17 + a18 < 2;

   /*------------------------------------------------------------*/
   /* Criterion 3 - Home/Away/Bye Pattern                        */
   /*------------------------------------------------------------*/
   %do j = 1 %to 16;
      /* No team can have more than two away matches in a row.*/
      lincon a&j + a%eval(&j+1) + a%eval(&j+2) < 3;
      /* No team can have more than two home matches in a row.*/
      lincon h&j + h%eval(&j+1) + h%eval(&j+2) < 3;
   %end;

   /* No team can have more than three away matches or byes in a row.*/
   %do j = 1 %to 15;
      lincon a&j + b&j + a%eval(&j+1) + b%eval(&j+1) + a%eval(&j+2)
             + b%eval(&j+2) + a%eval(&j+3) + b%eval(&j+3) < 4;
   %end;

   /* No team can have more than four home matches or byes in a row.*/
   %do j = 1 %to 14;
       lincon h&j + b&j + h%eval(&j+1) + b%eval(&j+1) + h%eval(&j+2)
              + b%eval(&j+2) + h%eval(&j+3) + b%eval(&j+3) + h%eval(&j+4)
              + b%eval(&j+4) < 5;
   %end;

   /*------------------------------------------------------------*/
   /* Criterion 4 - Weekend Pattern                              */
   /*------------------------------------------------------------*/
   /* Each team plays four weekends at home. */
   lincon 0 %do j = 2 %to 18 %by 2; +h&j %end; =4;
   /* Each team plays four weekends away. */
   lincon 0 %do j = 2 %to 18 %by 2; +a&j %end; =4;
   /* Each team has 1 weekend with a bye  */
   lincon 0 %do j = 2 %to 18 %by 2; +b&j %end; =1;

   /*------------------------------------------------------------*/
   /* Criterion 5 - First Weekends                               */
   /*------------------------------------------------------------*/
   /* Each team must have home games or byes on at least two     */
   /* of the first five weekends.                                */
   lincon 0 %do j = 2 %to 10 %by 2; + h&j + b&j %end; >=2;

   /*------------------------------------------------------------*/
   /* Criterion 9 - (Partial)                                    */
   /*------------------------------------------------------------*/
   /* The team with a bye in date 1 does not play away on the    */
   /*    last date or home in date 17 (Wake)                     */
   /* The team with a bye in date 16 does not play away in       */
   /*    date 18 (Duke)                                          */
   lincon b1 + a18 < 2, b1 + h17 < 2, b16 + a18 < 2;

run;

%mend;

%patterns;


/*****************************************************************/
/* Determine all possible "pattern sets" considering only time   */
/* constraints.                                                  */
/* Individual teams are not considered at this stage.            */
/* xi - binary variable indicates pattern i is in pattern set    */
/*****************************************************************/

%macro pattern_sets();

data _null_;
   set all_patterns;
   %do i=1 %to 38;
      if _n_=&i then do;
         %do j=1 %to 18;
            call symput("h&i._&j", put(h&j,best.));
            call symput("a&i._&j", put(a&j,best.));
            call symput("b&i._&j", put(b&j,best.));
         %end;
      end;
   %end;
run;

proc clp out=pattern_sets findall;
   /* xi=1 if pattern i belongs to pattern set */
   var (x1-x38)= [0, 1];

   /* Exactly nine patterns per patterns set */
   lincon 0 %do i = 1 %to 38; + x&i %end;=9;

   /* time slot constraints */
   %do j = 1 %to 18;
      /* Four home games per time slot */
      lincon 0 %do i = 1 %to 38; + &&h&i._&j*x&i %end; =4;
      /* Four away games per time slot */
      lincon 0 %do i = 1 %to 38; + &&a&i._&j*x&i %end; =4;
      /* One bye per time slot */
      lincon 0 %do i = 1 %to 38; + &&b&i._&j*x&i %end; =1;
   %end;

   /* Exclude pattern pairs that do not support a meeting date */
   %do i = 1 %to 38;
      %do i1 = %eval(&i+1) %to 38;
         %let count=0;
         %do j=1 %to 18;
            %if ( (&&h&i._&j=0 or &&a&i1._&j=0) and
                  (&&a&i._&j=0 or &&h&i1._&j=0)) %then %do;
               %let count=%eval(&count+1);
            %end;
         %end;
         %if (&count=18) %then %do;
            lincon x&i+x&i1<=1;
         %end;
      %end;
   %end;
run;

%mend;

%pattern_sets;


/*********************************************************************/
/* Assign individual teams to pattern set k                          */
/* Teams: 1 Clem, 2 Duke, 3 FSU, 4 GT, 5 UMD, 6 UNC, 7 NCSU, 8 UVA,  */
/*        9 Wake                                                     */
/*********************************************************************/
%macro timetable(k);

proc clp out=ACC_ds_&k varselect=minrmaxc findall;

   %do j = 1 %to 18;
      /*  alpha(i,j): Team i's opponent on date j ( 0 = bye ). */
      %do i = 1 %to 9;
         var alpha&i._&j = [0, 9];
      %end;

      /* Timetable constraint 1 */
      /* Opponents in a time slot must be distinct */
      alldiff ( %do i = 1 %to 9; alpha&i._&j %end; );

      /* Timetable constraint 2 */
      %do i = 1 %to 9;
         %do i1 = 1 %to 9;
            /* indicates if teams i and i1 play in time slot j */
            var X&i._&i1._&j = [0, 1];
            reify X&i._&i1._&j: (alpha&i._&j = &i1);

            /* team i plays i1 iff team i1 plays i */
            %if (&i1 > &i ) %then %do;
               lincon X&i._&i1._&j = X&i1._&i._&j;
            %end;
         %end;
      %end;
   %end;
   /* Mirroring Scheme at team level.                         */
   /* The dates are grouped into pairs (j, j1) such that each */
   /* team plays the same opponent in dates j and j1.         */
   /* One of these should be a home game for each team.       */
   %do i = 1 %to 9;
      %do j = 1 %to 18;
         %do j1 = %eval(&j+1) %to 18;
            %if ( &j=1 and &j1=8 ) or ( &j=2 and &j1=9 ) or
                ( &j=3 and &j1=12 ) or ( &j=4 and &j1=13 ) or
                ( &j=5 and &j1=14 ) or ( &j=6 and &j1=15 ) or
                ( &j=7 and &j1=16 ) or ( &j=10 and &j1=17 ) or
                ( &j=11 and &j1=18 ) %then %do;
               lincon alpha&i._&j=alpha&i._&j1,
               /* H and A are matrices that indicate home */
               /* and away games                          */
               H&i._&j=A&i._&j1,
               H&i._&j1=A&i._&j;
            %end;
         %end;
      %end;
   %end;

   /* Timetable constraint 3 */
   /* Each team plays every other team twice */
   %do i = 1 %to 9;
      %do i1 = 1 %to 9;
         %if &i1 ne &i %then %do;
            lincon 0 %do j = 1 %to 18; + X&i._&i1._&j %end; = 2;
         %end;
      %end;
   %end;

   /* Timetable constraint 4 */
   /* Teams do not play against themselves */
   %do j = 1 %to 18;
      %do i = 1 %to 9;
         lincon alpha&i._&j<>&i;
         lincon X&i._&i._&j = 0;  /* redundant */
      %end;
   %end;

   /* Timetable constraint 5 */
   /* Setup Bye Matrix */
   /* alpha&i._&j=0 means team &i has a bye on date &j. */
   %do j = 1 %to 18;
      %do i = 1 %to 9;
         var B&i._&j = [0, 1]; /*Bye matrix*/
         reify B&i._&j: ( alpha&i._&j = 0 );
      %end;
   %end;

   /* Timetable constraint 6 */
   /* alpha&i._&j=&i1 implies teams &i and &i1 play on date &j */
   /* It must be a home game for one, away game for the other  */
   %do j = 1 %to 18;
      %do i = 1 %to 9;
         %do i1 = 1 %to 9;
            /* reify control variables.*/
            var U&i._&i1._&j = [0, 1] V&i._&i1._&j = [0, 1];

            /* if &i is home and &i1 is away. */
            reify U&i._&i1._&j: ( H&i._&j + A&i1._&j = 2);
            /* if &i1 is home and &i is away. */
            reify V&i._&i1._&j: ( A&i._&j + H&i1._&j = 2);

            /* Necessary condition if &i plays &i1 on date j  */
            lincon X&i._&i1._&j <= U&i._&i1._&j + V&i._&i1._&j;
         %end;
      %end;
   %end;

   /* Timetable constraint 7 */
   /* Each team must be home, away or have a bye on a given date */
   %do j = 1 %to 18;
      %do i = 1 %to 9;
         /* Team &i is home (away) at date &j. */
         var H&i._&j = [0, 1] A&i._&j = [0, 1];
         lincon H&i._&j + A&i._&j + B&i._&j = 1;
      %end;
   %end;

   %do i = 1 %to 9;
      %do i1 = %eval(&i+1) %to 9;

         /* Timetable constraint 8 */
         /*-------------------------------------------------------*/
         /* Criterion 6 - Rival Matches                           */
         /*-------------------------------------------------------*/
         /* The final weekend is reserved for 'rival games' */
         /* unless the team plays FSU or has a bye          */
         %if ( &i=1 and &i1=4 ) or ( &i=2 and &i1=6 ) or
             ( &i=5 and &i1=8 ) or ( &i=7 and &i1=9 ) %then %do;
            lincon X&i._&i1._18 + B&i._18 + X&i._3_18 = 1;

            /* redundant */
            lincon X&i1._&i._18 + B&i1._18 + X&i1._3_18 = 1;
         %end;

         /* Timetable constraint 9 */
         /*-------------------------------------------------------*/
         /* Criterion 7 - Popular Matches                         */
         /*-------------------------------------------------------*/
         /* The following pairings are specified to occur at      */
         /* least once in February.                               */
         %if ( &i=2 and &i1=4 ) or ( &i=2 and &i1=9 ) or
             ( &i=4 and &i1=6 ) or ( &i=6 and &i1=9 ) %then %do;
            lincon 0 %do j = 11 %to 18; + X&i._&i1._&j  %end; >= 1;

            /* redundant */
            lincon 0 %do j = 11 %to 18; + X&i1._&i._&j %end; >= 1;
         %end;
      %end;
   %end;

   /* Timetable constraint 10 */
   /*-------------------------------------------------------*/
   /* Criterion 8 - Opponent Sequence                       */
   /*-------------------------------------------------------*/
   %do i = 1 %to 9;
      /* No team plays two consecutive away dates against   */
      /* Duke (2) and UNC (6)                               */
      %do j = 1 %to 17;
         var Q&i._26_&j = [0, 1] P&i._26_&j = [0, 1];
         reify Q&i._26_&j: ( X&i._2_&j +  X&i._6_&j = 1 );
         reify P&i._26_&j: ( X&i._2_%eval(&j+1) +  X&i._6_%eval(&j+1) =1 );
         lincon Q&i._26_&j + A&i._&j + P&i._26_&j + A&i._%eval(&j+1) < 4;
      %end;

      /* No team plays three consecutive dates against      */
      /* Duke(2), UNC(6) and Wake(9).                       */
      %do j = 1 %to 16;
         var L&i._269_&j = [0, 1] M&i._269_&j = [0, 1]
             N&i._269_&j = [0, 1];
         reify L&i._269_&j: ( X&i._2_&j +  X&i._6_&j +  X&i._9_&j = 1 );
         reify M&i._269_&j: ( X&i._2_%eval(&j+1) + X&i._6_%eval(&j+1) +
                              X&i._9_%eval(&j+1) =1 );
         reify N&i._269_&j: ( X&i._2_%eval(&j+2) + X&i._6_%eval(&j+2) +
                              X&i._9_%eval(&j+2) =1 );
         lincon L&i._269_&j + M&i._269_&j + N&i._269_&j  < 3;
      %end;
   %end;

   /* Timetable constraint 11 */
   /*-------------------------------------------------------*/
   /* Criterion 9 - Idiosyncratic Constraints               */
   /*-------------------------------------------------------*/
   /* UNC plays Duke in date 11 and 18 */
   lincon alpha6_11 = 2 ;
   lincon alpha6_18 = 2 ;
   /* UNC plays Clem in the second date. */
   lincon alpha6_2 = 1 ;
   /* Duke has a bye in date 16. */
   lincon B2_16 = 1 ;
   /* Wake does not play home in date 17. */
   lincon H9_17 = 0 ;
   /* Wake has a bye in the first date. */
   lincon B9_1 = 1 ;
   /* Clem, Duke, UMD and Wake do not play away in the last date. */
   lincon A1_18 = 0 ;
   lincon A2_18 = 0 ;
   lincon A5_18 = 0 ;
   lincon A9_18 = 0 ;
   /* Clem, FSU, and GT do not play away in the first date. */
   lincon A1_1 = 0 ;
   lincon A3_1 = 0 ;
   lincon A4_1 = 0 ;
   /* FSU and NCSU do not have a bye in the last date. */
   lincon B3_18 = 0 ;
   lincon B7_18 = 0 ;
   /* UNC does not have a bye in the first date. */
   lincon B6_1 = 0 ;

   /* Timetable constraint 12 */
   /*-------------------------------------------------------*/
   /* Match teams with patterns.                            */
   /*-------------------------------------------------------*/
   %do i = 1 %to 9; /* For each team */
      var p&i=[1,9];
      %do j=1 %to 18; /* For each date */
         element ( p&i, (&&col&k._h_&j), H&i._&j )
                 ( p&i, (&&col&k._a_&j), A&i._&j )
                 ( p&i, (&&col&k._b_&j), B&i._&j );
      %end;
   %end;
run;

%mend;

/**************************************************************/
/* Try all possible pattern sets to find all valid schedules. */
/**************************************************************/

%macro find_schedules;

proc transpose data=pattern_sets out=trans_good; run;

data _temp;
   set trans_good;
   set all_patterns;
run;

proc sql noprint;
   %do k = 1 %to 17; /* For each pattern */
      %do j=1 %to 18; /* For each date */
         select h&j into :col&k._h_&j
            separated by ',' from _temp where col&k=1;
         select a&j into :col&k._a_&j
            separated by ',' from _temp where col&k=1;
         select b&j into :col&k._b_&j
            separated by ',' from _temp where col&k=1;
      %end;
   %end;
run;

data all; run;

%do k = 1 %to 17; /* For each pattern set */
   %timetable(k=&k);

   data all;
      set all ACC_ds_&k;
   run;
%end;

data all;
   set all;
   if _n_=1 then delete;
run;

%mend;

%find_schedules;


/********************/
/* Generate report! */
/********************/

%macro acc_report;

%let Univ1 = Clem;
%let Univ2 = Duke;
%let Univ3 = FSU;
%let Univ4 = GT;
%let Univ5 = UMD;
%let Univ6 = UNC;
%let Univ7 = NCSU;
%let Univ8 = UVA;
%let Univ9 = Wake;

%let Clem=1;
%let Duke=2;
%let FSU=3;
%let GT=4;
%let UMD=5;
%let UNC=6;
%let NCSU=7;
%let UVA=8;
%let Wake=9;
%let Bye=0;

data schedule1997;
   set all;
   if (alpha&Clem._1 = &UMD) and
      (alpha&Duke._1 = &UVA) and
      (alpha&FSU._1 = &UNC) and
      (alpha&GT._1 = &NCSU) and
      (alpha&UMD._1 = &Clem) and
      (alpha&UNC._1 = &FSU) and
      (alpha&NCSU._1 = &GT) and
      (alpha&UVA._1 = &Duke) and
      (alpha&Wake._1 = &Bye)
      and
      (alpha&Clem._2 = &UNC) and
      (alpha&Duke._2 = &UMD) and
      (alpha&FSU._2 = &NCSU) and
      (alpha&GT._2 = &Bye) and
      (alpha&UMD._2 = &Duke) and
      (alpha&UNC._2 = &Clem) and
      (alpha&NCSU._2 = &FSU) and
      (alpha&UVA._2 = &Wake) and
      (alpha&Wake._2 = &UVA)
      and
      (alpha&Clem._3 = &Wake) and
      (alpha&Duke._3 = &NCSU) and
      (alpha&FSU._3 = &UMD) and
      (alpha&GT._3 = &UNC) and
      (alpha&UMD._3 = &FSU) and
      (alpha&UNC._3 = &GT) and
      (alpha&NCSU._3 = &Duke) and
      (alpha&UVA._3 = &Bye) and
      (alpha&Wake._3 = &Clem)
   then
       output;
run;

data report1997 (keep= %do i = 1 %to 9; &&Univ&i %end;);
   set schedule1997;
   format %do i = 1 %to 9;
             &&Univ&i $8.
          %end;
   ;
   %do j = 1 %to 18;
      %do i = 1 %to 9;
         %do i1 = 1 %to 9;
            if (alpha&i._&j = &i1) and (H&i._&j =1 ) then
               &&Univ&i= "&&Univ&i1";
            else if (alpha&i._&j = &i1) and (A&i._&j =1 ) then
               &&Univ&i= "@&&Univ&i1";
            else if (alpha&i._&j = 0) and (B&i._&j =1 ) then
               &&Univ&i= "Bye";
         %end;
      %end;
      output;
   %end;
run;

data printfirst;
   Date="Date"||strip(put(_n_,best.));
   set report1997;
run;

proc print; run;

%mend;

%acc_report;



%macro gantt;

%let Univ1 = Clem;
%let Univ2 = Duke;
%let Univ3 = FSU;
%let Univ4 = GT;
%let Univ5 = UMD;
%let Univ6 = UNC;
%let Univ7 = NCSU;
%let Univ8 = UVA;
%let Univ9 = Wake;
data pattern_color_map;
   format color $10.;
   %do i = 1 %to 9;
      _pattern = &i;
      color = "black";
      output;
   %end;
run;

%macro setPattern(count, color);
pattern&count. v=e color=&color repeat=1;
%mend setPattern;

%macro setPatterns(data=pattern_color_map);
data _null_;
   set &data;
   retain count 1;
   dummy = resolve('%setPattern('||count||','||color||')');
   call execute(dummy);
   count = count + 1;
run;
%mend setPatterns;

%setPatterns;

proc format;
   value stage
      0.5 = '1'
      17.5 = '18'
      18.5 = ' '
      ;
run;

data activity;
   format _label $6. act$5.;
   format s_start stage.;
   label act='Team';
   set schedule1997;
   keep _pattern _label segmt_no act s_start s_finish duration;
   retain duration 0.95;
   %do i = 1 %to 9;/* home teams.*/
      %do j = 1 %to 18; /* dates */
         if (alpha&i._&j = 0) and (B&i._&j =1 ) then do;
            s_start=.;
            s_finish=.;
            segmt_no = &j;
            _label = "";
            _pattern = .;
            act="&&Univ&i";
            output;
         end;
         else do;
            %do i1 = 1 %to 9;
               if (alpha&i._&j = &i1) and (H&i._&j =1 ) then do;
                  s_start=%eval(&j-1)+0.5;
                  s_finish=&j+0.45;
                  segmt_no = &j;
                  _label = "&&Univ&i1";
                  _pattern = &i;
                  act="&&Univ&i";
                  output;
               end;
               else if (alpha&i._&j = &i1) and (A&i._&j =1 ) then do;
                  s_start=%eval(&j-1)+0.5;
                  s_finish=&j+0.45;
                  segmt_no = &j;
                  _label = "@&&Univ&i1";
                  _pattern = &i1;
                  act="&&Univ&i";
                  output;
               end;
            %end;
         end;
      %end;
   %end;
run;

data labels;
   _y=-1;
   _lvar="_label";
   _xvar="s_start";
   _hlabel=1.0;
   _yoffset = -0.2;
   _xoffset = 0;
run;

title1 "ACC Basketball Tournament Scheduling";
proc gantt data=activity labdata=labels;
   chart /
      skip=3
      nojobnum
      nolegend
      chartwidth=95
      pcompress
      act=act
      duration=duration
      mindate=0.5
      useformat
      increment=1
      ;
   id act;
run;

%mend;

%gantt;