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/set.hh>
00041
00042 using namespace Gecode;
00043
00050
00051 struct Tournament {
00053 int groups;
00055 int playersInGroup;
00057 int weeks;
00058 };
00060 static const Tournament t[]=
00061 { {8,4,9},
00062 {5,3,7},
00063 {4,3,2}
00064 };
00066 static const unsigned int n_examples = sizeof(t) / sizeof(Tournament);
00068
00077 class Golf : public Script {
00078 public:
00080 enum {
00081 MODEL_PLAIN,
00082 MODEL_SYMMETRY
00083 };
00084 enum {
00085 PROP_PLAIN,
00086 PROP_DECOMPOSE
00087 };
00088 int groups;
00089 int playersInGroup;
00090 int weeks;
00091 int players;
00092
00094 SetVarArray groupsS;
00095
00097 SetVar& group(int w, int g) {
00098 return groupsS[w*groups+g];
00099 }
00101 const SetVar& group(int w, int g) const {
00102 return groupsS[w*groups+g];
00103 }
00104
00106 Golf(const SizeOptions& opt) :
00107 groups(t[opt.size()].groups),
00108 playersInGroup(t[opt.size()].playersInGroup),
00109 weeks(t[opt.size()].weeks),
00110 players(groups*playersInGroup),
00111 groupsS(*this,groups*weeks,IntSet::empty,0,players-1,
00112 playersInGroup,playersInGroup) {
00113
00114 SetVar allPlayers(*this, 0, players-1, 0, players-1);
00115
00116
00117 for (int w=0; w<weeks; w++) {
00118 SetVarArgs p(groups);
00119 for (int g=0; g < groups; g++)
00120 p[g] = group(w,g);
00121
00122 rel(*this,SOT_DUNION,p,allPlayers);
00123 }
00124
00125
00126 for (int w=0; w<weeks; w++) {
00127 for (int g=0; g<groups; g++) {
00128 SetVar v = group(w,g);
00129 SetVar vcompl;
00130 if (opt.propagation() == PROP_DECOMPOSE) {
00131 vcompl = SetVar(*this,IntSet::empty,
00132 Set::Limits::min,Set::Limits::max);
00133 rel(*this, v, SRT_CMPL, vcompl);
00134 }
00135 for (int i=(w+1)*groups; i<weeks*groups; i++) {
00136 if (opt.propagation() == PROP_PLAIN) {
00137 SetVar atMostOne(*this,IntSet::empty,0,players-1,0,1);
00138 rel(*this, v, SOT_INTER, groupsS[i], SRT_EQ, atMostOne);
00139 } else {
00140 SetVar atMostOneC(*this,IntSet::empty,
00141 Set::Limits::min,
00142 Set::Limits::max,
00143 Set::Limits::card-1,
00144 Set::Limits::card);
00145 SetVar groupsSiC(*this,IntSet::empty,
00146 Set::Limits::min,Set::Limits::max);
00147 rel(*this, groupsS[i], SRT_CMPL, groupsSiC);
00148 rel(*this, vcompl, SOT_UNION, groupsSiC, SRT_EQ, atMostOneC);
00149 }
00150 }
00151 }
00152 }
00153
00154 if (opt.model() == MODEL_SYMMETRY) {
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165 for (int w=0; w < weeks; w++) {
00166 for (int p=0; p < players; p++) {
00167 BoolVarArgs bs(groups);
00168 for (int g=0; g<groups; g++) {
00169 BoolVar b(*this,0,1);
00170 dom(*this, group(w,g), SRT_SUP, p, b);
00171 bs[g] = b;
00172 }
00173 linear(*this, bs, IRT_EQ, 1);
00174 }
00175 }
00176
00177
00178
00179 atmostOne(*this, groupsS, playersInGroup);
00180
00181
00182 for (int w=0; w<weeks; w++) {
00183 for (int g=0; g<groups-1; g++) {
00184 IntVar minG1(*this, 0, players-1);
00185 IntVar minG2(*this, 0, players-1);
00186 SetVar g1 = group(w,g);
00187 SetVar g2 = group(w,g+1);
00188 min(*this, g1, minG1);
00189 min(*this, g2, minG2);
00190 rel(*this, minG1, IRT_LE, minG2);
00191 }
00192 }
00193
00194
00195
00196 for (int w=0; w<weeks-1; w++) {
00197 SetVar g1(*this, IntSet::empty, 1, players-1);
00198 SetVar g2(*this, IntSet::empty, 1, players-1);
00199 rel(*this, g1, SOT_DUNION, IntSet(0,0), SRT_EQ, group(w,0));
00200 rel(*this, g2, SOT_DUNION, IntSet(0,0), SRT_EQ, group(w+1,0));
00201 IntVar minG1(*this, 0, players-1);
00202 IntVar minG2(*this, 0, players-1);
00203 min(*this, g1, minG1);
00204 min(*this, g2, minG2);
00205 rel(*this, minG1, IRT_LE, minG2);
00206 }
00207
00208
00209
00210 IntVarArray groupsSInv(*this, weeks*players, 0, groups-1);
00211 for (int w=0; w<weeks; w++) {
00212 for (int p=0; p<players; p++) {
00213 SetVar thisPlayer(*this, p,p, 0, players-1);
00214 SetVarArgs thisWeek(groups);
00215 for (int g=0; g<groups; g++)
00216 thisWeek[g] = group(w,g);
00217 element(*this, thisWeek, groupsSInv[w*players+p], thisPlayer);
00218 }
00219 }
00220
00221
00222
00223 for (int w=0; w<weeks; w++)
00224 for (int p=0; p<groups; p++)
00225 rel(*this, groupsSInv[w*players+p], IRT_LQ, p);
00226 }
00227
00228 branch(*this, groupsS, SET_VAR_MIN_MIN, SET_VAL_MIN_INC);
00229 }
00230
00232 virtual void
00233 print(std::ostream& os) const {
00234 os << "Tournament plan" << std::endl;
00235
00236 for (int w=0; w<weeks; w++) {
00237 os << "Week " << w << ": " << std::endl << " ";
00238 for (int g=0; g<groups; g++) {
00239 if (group(w,g).assigned()) {
00240 bool first = true;
00241 os << "(";
00242 for (SetVarGlbValues glb(group(w,g)); glb(); ++glb) {
00243 if (first) first = false; else os << " ";
00244 os << glb.val();
00245 }
00246 os << ")";
00247 } else {
00248 os << "(" << group(w,g) << ")";
00249 }
00250 if (g < groups-1) os << " ";
00251 if (g > 0 && g % 4 == 0) os << std::endl << " ";
00252 }
00253 os << std::endl;
00254 }
00255 }
00256
00258 Golf(bool share, Golf& s) : Script(share,s),
00259 groups(s.groups), playersInGroup(s.playersInGroup),
00260 weeks(s.weeks), players(s.players) {
00261 groupsS.update(*this, share, s.groupsS);
00262 }
00264 virtual Space*
00265 copy(bool share) {
00266 return new Golf(share,*this);
00267 }
00268 };
00269
00273 int
00274 main(int argc, char* argv[]) {
00275 SizeOptions opt("Golf");
00276 opt.model(Golf::MODEL_PLAIN);
00277 opt.model(Golf::MODEL_PLAIN, "none", "no symmetry breaking");
00278 opt.model(Golf::MODEL_SYMMETRY, "symmetry", "static symmetry breaking");
00279 opt.propagation(Golf::PROP_PLAIN);
00280 opt.propagation(Golf::PROP_PLAIN, "plain", "intersection constraints");
00281 opt.propagation(Golf::PROP_DECOMPOSE, "decompose",
00282 "union and complement constraints");
00283 opt.solutions(1);
00284 opt.parse(argc,argv);
00285 if (opt.size() >= n_examples) {
00286 std::cerr << "Error: size must be between 0 and " << n_examples - 1
00287 << std::endl;
00288 return 1;
00289 }
00290 Script::run<Golf,DFS,SizeOptions>(opt);
00291 return 0;
00292 }
00293
00294
00295