Generated on Mon May 10 06:46:30 2010 for Gecode by doxygen 1.6.3

sports-league.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Patrick Pekczynski, 2004
00011  *     Christian Schulte, 2007
00012  *
00013  *  Last modified:
00014  *     $Date: 2009-05-14 00:24:31 +0200 (Thu, 14 May 2009) $ by $Author: tack $
00015  *     $Revision: 9095 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 #include <gecode/driver.hh>
00043 #include <gecode/int.hh>
00044 #include <gecode/minimodel.hh>
00045 
00046 #include <algorithm>
00047 #include <iomanip>
00048 
00049 using namespace Gecode;
00050 
00052 class Play {
00053 public:
00054   int h; 
00055   int a; 
00056   int g; 
00057 };
00058 
00060 class RRS {
00061 protected:
00063   const int teams;
00065   Play* plays;
00067   int weeks(void) const {
00068     return teams-1;
00069   }
00071   int periods(void) const {
00072     return teams/2;
00073   }
00075   int gn(int h, int a) const {
00076     return teams*(h-1) + a;
00077   }
00079   Play& play(int p, int w) {
00080     return plays[p*weeks() + w];
00081   }
00082 public:
00108   RRS(int t) : teams(t), plays(new Play[periods()*weeks()])  {
00109     // Initialize array
00110     for (int p=0; p<periods(); p++)
00111       for (int w=0; w<weeks(); w++)
00112         play(p,w).h = play(p,w).a = play(p,w).g = 0;
00113 
00114     // Determine the first game (week 0 period 0)
00115     play(0,0).h = 1;
00116     play(0,0).a = 2;
00117     play(0,0).g = 2;
00118 
00119     // Determine the other games of the first week
00120     for (int p=1; p<periods(); p++) {
00121       play(p,0).h = (p + 1) + 1;
00122       play(p,0).a = teams - (p + 1 - 2);
00123       play(p,0).g = gn(play(p,0).h,play(p,0).a);
00124     }
00125 
00126     // Compute the games for the subsequent weeks
00127     for (int w=1; w<weeks(); w++) {
00128       for (int p=0; p<periods(); p++) {
00129         if (play(p,w-1).h == teams) {
00130           play(p,w).h = 2;
00131         } else if (play(p,w-1).h == 1) {
00132           play(p,w).h = 1;
00133         } else {
00134           play(p,w).h = play(p,w-1).h + 1;
00135         }
00136 
00137         if (play(p,w-1).a == teams) {
00138           play(p,w).a = 2;
00139         } else {
00140           play(p,w).a = play(p,w-1).a + 1;
00141         }
00142 
00143         // maintain symmetry for (h,a): h < a
00144         if (play(p,w).h > play(p,w).a)
00145           std::swap(play(p,w).h,play(p,w).a);
00146 
00147         play(p,w).g = gn(play(p,w).h,play(p,w).a);
00148       }
00149     }
00150 
00151   }
00153   void hag(int w, IntArgs& h, IntArgs& a, IntArgs& g) {
00154     for (int p=0; p<periods(); p++) {
00155       h[p] = play(p,w).h;
00156       a[p] = play(p,w).a;
00157       g[p] = play(p,w).g;
00158     }
00159   }
00161   ~RRS(void) {
00162     delete [] plays;
00163   }
00164 };
00165 
00166 
00167 
00184 class SportsLeague : public Script {
00185 protected:
00186   const int teams;  
00187   IntVarArray home; 
00188   IntVarArray away; 
00189   IntVarArray game; 
00190 
00192   int weeks(void) const {
00193     return teams-1;
00194   }
00196   int periods(void) const {
00197     return teams/2;
00198   }
00200   IntVar& h(int p, int w) {
00201     return home[p*teams + w];
00202   }
00204   const IntVar& h(int p, int w) const {
00205     return home[p*teams + w];
00206   }
00208   IntVar& a(int p, int w) {
00209     return away[p*teams + w];
00210   }
00212   const IntVar& a(int p, int w) const {
00213     return away[p*teams + w];
00214   }
00216   IntVar& g(int p, int w) {
00217     return game[p*weeks() + w];
00218   }
00220   const IntVar& g(int p, int w) const {
00221     return game[p*weeks() + w];
00222   }
00223 
00224 public:
00226   SportsLeague(const SizeOptions& opt) :
00227     teams(opt.size()),
00228     home(*this, periods() * teams, 1, weeks()),
00229     away(*this, periods() * teams, 2, weeks()+1),
00230     game(*this, weeks()*periods(), 2, teams*weeks())
00231   {
00232     // Initialize round robin schedule
00233     RRS r(teams);
00234 
00235     // Domain for gamenumber of period
00236     for (int w=0; w<weeks(); w++) {
00237       IntArgs rh(periods()), ra(periods()), rg(periods());
00238       IntVarArgs n(periods());
00239 
00240       for (int p=0; p<periods(); p++)
00241         n[p].init(*this,0,periods()-1);
00242       distinct(*this, n, opt.icl());
00243 
00244       r.hag(w,rh,ra,rg);
00245 
00246       for (int p=0; p<periods(); p++) {
00247         element(*this, rh, n[p], h(p,w));
00248         element(*this, ra, n[p], a(p,w));
00249         element(*this, rg, n[p], g(p,w));
00250       }
00251     }
00252 
00254     for (int p=0; p<periods(); p++)
00255       for (int w=0; w<teams; w++)
00256         rel(*this, h(p,w), IRT_LE, a(p,w));
00257 
00258     // Home teams in first week are ordered
00259     for (int p=0; p<periods()-1; p++)
00260       rel(*this, h(p,0), IRT_LE, h(p+1,0));
00261 
00262     // Fix first pair
00263     rel(*this, h(0,0), IRT_EQ, 1);
00264     rel(*this, a(0,0), IRT_EQ, 2);
00265 
00267     for (int w=0; w<teams; w++) {
00268       IntVarArgs c(teams);
00269       for (int p=0; p<periods(); p++) {
00270         c[2*p] = h(p,w); c[2*p+1] = a(p,w);
00271       }
00272       distinct(*this, c, opt.icl());
00273     }
00274 
00276     for (int p=0; p<periods(); p++) {
00277       IntVarArgs r(2*teams);
00278       for (int t=0; t<teams; t++) {
00279         r[2*t]   = h(p,t);
00280         r[2*t+1] = a(p,t);
00281       }
00282       IntArgs values(teams);
00283       for (int i=1; i<=teams; i++)
00284         values[i-1] = i;
00285       count(*this, r, IntSet(2,2), values, opt.icl());
00286     }
00287 
00288     // Redundant constraint
00289     for (int p=0; p<periods(); p++)
00290       for (int w=0; w<weeks(); w ++)
00291         post(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams);
00292 
00293     distinct(*this, game, opt.icl());
00294 
00295     branch(*this, game, INT_VAR_NONE, INT_VAL_SPLIT_MIN);
00296   }
00298   SportsLeague(bool share, SportsLeague& s)
00299     : Script(share, s), teams(s.teams) {
00300     home.update(*this, share, s.home);
00301     away.update(*this, share, s.away);
00302     game.update(*this, share, s.game);
00303   }
00305   virtual Space*
00306   copy(bool share) {
00307     return new SportsLeague(share, *this);
00308   }
00310   virtual void print(std::ostream& os) const {
00311     // print period index
00312     os << "\t       ";
00313     for (int p=0; p<periods(); p++) {
00314       os << "P[";
00315       os.width(2);
00316       os << p << "] ";
00317       }
00318     os << std::endl;
00319     // print entries
00320     for (int w=0; w<weeks(); w++) {
00321       os << "\tW[";
00322       os.width(2);
00323       os << w+1 << "]: ";
00324       for (int p=0; p<periods(); p++) {
00325         os.width(2);
00326         os << h(p,w).val() << '-';
00327         os.width(2);
00328         os << a(p,w).val() << " ";
00329       }
00330       os << std::endl;
00331     }
00332   }
00333 };
00334 
00335 
00339 int
00340 main(int argc, char* argv[]) {
00341   SizeOptions opt("Sports League Scheduling");
00342   opt.icl(ICL_DOM);
00343   opt.size(18);
00344   opt.parse(argc,argv);
00345   if (opt.size() < 5) {
00346     std::cerr<< "No Solution for less than 5 teams!" << std::endl;
00347     return 1;
00348   }
00349   if (opt.size() % 2 != 0) {
00350     std::cerr << "Number of teams has to be even!" << std::endl;
00351     return 1;
00352   }
00353   Script::run<SportsLeague, DFS,SizeOptions>(opt);
00354   return 0;
00355 }
00356 
00357 // STATISTICS: example-any