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
00045 class GolfOptions : public Options {
00046 protected:
00047 Driver::IntOption _w;
00048 Driver::IntOption _g;
00049 Driver::IntOption _s;
00050 public:
00052 GolfOptions(void)
00053 : Options("Golf"),
00054 _w("w","number of weeks",9),
00055 _g("g","number of groups",8),
00056 _s("s","number of players per group",4) {
00057 add(_w);
00058 add(_g);
00059 add(_s);
00060 }
00062 int w(void) const { return _w.value(); }
00064 int g(void) const { return _g.value(); }
00066 int s(void) const { return _s.value(); }
00067 };
00068
00080 class Golf : public Script {
00081 public:
00083 enum {
00084 MODEL_PLAIN,
00085 MODEL_SYMMETRY
00086 };
00088 enum {
00089 PROP_SET,
00090 PROP_INT,
00091 PROP_MIXED,
00092 };
00093 int g;
00094 int s;
00095 int w;
00096
00098 SetVarArray groups;
00099
00101 Golf(const GolfOptions& opt)
00102 : Script(opt),
00103 g(opt.g()), s(opt.s()), w(opt.w()),
00104 groups(*this,g*w,IntSet::empty,0,g*s-1,
00105 static_cast<unsigned int>(s),static_cast<unsigned int>(s)) {
00106 Matrix<SetVarArray> schedule(groups,g,w);
00107
00108
00109 SetVar allPlayers(*this, 0,g*s-1, 0,g*s-1);
00110 for (int i=0; i<w; i++)
00111 rel(*this, setdunion(schedule.row(i)) == allPlayers);
00112
00113
00114 if (opt.propagation() == PROP_SET || opt.propagation() == PROP_MIXED) {
00115
00116 for (int i=0; i<groups.size()-1; i++)
00117 for (int j=i+1; j<groups.size(); j++)
00118 rel(*this, cardinality(groups[i] & groups[j]) <= 1);
00119 }
00120 if (opt.propagation() == PROP_INT || opt.propagation() == PROP_MIXED) {
00121
00122
00123 int playerCount = g * s;
00124 TupleSet ts(3);
00125 int pairCount=0;
00126 for (int p1=0; p1<playerCount-1; p1++)
00127 for (int p2=p1+1; p2<playerCount; p2++)
00128 ts.add(p1, p2, pairCount++);
00129 ts.finalize();
00130
00131
00132 IntVarArgs pairs;
00133 for (int i=0; i<groups.size()-1; i++) {
00134
00135
00136 IntVarArgs group(*this, s, 0, playerCount-1);
00137 channelSorted(*this, group, groups[i]);
00138
00139 for (int p1=0; p1<group.size()-1; ++p1) {
00140 for (int p2=p1+1; p2<group.size(); ++p2) {
00141 IntVar pair(*this, 0, pairCount);
00142
00143 IntVarArgs args;
00144 args << group[p1] << group[p2] << pair;
00145 extensional(*this, args, ts);
00146
00147 pairs << pair;
00148 }
00149 }
00150 }
00151
00152
00153 distinct(*this, pairs, opt.ipl());
00154 }
00155
00156 if (opt.model() == MODEL_SYMMETRY) {
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167 for (int j=0; j<w; j++) {
00168 for (int p=0; p < g*s; p++) {
00169 BoolVarArgs b(g);
00170 for (int i=0; i<g; i++)
00171 b[i] = expr(*this, (singleton(p) <= schedule(i,j)));
00172 linear(*this, b, IRT_EQ, 1);
00173 }
00174 }
00175
00176
00177 for (int j=0; j<w; j++) {
00178 IntVarArgs m(g);
00179 for (int i=0; i<g; i++)
00180 m[i] = expr(*this, min(schedule(i,j)));
00181 rel(*this, m, IRT_LE);
00182 }
00183
00184
00185
00186 {
00187 IntVarArgs m(w);
00188 for (int i=0; i<w; i++)
00189 m[i] = expr(*this, min(schedule(0,i)-IntSet(0,0)));
00190 rel(*this, m, IRT_LE);
00191 }
00192
00193
00194 precede(*this, groups, IntArgs::create(groups.size(),0));
00195 }
00196
00197 branch(*this, groups, SET_VAR_MIN_MIN(), SET_VAL_MIN_INC());
00198 }
00199
00201 virtual void
00202 print(std::ostream& os) const {
00203 os << "Tournament plan" << std::endl;
00204 Matrix<SetVarArray> schedule(groups,g,w);
00205 for (int j=0; j<w; j++) {
00206 os << "Week " << j << ": " << std::endl << " ";
00207 os << schedule.row(j) << std::endl;
00208 }
00209 }
00210
00212 Golf(Golf& s) : Script(s), g(s.g), s(s.s), w(s.w) {
00213 groups.update(*this, s.groups);
00214 }
00216 virtual Space*
00217 copy(void) {
00218 return new Golf(*this);
00219 }
00220 };
00221
00225 int
00226 main(int argc, char* argv[]) {
00227 GolfOptions opt;
00228 opt.model(Golf::MODEL_PLAIN);
00229 opt.model(Golf::MODEL_PLAIN, "none", "no symmetry breaking");
00230 opt.model(Golf::MODEL_SYMMETRY, "symmetry", "static symmetry breaking");
00231 opt.propagation(Golf::PROP_SET);
00232 opt.propagation(Golf::PROP_SET, "set", "Use set intersection cardinality for pair play constraints");
00233 opt.propagation(Golf::PROP_INT, "int", "Use integer distinct for pair play constraints");
00234 opt.propagation(Golf::PROP_MIXED, "mixed", "Use set interesection cardinality and integer distinct for pair play constraints");
00235 opt.ipl(IPL_DOM);
00236 opt.solutions(1);
00237 opt.parse(argc,argv);
00238 Script::run<Golf,DFS,GolfOptions>(opt);
00239 return 0;
00240 }
00241
00242