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/set.hh"
00039 #include "examples/support.hh"
00040
00047
00048 struct Tournament {
00050 int groups;
00052 int playersInGroup;
00054 int weeks;
00055 };
00057 static const Tournament t[]=
00058 { {8,4,9},
00059 {5,3,7},
00060 {4,3,2}
00061 };
00063 static const unsigned int n_examples = sizeof(t) / sizeof(Tournament);
00065
00074 class Golf : public Example {
00075 public:
00077 enum {
00078 MODEL_PLAIN,
00079 MODEL_SYMMETRY
00080 };
00081 int groups;
00082 int playersInGroup;
00083 int weeks;
00084 int players;
00085
00087 SetVarArray groupsS;
00088
00090 SetVar& group(int w, int g) {
00091 return groupsS[w*groups+g];
00092 }
00093
00095 Golf(const SizeOptions& opt) :
00096 groups(t[opt.size()].groups),
00097 playersInGroup(t[opt.size()].playersInGroup),
00098 weeks(t[opt.size()].weeks),
00099 players(groups*playersInGroup),
00100 groupsS(this,groups*weeks,IntSet::empty,0,players-1,
00101 playersInGroup,playersInGroup) {
00102
00103 SetVar allPlayers(this, 0, players-1, 0, players-1);
00104
00105
00106 for (int w=0; w<weeks; w++) {
00107 SetVarArgs p(groups);
00108 for (int g=0; g < groups; g++)
00109 p[g] = group(w,g);
00110
00111 rel(this,SOT_DUNION,p,allPlayers);
00112 }
00113
00114
00115 for (int w=0; w<weeks; w++) {
00116 for (int g=0; g<groups; g++) {
00117 SetVar v = group(w,g);
00118 for (int i=(w+1)*groups; i<weeks*groups; i++) {
00119 SetVar atMostOne(this,IntSet::empty,0,players-1,0,1);
00120 rel(this, v, SOT_INTER, groupsS[i], SRT_EQ, atMostOne);
00121 }
00122 }
00123 }
00124
00125 if (opt.model() == MODEL_SYMMETRY) {
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136 for (int w=0; w < weeks; w++) {
00137 for (int p=0; p < players; p++) {
00138 BoolVarArgs bs(groups);
00139 for (int g=0; g<groups; g++) {
00140 BoolVar b(this,0,1);
00141 dom(this, group(w,g), SRT_SUP, p, b);
00142 bs[g] = b;
00143 }
00144 linear(this, bs, IRT_EQ, 1);
00145 }
00146 }
00147
00148
00149
00150 atmostOne(this, groupsS, playersInGroup);
00151
00152
00153 for (int w=0; w<weeks; w++) {
00154 for (int g=0; g<groups-1; g++) {
00155 IntVar minG1(this, 0, players-1);
00156 IntVar minG2(this, 0, players-1);
00157 SetVar g1 = group(w,g);
00158 SetVar g2 = group(w,g+1);
00159 min(this, g1, minG1);
00160 min(this, g2, minG2);
00161 rel(this, minG1, IRT_LE, minG2);
00162 }
00163 }
00164
00165
00166
00167 for (int w=0; w<weeks-1; w++) {
00168 SetVar g1(this, IntSet::empty, 1, players-1);
00169 SetVar g2(this, IntSet::empty, 1, players-1);
00170 rel(this, g1, SOT_DUNION, IntSet(0,0), SRT_EQ, group(w,0));
00171 rel(this, g2, SOT_DUNION, IntSet(0,0), SRT_EQ, group(w+1,0));
00172 IntVar minG1(this, 0, players-1);
00173 IntVar minG2(this, 0, players-1);
00174 min(this, g1, minG1);
00175 min(this, g2, minG2);
00176 rel(this, minG1, IRT_LE, minG2);
00177 }
00178
00179
00180
00181 IntVarArray groupsSInv(this, weeks*players, 0, groups-1);
00182 for (int w=0; w<weeks; w++) {
00183 for (int p=0; p<players; p++) {
00184 SetVar thisPlayer(this, p,p, 0, players-1);
00185 SetVarArgs thisWeek(groups);
00186 for (int g=0; g<groups; g++)
00187 thisWeek[g] = group(w,g);
00188 selectSet(this, thisWeek, groupsSInv[w*players+p], thisPlayer);
00189 }
00190 }
00191
00192
00193
00194 for (int w=0; w<weeks; w++) {
00195 for (int p=0; p<groups; p++) {
00196 rel(this, groupsSInv[w*players+p], IRT_LQ, p);
00197 }
00198 }
00199
00200 }
00201
00202 branch(this, groupsS, SET_VAR_MIN_UNKNOWN_ELEM, SET_VAL_MIN);
00203 }
00204
00206 virtual void
00207 print(std::ostream& os) {
00208 os << "Tournament plan" << std::endl;
00209
00210 for (int w=0; w<weeks; w++) {
00211 os << "Week " << w << ": " << std::endl << " ";
00212 for (int g=0; g<groups; g++) {
00213 if (group(w,g).assigned()) {
00214 bool first = true;
00215 os << "(";
00216 for (SetVarGlbValues glb(group(w,g)); glb(); ++glb) {
00217 if (first) first = false; else os << " ";
00218 os << glb.val();
00219 }
00220 os << ")";
00221 } else {
00222 os << "(" << group(w,g) << ")";
00223 }
00224 if (g < groups-1) os << " ";
00225 if (g > 0 && g % 4 == 0) os << std::endl << " ";
00226 }
00227 os << std::endl;
00228 }
00229 }
00230
00232 Golf(bool share, Golf& s) : Example(share,s),
00233 groups(s.groups), playersInGroup(s.playersInGroup),
00234 weeks(s.weeks), players(s.players) {
00235 groupsS.update(this, share, s.groupsS);
00236 }
00238 virtual Space*
00239 copy(bool share) {
00240 return new Golf(share,*this);
00241 }
00242
00244 virtual void
00245 getVars(Gecode::Reflection::VarMap& vm, bool registerOnly) {
00246 vm.putArray(this, groupsS, "groupsS", registerOnly);
00247 }
00248 };
00249
00253 int
00254 main(int argc, char* argv[]) {
00255 SizeOptions opt("Golf");
00256 opt.model(Golf::MODEL_PLAIN);
00257 opt.model(Golf::MODEL_PLAIN, "none", "no symmetry breaking");
00258 opt.model(Golf::MODEL_SYMMETRY, "symmetry", "static symmetry breaking");
00259 opt.solutions(1);
00260 opt.parse(argc,argv);
00261 if (opt.size() >= n_examples) {
00262 std::cerr << "Error: size must be between 0 and " << n_examples - 1
00263 << std::endl;
00264 return 1;
00265 }
00266 Example::run<Golf,DFS,SizeOptions>(opt);
00267 return 0;
00268 }
00269
00270
00271