Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

sports-league.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-11-28 13:56:08 +0100 (Mon, 28 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2654 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */     
00021 
00022 #include "int.hh"
00023 #include "examples/support.hh"
00024 #include "minimodel.hh"
00025 
00032 struct Play {
00034   int h;
00036   int a;
00038   int g;
00039 };
00040 
00041 typedef PrimArgArray<Play> RRSArray;
00042 
00060 class SportsLeague : public Example {
00061 private:
00064   int t;            
00066   int weeks; 
00068   int eweeks;
00070   int periods;
00072   int season;
00074   int value;
00076   IntVarArray home;
00078   IntVarArray away;
00080   IntVarArray game;
00082   RRSArray rrs_array;
00083 protected:
00084   // return the number of digits of n
00085   int digit(int n) {
00086     int f = n;
00087     int fdigit = 0;
00088     while (f / 10) {
00089       fdigit++;
00090       f = f / 10;
00091     }
00092     return fdigit;
00093   }
00094 
00095   // printing function that makes the schedule more readable
00096   void blank(int n) {
00097     for (int d = digit(t) - digit(n); d--; ) {
00098       std::cout << " ";
00099     }
00100     std::cout << n;
00101   }
00102 
00103   void blankv(int n) {
00104     for (int d = digit(value) - digit(n); d--; ) {
00105       std::cout << " ";
00106     }
00107     std::cout << n;
00108   }
00109 
00110   void blank_only(int n) {
00111     for (int i = digit(n); i--; ) {
00112       std::cout << " ";
00113     }
00114   }
00115 
00116 public:
00118   IntVar& h (int p, int w) {
00119     return home[p * eweeks + w];
00120   }
00121 
00123   IntVar& a (int p, int w) {
00124     return away[p * eweeks + w];
00125   }
00126 
00131   IntVar& g (int p, int w) {
00132     return game[p * weeks + w];
00133   }
00134  
00139   Play& rrs(int p, int w) {
00140     return rrs_array[p * weeks + w];
00141   }
00142 
00152   int gn(int h, int a) {
00153     return (t * (h - 1) + a);
00154   }
00155 
00182   void init_rrs(void) {
00183 
00184     // Initialize the array 
00185     for(int p = 0; p < periods; p++)
00186       for (int w = 0; w < weeks; w++) {
00187         rrs(p, w).h = 0;
00188         rrs(p, w).a = 0;
00189         rrs(p, w).g = 0;
00190       }
00191     
00192     // Determine the first game (week 0 period 0)
00193     rrs(0, 0).h = 1;
00194     rrs(0, 0).a = 2;
00195     rrs(0, 0).g = 2;
00196 
00197     // Determine the other games of the first week
00198     for(int p = 1; p < periods; p++){
00199       rrs(p, 0).h = (p + 1) + 1;
00200       rrs(p, 0).a = t - (p + 1 - 2);
00201       rrs(p, 0).g = gn(rrs(p, 0).h, rrs(p, 0).a);
00202     }
00203 
00204     // Compute the games for the subsequent weeks
00205     for (int w = 1; w < weeks; w++) {
00206       for (int p = 0; p < periods; p++) {
00207         if (rrs(p, w - 1).h == t) {
00208           rrs(p, w).h = 2;
00209         } else {
00210           if (rrs(p, w - 1).h == 1) {
00211             rrs(p, w).h = 1;
00212           } else {
00213             rrs(p, w).h = rrs(p, w - 1).h + 1;
00214           }
00215         }
00216         if (rrs(p, w - 1).a == t) {
00217           rrs(p, w).a = 2;
00218         } else {
00219           rrs(p, w).a = rrs(p, w - 1).a + 1;
00220         }
00221 
00222         // maintain symmetry for (h, a): h < a
00223         if (rrs(p, w).h > rrs(p, w).a) {
00224           int buffer  = rrs(p, w).h;
00225           rrs(p, w).h = rrs(p, w).a;
00226           rrs(p, w).a = buffer;
00227         }
00228         rrs(p, w).g = gn(rrs(p, w).h, rrs(p, w).a);
00229       }
00230     }
00231   }
00232   
00233   SportsLeague(const Options& op) :
00234     t       (op.size), 
00235     weeks   (t - 1), 
00236     eweeks  (t), 
00237     periods (t / 2), 
00238     season  (weeks * periods), 
00239     value   (t * (t - 2) + t), 
00240     home    (this, periods * eweeks),
00241     away    (this, periods * eweeks),
00242     game    (this, season), 
00243     rrs_array     (periods * weeks){
00244 
00245     IntSet dom_all   (1, t);
00246     IntSet dom_game  (2, value);
00247     IntSet dom_home  (1, t - 1);
00248     IntSet dom_away  (2, t);
00249     IntSet dom_index (0, periods - 1);
00250     
00251     for (int i = eweeks * periods; i--; ) {
00252       home[i].init(this, dom_home);
00253       away[i].init(this, dom_away);
00254     }
00255     for (int i = season; i--; ) {
00256       game[i].init(this, dom_game);
00257     }
00258 
00259 
00260     // Initialize the round robin schedule
00261     init_rrs();
00262 
00263     //    domain for the gamenumber of period
00264     for (int w = 0; w < weeks; w++) {
00265       IntArgs gamenum(periods);
00266       IntArgs fst(periods);
00267       IntArgs snd(periods);
00268 
00269       for(int p = 0; p < periods; p++){
00270         gamenum[p] = rrs(p, w).g; 
00271         fst[p]     = rrs(p, w).h;
00272         snd[p]     = rrs(p, w).a;
00273       }
00274 
00275       IntVarArray n(this, periods, 0, periods - 1);
00276       distinct(this, n, ICL_DOM);
00277         
00278       for(int p = 0; p < periods; p++){
00279         element(this, gamenum, n[p], g(p, w), op.icl);
00280         element(this, fst,     n[p], h(p, w), op.icl);
00281         element(this, snd,     n[p], a(p, w), op.icl);
00282       }
00283     }
00284 
00285 
00292     // fix the first pair
00293     rel(this, h(0,0), IRT_EQ, 1);
00294     rel(this, a(0,0), IRT_EQ, 2);
00295 
00296     for (int p = 0; p < periods; p++) {
00297       for (int w = 0; w < eweeks; w++) {
00298         rel(this, h(p, w), IRT_LE, a(p, w));
00299       }
00300     }
00301 
00302     // home teams in the first week are ordered
00303     for (int p = 0; p < periods - 1; p++) {
00304       rel(this, h(p, 0), IRT_LE, h(p + 1, 0));
00305     }
00306     
00313     for(int w = 0; w < eweeks; w++ ) {
00314       IntVarArray col(this, t);
00315       int k = 0;
00316       for( int p = 0; p < periods; p++ ) {
00317         col[k] = h(p, w); 
00318         k++;
00319         col[k] = a(p, w);
00320         k++;
00321       }
00322       distinct(this, col, ICL_DOM);
00323     }
00324 
00333     for(int p = 0; p < periods; p++) {
00334       IntVarArray row(this, 2 * eweeks);
00335       for (int w = 0; w < 2 * eweeks; w +=2) {
00336         row[w]     = h(p, w / 2);
00337         row[w + 1] = a(p, w / 2);
00338       }
00339       gcc(this, row, 2, op.icl); // cardvars
00340     }
00341 
00342 
00343 
00344     for(int p = 0; p < periods; p++) {
00345       for(int w = 0; w < weeks; w ++) {
00346         post(this, t * h(p, w) + 1 * a(p, w) - 1* g(p, w) == t);
00347       }
00348     }
00349 
00350     distinct(this, game, ICL_DOM);
00351 
00352     branch(this, game, BVAR_NONE, BVAL_MIN);
00353 
00354   }
00355 
00356   SportsLeague(bool share, SportsLeague& s)
00357     : Example(share, s), 
00358       t(s.t), weeks(s.weeks), eweeks(s.eweeks), 
00359       periods(s.periods), season(s.season), 
00360       value(s.value), rrs_array(s.rrs_array) {
00361     home.update(this, share, s.home);
00362     away.update(this, share, s.away);
00363     game.update(this, share, s.game);
00364   }
00365   
00366   virtual Space* 
00367   copy(bool share) {
00368     return new SportsLeague(share, *this);
00369   }
00370 
00371   virtual void print(void){
00372     // print feasible schedule
00373     // t is the number of the greatest game
00374     std::cout << "\nSchedule for " << t << " teams"
00375               << " and "<< weeks << " weeks:" << std::endl;
00376     // print period index
00377     std::cout << " ";
00378     blank_only(t);
00379     std::cout << "     ";
00380     for (int p = 0; p < periods; p++) {
00381       blank_only(t);
00382       std::cout << "P[";
00383       blank(p);
00384       std::cout <<"]";
00385       blank_only(t);
00386     }
00387     std::cout <<"\n";
00388 
00389     // print entries
00390     for(int w = 0; w < weeks; w++){
00391       std::cout << "W["; 
00392       blank(w + 1); 
00393       std::cout <<"]: ";
00394       for(int p = 0; p < periods; p++){
00395         if (h(p, w).assigned() && a(p, w).assigned()) {
00396           std::cout <<" ";
00397           blank(h(p, w).val());
00398           std::cout <<",";
00399           blank(a(p, w).val());
00400           std::cout <<" ";
00401         } else {
00402           blank_only(t);
00403           std::cout << " x ";
00404           blank_only(t);
00405         }
00406       }
00407       std::cout << "\n";
00408     }
00409     std::cout << "\n";
00410 
00411     //print gamenumbers
00412     std::cout << "\nUnique game numbers:\n";
00413     std::cout <<"\n";
00414     for(int p = 0; p < periods; p++){
00415       std::cout << "Period[";
00416       blank(p + 1);
00417       std::cout <<"]: " ;
00418       for(int w = 0; w < weeks; w++){
00419         if (g(p, w).assigned()) {
00420           blankv(g(p, w).val());
00421           std::cout << " ";
00422         } else {
00423           for (int i = digit(value); i--; ) {
00424             std::cout << " ";
00425           }
00426           std::cout << " ";
00427         }
00428       }
00429       std::cout << "\n";
00430     }
00431     std::cout << "\n";
00432 
00433   }
00434 };
00435 
00436 
00437 int main(int argc, char** argv){
00438   Options o("Sports League Scheduling ");
00439   o.solutions = 1;
00440   o.size      = 18;
00441   o.parse(argc, argv);
00442   if (o.size == 4) {
00443     std::cerr<< "No Solution for t = 4!\n";
00444     return -1;
00445   } 
00446   if (o.size % 2 != 0) {
00447     std::cerr << "Number of t has to be even!\n";
00448     return -1;
00449   }
00450   Example::run<SportsLeague, DFS>(o);
00451   return 0;
00452 }
00453 
00454 // STATISTICS: example-any
00455