Generated on Fri Oct 19 11:24:49 2018 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  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041 
00042 #include <algorithm>
00043 #include <iomanip>
00044 
00045 using namespace Gecode;
00046 
00048 class Play {
00049 public:
00050   int h; 
00051   int a; 
00052   int g; 
00053 
00054   Play(void) : h(0), a(0), g(0) {}
00055 };
00056 
00058 class RRS {
00059 protected:
00061   const int teams;
00063   Play* plays;
00065   int weeks(void) const {
00066     return teams-1;
00067   }
00069   int periods(void) const {
00070     return teams/2;
00071   }
00073   int gn(int h, int a) const {
00074     return teams*(h-1) + a;
00075   }
00077   Play& play(int p, int w) {
00078     return plays[p*weeks() + w];
00079   }
00080 public:
00106   RRS(int t) : teams(t), plays(new Play[periods()*weeks()])  {
00107     // Determine the first game (week 0 period 0)
00108     play(0,0).h = 1;
00109     play(0,0).a = 2;
00110     play(0,0).g = 2;
00111 
00112     // Determine the other games of the first week
00113     for (int p=1; p<periods(); p++) {
00114       play(p,0).h = (p + 1) + 1;
00115       play(p,0).a = teams - (p + 1 - 2);
00116       play(p,0).g = gn(play(p,0).h,play(p,0).a);
00117     }
00118 
00119     // Compute the games for the subsequent weeks
00120     for (int w=1; w<weeks(); w++) {
00121       for (int p=0; p<periods(); p++) {
00122         if (play(p,w-1).h == teams)
00123           play(p,w).h = 2;
00124         else if (play(p,w-1).h == 1)
00125           play(p,w).h = 1;
00126         else
00127           play(p,w).h = play(p,w-1).h + 1;
00128         if (play(p,w-1).a == teams)
00129           play(p,w).a = 2;
00130         else
00131           play(p,w).a = play(p,w-1).a + 1;
00132 
00133         // maintain symmetry for (h,a): h < a
00134         if (play(p,w).h > play(p,w).a)
00135           std::swap(play(p,w).h,play(p,w).a);
00136 
00137         play(p,w).g = gn(play(p,w).h,play(p,w).a);
00138       }
00139     }
00140 
00141   }
00143   void hag(int w, IntArgs& h, IntArgs& a, IntArgs& g) {
00144     for (int p=0; p<periods(); p++) {
00145       h[p] = play(p,w).h;
00146       a[p] = play(p,w).a;
00147       g[p] = play(p,w).g;
00148     }
00149   }
00151   ~RRS(void) {
00152     delete [] plays;
00153   }
00154 };
00155 
00156 
00157 
00174 class SportsLeague : public Script {
00175 protected:
00176   const int teams;  
00177   IntVarArray home; 
00178   IntVarArray away; 
00179   IntVarArray game; 
00180 
00182   int weeks(void) const {
00183     return teams-1;
00184   }
00186   int periods(void) const {
00187     return teams/2;
00188   }
00190   IntVar& h(int p, int w) {
00191     return home[p*teams + w];
00192   }
00194   const IntVar& h(int p, int w) const {
00195     return home[p*teams + w];
00196   }
00198   IntVar& a(int p, int w) {
00199     return away[p*teams + w];
00200   }
00202   const IntVar& a(int p, int w) const {
00203     return away[p*teams + w];
00204   }
00206   IntVar& g(int p, int w) {
00207     return game[p*weeks() + w];
00208   }
00210   const IntVar& g(int p, int w) const {
00211     return game[p*weeks() + w];
00212   }
00213 
00214 public:
00216   SportsLeague(const SizeOptions& opt) :
00217     Script(opt),
00218     teams(opt.size()),
00219     home(*this, periods() * teams, 1, weeks()),
00220     away(*this, periods() * teams, 2, weeks()+1),
00221     game(*this, weeks()*periods(), 2, teams*weeks())
00222   {
00223     // Initialize round robin schedule
00224     RRS r(teams);
00225 
00226     // Domain for gamenumber of period
00227     for (int w=0; w<weeks(); w++) {
00228       IntArgs rh(periods()), ra(periods()), rg(periods());
00229       IntVarArgs n(*this,periods(),0,periods()-1);
00230 
00231       distinct(*this, n, opt.ipl());
00232 
00233       r.hag(w,rh,ra,rg);
00234 
00235       for (int p=0; p<periods(); p++) {
00236         element(*this, rh, n[p], h(p,w));
00237         element(*this, ra, n[p], a(p,w));
00238         element(*this, rg, n[p], g(p,w));
00239       }
00240     }
00241 
00243     for (int p=0; p<periods(); p++)
00244       for (int w=0; w<teams; w++)
00245         rel(*this, h(p,w), IRT_LE, a(p,w));
00246 
00247     // Home teams in first week are ordered
00248     {
00249       IntVarArgs h0(periods());
00250       for (int p=0; p<periods(); p++)
00251         h0[p] = h(p,0);
00252       rel(*this, h0, IRT_LE);
00253     }
00254 
00255     // Fix first pair
00256     rel(*this, h(0,0), IRT_EQ, 1);
00257     rel(*this, a(0,0), IRT_EQ, 2);
00258 
00260     for (int w=0; w<teams; w++) {
00261       IntVarArgs c(teams);
00262       for (int p=0; p<periods(); p++) {
00263         c[2*p] = h(p,w); c[2*p+1] = a(p,w);
00264       }
00265       distinct(*this, c, opt.ipl());
00266     }
00267 
00269     for (int p=0; p<periods(); p++) {
00270       IntVarArgs r(2*teams);
00271       for (int t=0; t<teams; t++) {
00272         r[2*t]   = h(p,t);
00273         r[2*t+1] = a(p,t);
00274       }
00275       IntArgs values(teams);
00276       for (int i=1; i<=teams; i++)
00277         values[i-1] = i;
00278       count(*this, r, IntSet(2,2), values, opt.ipl());
00279     }
00280 
00281     // Redundant constraint
00282     for (int p=0; p<periods(); p++)
00283       for (int w=0; w<weeks(); w ++)
00284         rel(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams);
00285 
00286     distinct(*this, game, opt.ipl());
00287 
00288     branch(*this, game, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
00289   }
00291   SportsLeague(SportsLeague& s)
00292     : Script(s), teams(s.teams) {
00293     home.update(*this, s.home);
00294     away.update(*this, s.away);
00295     game.update(*this, s.game);
00296   }
00298   virtual Space*
00299   copy(void) {
00300     return new SportsLeague(*this);
00301   }
00303   virtual void print(std::ostream& os) const {
00304     // print period index
00305     os << "\t       ";
00306     for (int p=0; p<periods(); p++) {
00307       os << "P[";
00308       os.width(2);
00309       os << p << "] ";
00310       }
00311     os << std::endl;
00312     // print entries
00313     for (int w=0; w<weeks(); w++) {
00314       os << "\tW[";
00315       os.width(2);
00316       os << w+1 << "]: ";
00317       for (int p=0; p<periods(); p++) {
00318         os.width(2);
00319         os << h(p,w).val() << '-';
00320         os.width(2);
00321         os << a(p,w).val() << " ";
00322       }
00323       os << std::endl;
00324     }
00325   }
00326 };
00327 
00328 
00332 int
00333 main(int argc, char* argv[]) {
00334   SizeOptions opt("Sports League Scheduling");
00335   opt.ipl(IPL_DOM);
00336   opt.size(18);
00337   opt.parse(argc,argv);
00338   if (opt.size() < 5) {
00339     std::cerr<< "No Solution for less than 5 teams!" << std::endl;
00340     return 1;
00341   }
00342   if (opt.size() % 2 != 0) {
00343     std::cerr << "Number of teams has to be even!" << std::endl;
00344     return 1;
00345   }
00346   Script::run<SportsLeague, DFS,SizeOptions>(opt);
00347   return 0;
00348 }
00349 
00350 // STATISTICS: example-any