00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
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
00112 play(0,0).h = 1;
00113 play(0,0).a = 2;
00114 play(0,0).g = 2;
00115
00116
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
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
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 Script(opt),
00222 teams(opt.size()),
00223 home(*this, periods() * teams, 1, weeks()),
00224 away(*this, periods() * teams, 2, weeks()+1),
00225 game(*this, weeks()*periods(), 2, teams*weeks())
00226 {
00227
00228 RRS r(teams);
00229
00230
00231 for (int w=0; w<weeks(); w++) {
00232 IntArgs rh(periods()), ra(periods()), rg(periods());
00233 IntVarArgs n(*this,periods(),0,periods()-1);
00234
00235 distinct(*this, n, opt.ipl());
00236
00237 r.hag(w,rh,ra,rg);
00238
00239 for (int p=0; p<periods(); p++) {
00240 element(*this, rh, n[p], h(p,w));
00241 element(*this, ra, n[p], a(p,w));
00242 element(*this, rg, n[p], g(p,w));
00243 }
00244 }
00245
00247 for (int p=0; p<periods(); p++)
00248 for (int w=0; w<teams; w++)
00249 rel(*this, h(p,w), IRT_LE, a(p,w));
00250
00251
00252 {
00253 IntVarArgs h0(periods());
00254 for (int p=0; p<periods(); p++)
00255 h0[p] = h(p,0);
00256 rel(*this, h0, IRT_LE);
00257 }
00258
00259
00260 rel(*this, h(0,0), IRT_EQ, 1);
00261 rel(*this, a(0,0), IRT_EQ, 2);
00262
00264 for (int w=0; w<teams; w++) {
00265 IntVarArgs c(teams);
00266 for (int p=0; p<periods(); p++) {
00267 c[2*p] = h(p,w); c[2*p+1] = a(p,w);
00268 }
00269 distinct(*this, c, opt.ipl());
00270 }
00271
00273 for (int p=0; p<periods(); p++) {
00274 IntVarArgs r(2*teams);
00275 for (int t=0; t<teams; t++) {
00276 r[2*t] = h(p,t);
00277 r[2*t+1] = a(p,t);
00278 }
00279 IntArgs values(teams);
00280 for (int i=1; i<=teams; i++)
00281 values[i-1] = i;
00282 count(*this, r, IntSet(2,2), values, opt.ipl());
00283 }
00284
00285
00286 for (int p=0; p<periods(); p++)
00287 for (int w=0; w<weeks(); w ++)
00288 rel(*this, teams * h(p,w) + a(p,w) - g(p,w) == teams);
00289
00290 distinct(*this, game, opt.ipl());
00291
00292 branch(*this, game, INT_VAR_NONE(), INT_VAL_SPLIT_MIN());
00293 }
00295 SportsLeague(bool share, SportsLeague& s)
00296 : Script(share, s), teams(s.teams) {
00297 home.update(*this, share, s.home);
00298 away.update(*this, share, s.away);
00299 game.update(*this, share, s.game);
00300 }
00302 virtual Space*
00303 copy(bool share) {
00304 return new SportsLeague(share, *this);
00305 }
00307 virtual void print(std::ostream& os) const {
00308
00309 os << "\t ";
00310 for (int p=0; p<periods(); p++) {
00311 os << "P[";
00312 os.width(2);
00313 os << p << "] ";
00314 }
00315 os << std::endl;
00316
00317 for (int w=0; w<weeks(); w++) {
00318 os << "\tW[";
00319 os.width(2);
00320 os << w+1 << "]: ";
00321 for (int p=0; p<periods(); p++) {
00322 os.width(2);
00323 os << h(p,w).val() << '-';
00324 os.width(2);
00325 os << a(p,w).val() << " ";
00326 }
00327 os << std::endl;
00328 }
00329 }
00330 };
00331
00332
00336 int
00337 main(int argc, char* argv[]) {
00338 SizeOptions opt("Sports League Scheduling");
00339 opt.ipl(IPL_DOM);
00340 opt.size(18);
00341 opt.parse(argc,argv);
00342 if (opt.size() < 5) {
00343 std::cerr<< "No Solution for less than 5 teams!" << std::endl;
00344 return 1;
00345 }
00346 if (opt.size() % 2 != 0) {
00347 std::cerr << "Number of teams has to be even!" << std::endl;
00348 return 1;
00349 }
00350 Script::run<SportsLeague, DFS,SizeOptions>(opt);
00351 return 0;
00352 }
00353
00354