Generated on Sat Feb 12 2011 17:40:46 for Gecode by doxygen 1.7.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: 2010-10-07 11:52:01 +0200 (Thu, 07 Oct 2010) $ by $Author: schulte $
00015  *     $Revision: 11473 $
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   Play(void) : h(0), a(0), g(0) {}
00059 };
00060 
00062 class RRS {
00063 protected:
00065   const int teams;
00067   Play* plays;
00069   int weeks(void) const {
00070     return teams-1;
00071   }
00073   int periods(void) const {
00074     return teams/2;
00075   }
00077   int gn(int h, int a) const {
00078     return teams*(h-1) + a;
00079   }
00081   Play& play(int p, int w) {
00082     return plays[p*weeks() + w];
00083   }
00084 public:
00110   RRS(int t) : teams(t), plays(new Play[periods()*weeks()])  {
00111     // Determine the first game (week 0 period 0)
00112     play(0,0).h = 1;
00113     play(0,0).a = 2;
00114     play(0,0).g = 2;
00115 
00116     // Determine the other games of the first week
00117     for (int p=1; p<periods(); p++) {
00118       play(p,0).h = (p + 1) + 1;
00119       play(p,0).a = teams - (p + 1 - 2);
00120       play(p,0).g = gn(play(p,0).h,play(p,0).a);
00121     }
00122 
00123     // Compute the games for the subsequent weeks
00124     for (int w=1; w<weeks(); w++) {
00125       for (int p=0; p<periods(); p++) {
00126         if (play(p,w-1).h == teams)
00127           play(p,w).h = 2;
00128         else if (play(p,w-1).h == 1)
00129           play(p,w).h = 1;
00130         else
00131           play(p,w).h = play(p,w-1).h + 1;
00132         if (play(p,w-1).a == teams)
00133           play(p,w).a = 2;
00134         else
00135           play(p,w).a = play(p,w-1).a + 1;
00136 
00137         // maintain symmetry for (h,a): h < a
00138         if (play(p,w).h > play(p,w).a)
00139           std::swap(play(p,w).h,play(p,w).a);
00140 
00141         play(p,w).g = gn(play(p,w).h,play(p,w).a);
00142       }
00143     }
00144 
00145   }
00147   void hag(int w, IntArgs& h, IntArgs& a, IntArgs& g) {
00148     for (int p=0; p<periods(); p++) {
00149       h[p] = play(p,w).h;
00150       a[p] = play(p,w).a;
00151       g[p] = play(p,w).g;
00152     }
00153   }
00155   ~RRS(void) {
00156     delete [] plays;
00157   }
00158 };
00159 
00160 
00161 
00178 class SportsLeague : public Script {
00179 protected:
00180   const int teams;  
00181   IntVarArray home; 
00182   IntVarArray away; 
00183   IntVarArray game; 
00184 
00186   int weeks(void) const {
00187     return teams-1;
00188   }
00190   int periods(void) const {
00191     return teams/2;
00192   }
00194   IntVar& h(int p, int w) {
00195     return home[p*teams + w];
00196   }
00198   const IntVar& h(int p, int w) const {
00199     return home[p*teams + w];
00200   }
00202   IntVar& a(int p, int w) {
00203     return away[p*teams + w];
00204   }
00206   const IntVar& a(int p, int w) const {
00207     return away[p*teams + w];
00208   }
00210   IntVar& g(int p, int w) {
00211     return game[p*weeks() + w];
00212   }
00214   const IntVar& g(int p, int w) const {
00215     return game[p*weeks() + w];
00216   }
00217 
00218 public:
00220   SportsLeague(const SizeOptions& opt) :
00221     teams(opt.size()),
00222     home(*this, periods() * teams, 1, weeks()),
00223     away(*this, periods() * teams, 2, weeks()+1),
00224     game(*this, weeks()*periods(), 2, teams*weeks())
00225   {
00226     // Initialize round robin schedule
00227     RRS r(teams);
00228 
00229     // Domain for gamenumber of period
00230     for (int w=0; w<weeks(); w++) {
00231       IntArgs rh(periods()), ra(periods()), rg(periods());
00232       IntVarArgs n(*this,periods(),0,periods()-1);
00233 
00234       distinct(*this, n, opt.icl());
00235 
00236       r.hag(w,rh,ra,rg);
00237 
00238       for (int p=0; p<periods(); p++) {
00239         element(*this, rh, n[p], h(p,w));
00240         element(*this, ra, n[p], a(p,w));
00241         element(*this, rg, n[p], g(p,w));
00242       }
00243     }
00244 
00246     for (int p=0; p<periods(); p++)
00247       for (int w=0; w<teams; w++)
00248         rel(*this, h(p,w), IRT_LE, a(p,w));
00249 
00250     // Home teams in first week are ordered
00251     for (int p=0; p<periods()-1; p++)
00252       rel(*this, h(p,0), IRT_LE, h(p+1,0));
00253 
00254     // Fix first pair
00255     rel(*this, h(0,0), IRT_EQ, 1);
00256     rel(*this, a(0,0), IRT_EQ, 2);
00257 
00259     for (int w=0; w<teams; w++) {
00260       IntVarArgs c(teams);
00261       for (int p=0; p<periods(); p++) {
00262         c[2*p] = h(p,w); c[2*p+1] = a(p,w);
00263       }
00264       distinct(*this, c, opt.icl());
00265     }
00266 
00268     for (int p=0; p<periods(); p++) {
00269       IntVarArgs r(2*teams);
00270       for (int t=0; t<teams; t++) {
00271         r[2*t]   = h(p,t);
00272         r[2*t+1] = a(p,t);
00273       }
00274       IntArgs values(teams);
00275       for (int i=1; i<=teams; i++)
00276         values[i-1] = i;
00277       count(*this, r, IntSet(2,2), values, opt.icl());
00278     }
00279 
00280     // Redundant constraint
00281     for (int p=0; p<periods(); p++)
00282       for (int w=0; w<weeks(); w ++)
00283         rel(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams);
00284 
00285     distinct(*this, game, opt.icl());
00286 
00287     branch(*this, game, INT_VAR_NONE, INT_VAL_SPLIT_MIN);
00288   }
00290   SportsLeague(bool share, SportsLeague& s)
00291     : Script(share, s), teams(s.teams) {
00292     home.update(*this, share, s.home);
00293     away.update(*this, share, s.away);
00294     game.update(*this, share, s.game);
00295   }
00297   virtual Space*
00298   copy(bool share) {
00299     return new SportsLeague(share, *this);
00300   }
00302   virtual void print(std::ostream& os) const {
00303     // print period index
00304     os << "\t       ";
00305     for (int p=0; p<periods(); p++) {
00306       os << "P[";
00307       os.width(2);
00308       os << p << "] ";
00309       }
00310     os << std::endl;
00311     // print entries
00312     for (int w=0; w<weeks(); w++) {
00313       os << "\tW[";
00314       os.width(2);
00315       os << w+1 << "]: ";
00316       for (int p=0; p<periods(); p++) {
00317         os.width(2);
00318         os << h(p,w).val() << '-';
00319         os.width(2);
00320         os << a(p,w).val() << " ";
00321       }
00322       os << std::endl;
00323     }
00324   }
00325 };
00326 
00327 
00331 int
00332 main(int argc, char* argv[]) {
00333   SizeOptions opt("Sports League Scheduling");
00334   opt.icl(ICL_DOM);
00335   opt.size(18);
00336   opt.parse(argc,argv);
00337   if (opt.size() < 5) {
00338     std::cerr<< "No Solution for less than 5 teams!" << std::endl;
00339     return 1;
00340   }
00341   if (opt.size() % 2 != 0) {
00342     std::cerr << "Number of teams has to be even!" << std::endl;
00343     return 1;
00344   }
00345   Script::run<SportsLeague, DFS,SizeOptions>(opt);
00346   return 0;
00347 }
00348 
00349 // STATISTICS: example-any