Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

golf.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2004
00008  *     Guido Tack, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-11-15 09:31:23 +0100 (Tue, 15 Nov 2005) $ by $Author: tack $
00012  *     $Revision: 2567 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 #include "set.hh"
00025 #include "examples/support.hh"
00026 
00033 
00034 struct Tournament {
00036   int groups;
00038   int playersInGroup;
00040   int weeks;
00041 };
00043 static const Tournament t[]=
00044   { {8,4,9},
00045     {5,3,7}
00046   };
00048 static const unsigned int n_examples = sizeof(t) / sizeof(Tournament);
00050 
00059 class Golf : public Example {
00060 public:
00061   int groups;
00062   int playersInGroup;
00063   int weeks;
00064   int players;
00065 
00066   SetVarArray groupsS;
00067   IntVarArray groupsSInv;
00068 
00069   SetVar& group(int w, int g) {
00070     return groupsS[w*groups+g];
00071   }
00072   IntVar& groupInv(int w, int p) {
00073     return groupsSInv[w*players+p];
00074   }
00075 
00076   Golf(const Options& o) :
00077     groups(t[o.size].groups),
00078     playersInGroup(t[o.size].playersInGroup),
00079     weeks(t[o.size].weeks),
00080     players(groups*playersInGroup),
00081     groupsS(this,groups*weeks,IntSet::empty,0,players-1,
00082             playersInGroup,playersInGroup),
00083     groupsSInv(this, weeks*players, 0, groups-1) {
00084 
00085     SetVar allPlayers(this, 0, players-1, 0, players-1);
00086 
00087     // Groups in one week must be disjoint
00088     for (int w=0; w<weeks; w++) {
00089       SetVarArgs p(groups);
00090       for (int g=0; g < groups; g++)
00091         p[g] = group(w,g);
00092       
00093       rel(this,SOT_DUNION,p,allPlayers);
00094     }
00095 
00096     // No two golfers play in the same group more than once
00097     for (int w=0; w<weeks; w++) {
00098       for (int g=0; g<groups; g++) {
00099         SetVar v = group(w,g);
00100         for (int i=(w+1)*groups; i<weeks*groups; i++) {
00101           SetVar atMostOne(this,IntSet::empty,0,players-1,0,1);
00102           rel(this, v, SOT_INTER, groupsS[i], SRT_EQ, atMostOne);
00103         }
00104       }
00105     }
00106 
00107     if (!o.naive) {
00108       
00109       /*
00110        * Redundant constraints and static symmetry breaking from
00111        * "Solving Kirkman's Schoolgirl Problem in a Few Seconds"
00112        * Nicolas Barnier, Pascal Brisset, Constraints, 10, 7-21, 2005
00113        *
00114        */
00115 
00116       // Redundant constraint:
00117       // in each week, one player plays in only one group
00118       for (int w=0; w < weeks; w++) {
00119         for (int p=0; p < players; p++) {
00120           BoolVarArgs bs(groups);
00121           for (int g=0; g<groups; g++) {
00122             BoolVar b(this,0,1);
00123             dom(this, group(w,g), SRT_SUP, p, b);
00124             bs[g] = b;
00125           }
00126           linear(this, bs, IRT_EQ, 1);
00127         }
00128        }
00129       
00130       // Symmetry breaking: order groups
00131       for (int w=0; w<weeks; w++) {
00132         for (int g=0; g<groups-1; g++) {
00133           IntVar minG1(this, 0, players-1);
00134           IntVar minG2(this, 0, players-1);
00135           SetVar g1 = group(w,g);
00136           SetVar g2 = group(w,g+1);
00137           minElement(this, g1, minG1);
00138           minElement(this, g2, minG2);
00139           rel(this, minG1, IRT_LE, minG2);
00140         }
00141       }
00142       
00143       // Symmetry breaking: order weeks
00144       // minElem(group(w,0)\{0}) < minElem(group(w+1,0)\{0})
00145       for (int w=0; w<weeks-1; w++) {
00146         SetVar g1(this, IntSet::empty, 1, players-1);
00147         SetVar g2(this, IntSet::empty, 1, players-1);
00148         SetVar zero1(this, IntSet::empty,0,0);
00149         SetVar zero2(this, IntSet::empty,0,0);
00150         rel(this, g1, SOT_DUNION, zero1, SRT_EQ, group(w,0));
00151         rel(this, g2, SOT_DUNION, zero2, SRT_EQ, group(w+1,0));
00152         IntVar minG1(this, 0, players-1);
00153         IntVar minG2(this, 0, players-1);
00154         minElement(this, g1, minG1);
00155         minElement(this, g2, minG2);
00156         rel(this, minG1, IRT_LE, minG2);
00157       }
00158       
00159       // Initialize the dual variables:
00160       // groupInv(w,p) is player p's group in week w
00161       for (int w=0; w<weeks; w++) {
00162         for (int p=0; p<players; p++) {
00163           SetVar thisPlayer(this, p,p, 0, players-1);
00164           SetVarArgs thisWeek(groups);
00165           for (int g=0; g<groups; g++)
00166             thisWeek[g] = group(w,g);
00167           selectSets(this, thisWeek, groupInv(w,p), thisPlayer);
00168         }
00169       }
00170 
00171       // Symmetry breaking: order players
00172       // For all p<groups : groupInv(w,p) <= p
00173       for (int w=0; w<weeks; w++) {
00174         for (int p=0; p<groups; p++) {
00175           rel(this, groupInv(w,p), IRT_LQ, p);
00176         }
00177       }
00178 
00179     }
00180 
00181     branch(this, groupsS, SETBVAR_MIN_UNKNOWN_ELEM, SETBVAL_MIN);
00182   }
00183 
00184   Golf(bool share, Golf& s) : Example(share,s),
00185       groups(s.groups), playersInGroup(s.playersInGroup),
00186       weeks(s.weeks), players(s.players) {
00187     groupsS.update(this, share, s.groupsS);
00188   }
00189 
00190   virtual Space*
00191   copy(bool share) {
00192     return new Golf(share,*this);
00193   }
00194 
00195   virtual void
00196   print(void) {
00197 
00198     std::cout << "Tournament plan" << std::endl;
00199 
00200     for (int w=0; w<weeks; w++) {
00201       std::cout << "Week " << w << ": " << std::endl << "    ";
00202       for (int g=0; g<groups; g++) {
00203         SetVarGlbValues glb(group(w,g));
00204         std::cout << "(" << glb.val();
00205         ++glb;
00206         while(glb()) {
00207           std::cout << " " << glb.val();
00208           ++glb;
00209         }
00210         std::cout << ")";
00211         if (g < groups-1) std::cout << " ";
00212         if (g > 0 && g % 4 == 0) std::cout << std::endl << "    ";
00213       }
00214       std::cout << std::endl;
00215     }
00216 
00217   }
00218 };
00219 
00220 int
00221 main(int argc, char** argv) {
00222   Options o("Golf");
00223   o.parse(argc,argv);
00224   o.solutions  = 1;
00225   if (o.size >= n_examples) {
00226     std::cerr << "Error: size must be between 0 and " << n_examples - 1
00227               << std::endl;
00228     return 1;
00229   }
00230   Example::run<Golf,DFS>(o);
00231   return 0;
00232 }
00233 
00234 // STATISTICS: example-any
00235