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