00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "int.hh"
00023 #include "examples/support.hh"
00024 #include "minimodel.hh"
00025
00032 struct Play {
00034 int h;
00036 int a;
00038 int g;
00039 };
00040
00041 typedef PrimArgArray<Play> RRSArray;
00042
00060 class SportsLeague : public Example {
00061 private:
00064 int t;
00066 int weeks;
00068 int eweeks;
00070 int periods;
00072 int season;
00074 int value;
00076 IntVarArray home;
00078 IntVarArray away;
00080 IntVarArray game;
00082 RRSArray rrs_array;
00083 protected:
00084
00085 int digit(int n) {
00086 int f = n;
00087 int fdigit = 0;
00088 while (f / 10) {
00089 fdigit++;
00090 f = f / 10;
00091 }
00092 return fdigit;
00093 }
00094
00095
00096 void blank(int n) {
00097 for (int d = digit(t) - digit(n); d--; ) {
00098 std::cout << " ";
00099 }
00100 std::cout << n;
00101 }
00102
00103 void blankv(int n) {
00104 for (int d = digit(value) - digit(n); d--; ) {
00105 std::cout << " ";
00106 }
00107 std::cout << n;
00108 }
00109
00110 void blank_only(int n) {
00111 for (int i = digit(n); i--; ) {
00112 std::cout << " ";
00113 }
00114 }
00115
00116 public:
00118 IntVar& h (int p, int w) {
00119 return home[p * eweeks + w];
00120 }
00121
00123 IntVar& a (int p, int w) {
00124 return away[p * eweeks + w];
00125 }
00126
00131 IntVar& g (int p, int w) {
00132 return game[p * weeks + w];
00133 }
00134
00139 Play& rrs(int p, int w) {
00140 return rrs_array[p * weeks + w];
00141 }
00142
00152 int gn(int h, int a) {
00153 return (t * (h - 1) + a);
00154 }
00155
00182 void init_rrs(void) {
00183
00184
00185 for(int p = 0; p < periods; p++)
00186 for (int w = 0; w < weeks; w++) {
00187 rrs(p, w).h = 0;
00188 rrs(p, w).a = 0;
00189 rrs(p, w).g = 0;
00190 }
00191
00192
00193 rrs(0, 0).h = 1;
00194 rrs(0, 0).a = 2;
00195 rrs(0, 0).g = 2;
00196
00197
00198 for(int p = 1; p < periods; p++){
00199 rrs(p, 0).h = (p + 1) + 1;
00200 rrs(p, 0).a = t - (p + 1 - 2);
00201 rrs(p, 0).g = gn(rrs(p, 0).h, rrs(p, 0).a);
00202 }
00203
00204
00205 for (int w = 1; w < weeks; w++) {
00206 for (int p = 0; p < periods; p++) {
00207 if (rrs(p, w - 1).h == t) {
00208 rrs(p, w).h = 2;
00209 } else {
00210 if (rrs(p, w - 1).h == 1) {
00211 rrs(p, w).h = 1;
00212 } else {
00213 rrs(p, w).h = rrs(p, w - 1).h + 1;
00214 }
00215 }
00216 if (rrs(p, w - 1).a == t) {
00217 rrs(p, w).a = 2;
00218 } else {
00219 rrs(p, w).a = rrs(p, w - 1).a + 1;
00220 }
00221
00222
00223 if (rrs(p, w).h > rrs(p, w).a) {
00224 int buffer = rrs(p, w).h;
00225 rrs(p, w).h = rrs(p, w).a;
00226 rrs(p, w).a = buffer;
00227 }
00228 rrs(p, w).g = gn(rrs(p, w).h, rrs(p, w).a);
00229 }
00230 }
00231 }
00232
00233 SportsLeague(const Options& op) :
00234 t (op.size),
00235 weeks (t - 1),
00236 eweeks (t),
00237 periods (t / 2),
00238 season (weeks * periods),
00239 value (t * (t - 2) + t),
00240 home (this, periods * eweeks),
00241 away (this, periods * eweeks),
00242 game (this, season),
00243 rrs_array (periods * weeks){
00244
00245 IntSet dom_all (1, t);
00246 IntSet dom_game (2, value);
00247 IntSet dom_home (1, t - 1);
00248 IntSet dom_away (2, t);
00249 IntSet dom_index (0, periods - 1);
00250
00251 for (int i = eweeks * periods; i--; ) {
00252 home[i].init(this, dom_home);
00253 away[i].init(this, dom_away);
00254 }
00255 for (int i = season; i--; ) {
00256 game[i].init(this, dom_game);
00257 }
00258
00259
00260
00261 init_rrs();
00262
00263
00264 for (int w = 0; w < weeks; w++) {
00265 IntArgs gamenum(periods);
00266 IntArgs fst(periods);
00267 IntArgs snd(periods);
00268
00269 for(int p = 0; p < periods; p++){
00270 gamenum[p] = rrs(p, w).g;
00271 fst[p] = rrs(p, w).h;
00272 snd[p] = rrs(p, w).a;
00273 }
00274
00275 IntVarArray n(this, periods, 0, periods - 1);
00276 distinct(this, n, ICL_DOM);
00277
00278 for(int p = 0; p < periods; p++){
00279 element(this, gamenum, n[p], g(p, w), op.icl);
00280 element(this, fst, n[p], h(p, w), op.icl);
00281 element(this, snd, n[p], a(p, w), op.icl);
00282 }
00283 }
00284
00285
00292
00293 rel(this, h(0,0), IRT_EQ, 1);
00294 rel(this, a(0,0), IRT_EQ, 2);
00295
00296 for (int p = 0; p < periods; p++) {
00297 for (int w = 0; w < eweeks; w++) {
00298 rel(this, h(p, w), IRT_LE, a(p, w));
00299 }
00300 }
00301
00302
00303 for (int p = 0; p < periods - 1; p++) {
00304 rel(this, h(p, 0), IRT_LE, h(p + 1, 0));
00305 }
00306
00313 for(int w = 0; w < eweeks; w++ ) {
00314 IntVarArray col(this, t);
00315 int k = 0;
00316 for( int p = 0; p < periods; p++ ) {
00317 col[k] = h(p, w);
00318 k++;
00319 col[k] = a(p, w);
00320 k++;
00321 }
00322 distinct(this, col, ICL_DOM);
00323 }
00324
00333 for(int p = 0; p < periods; p++) {
00334 IntVarArray row(this, 2 * eweeks);
00335 for (int w = 0; w < 2 * eweeks; w +=2) {
00336 row[w] = h(p, w / 2);
00337 row[w + 1] = a(p, w / 2);
00338 }
00339 gcc(this, row, 2, op.icl);
00340 }
00341
00342
00343
00344 for(int p = 0; p < periods; p++) {
00345 for(int w = 0; w < weeks; w ++) {
00346 post(this, t * h(p, w) + 1 * a(p, w) - 1* g(p, w) == t);
00347 }
00348 }
00349
00350 distinct(this, game, ICL_DOM);
00351
00352 branch(this, game, BVAR_NONE, BVAL_MIN);
00353
00354 }
00355
00356 SportsLeague(bool share, SportsLeague& s)
00357 : Example(share, s),
00358 t(s.t), weeks(s.weeks), eweeks(s.eweeks),
00359 periods(s.periods), season(s.season),
00360 value(s.value), rrs_array(s.rrs_array) {
00361 home.update(this, share, s.home);
00362 away.update(this, share, s.away);
00363 game.update(this, share, s.game);
00364 }
00365
00366 virtual Space*
00367 copy(bool share) {
00368 return new SportsLeague(share, *this);
00369 }
00370
00371 virtual void print(void){
00372
00373
00374 std::cout << "\nSchedule for " << t << " teams"
00375 << " and "<< weeks << " weeks:" << std::endl;
00376
00377 std::cout << " ";
00378 blank_only(t);
00379 std::cout << " ";
00380 for (int p = 0; p < periods; p++) {
00381 blank_only(t);
00382 std::cout << "P[";
00383 blank(p);
00384 std::cout <<"]";
00385 blank_only(t);
00386 }
00387 std::cout <<"\n";
00388
00389
00390 for(int w = 0; w < weeks; w++){
00391 std::cout << "W[";
00392 blank(w + 1);
00393 std::cout <<"]: ";
00394 for(int p = 0; p < periods; p++){
00395 if (h(p, w).assigned() && a(p, w).assigned()) {
00396 std::cout <<" ";
00397 blank(h(p, w).val());
00398 std::cout <<",";
00399 blank(a(p, w).val());
00400 std::cout <<" ";
00401 } else {
00402 blank_only(t);
00403 std::cout << " x ";
00404 blank_only(t);
00405 }
00406 }
00407 std::cout << "\n";
00408 }
00409 std::cout << "\n";
00410
00411
00412 std::cout << "\nUnique game numbers:\n";
00413 std::cout <<"\n";
00414 for(int p = 0; p < periods; p++){
00415 std::cout << "Period[";
00416 blank(p + 1);
00417 std::cout <<"]: " ;
00418 for(int w = 0; w < weeks; w++){
00419 if (g(p, w).assigned()) {
00420 blankv(g(p, w).val());
00421 std::cout << " ";
00422 } else {
00423 for (int i = digit(value); i--; ) {
00424 std::cout << " ";
00425 }
00426 std::cout << " ";
00427 }
00428 }
00429 std::cout << "\n";
00430 }
00431 std::cout << "\n";
00432
00433 }
00434 };
00435
00436
00437 int main(int argc, char** argv){
00438 Options o("Sports League Scheduling ");
00439 o.solutions = 1;
00440 o.size = 18;
00441 o.parse(argc, argv);
00442 if (o.size == 4) {
00443 std::cerr<< "No Solution for t = 4!\n";
00444 return -1;
00445 }
00446 if (o.size % 2 != 0) {
00447 std::cerr << "Number of t has to be even!\n";
00448 return -1;
00449 }
00450 Example::run<SportsLeague, DFS>(o);
00451 return 0;
00452 }
00453
00454
00455