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 };
00087 int g;
00088 int s;
00089 int w;
00090
00092 SetVarArray groups;
00093
00095 Golf(const GolfOptions& opt)
00096 : Script(opt),
00097 g(opt.g()), s(opt.s()), w(opt.w()),
00098 groups(*this,g*w,IntSet::empty,0,g*s-1,s,s) {
00099 Matrix<SetVarArray> schedule(groups,g,w);
00100
00101
00102 SetVar allPlayers(*this, 0,g*s-1, 0,g*s-1);
00103 for (int i=0; i<w; i++)
00104 rel(*this, setdunion(schedule.row(i)) == allPlayers);
00105
00106
00107 for (int i=0; i<groups.size()-1; i++)
00108 for (int j=i+1; j<groups.size(); j++)
00109 rel(*this, cardinality(groups[i] & groups[j]) <= 1);
00110
00111 if (opt.model() == MODEL_SYMMETRY) {
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122 for (int j=0; j<w; j++) {
00123 for (int p=0; p < g*s; p++) {
00124 BoolVarArgs b(g);
00125 for (int i=0; i<g; i++)
00126 b[i] = expr(*this, (singleton(p) <= schedule(i,j)));
00127 linear(*this, b, IRT_EQ, 1);
00128 }
00129 }
00130
00131
00132 for (int j=0; j<w; j++) {
00133 IntVarArgs m(g);
00134 for (int i=0; i<g; i++)
00135 m[i] = expr(*this, min(schedule(i,j)));
00136 rel(*this, m, IRT_LE);
00137 }
00138
00139
00140
00141 {
00142 IntVarArgs m(w);
00143 for (int i=0; i<w; i++)
00144 m[i] = expr(*this, min(schedule(0,i)-IntSet(0,0)));
00145 rel(*this, m, IRT_LE);
00146 }
00147
00148
00149 precede(*this, groups, IntArgs::create(groups.size(),0));
00150 }
00151
00152 branch(*this, groups, SET_VAR_MIN_MIN(), SET_VAL_MIN_INC());
00153 }
00154
00156 virtual void
00157 print(std::ostream& os) const {
00158 os << "Tournament plan" << std::endl;
00159 Matrix<SetVarArray> schedule(groups,g,w);
00160 for (int j=0; j<w; j++) {
00161 os << "Week " << j << ": " << std::endl << " ";
00162 os << schedule.row(j) << std::endl;
00163 }
00164 }
00165
00167 Golf(bool share, Golf& s) : Script(share,s), g(s.g), s(s.s), w(s.w) {
00168 groups.update(*this, share, s.groups);
00169 }
00171 virtual Space*
00172 copy(bool share) {
00173 return new Golf(share,*this);
00174 }
00175 };
00176
00180 int
00181 main(int argc, char* argv[]) {
00182 GolfOptions opt;
00183 opt.model(Golf::MODEL_PLAIN);
00184 opt.model(Golf::MODEL_PLAIN, "none", "no symmetry breaking");
00185 opt.model(Golf::MODEL_SYMMETRY, "symmetry", "static symmetry breaking");
00186 opt.solutions(1);
00187 opt.parse(argc,argv);
00188 Script::run<Golf,DFS,GolfOptions>(opt);
00189 return 0;
00190 }
00191
00192