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