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