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 #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
00108 play(0,0).h = 1;
00109 play(0,0).a = 2;
00110 play(0,0).g = 2;
00111
00112
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
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
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
00224 RRS r(teams);
00225
00226
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
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
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
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
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
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