00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include "gecode/set.hh"
00025 #include "examples/support.hh"
00026
00033
00034 struct Tournament {
00036 int groups;
00038 int playersInGroup;
00040 int weeks;
00041 };
00043 static const Tournament t[]=
00044 { {8,4,9},
00045 {5,3,7}
00046 };
00048 static const unsigned int n_examples = sizeof(t) / sizeof(Tournament);
00050
00059 class Golf : public Example {
00060 public:
00061 int groups;
00062 int playersInGroup;
00063 int weeks;
00064 int players;
00065
00066 SetVarArray groupsS;
00067 IntVarArray groupsSInv;
00068
00069 SetVar& group(int w, int g) {
00070 return groupsS[w*groups+g];
00071 }
00072 IntVar& groupInv(int w, int p) {
00073 return groupsSInv[w*players+p];
00074 }
00075
00076 Golf(const Options& o) :
00077 groups(t[o.size].groups),
00078 playersInGroup(t[o.size].playersInGroup),
00079 weeks(t[o.size].weeks),
00080 players(groups*playersInGroup),
00081 groupsS(this,groups*weeks,IntSet::empty,0,players-1,
00082 playersInGroup,playersInGroup),
00083 groupsSInv(this, weeks*players, 0, groups-1) {
00084
00085 SetVar allPlayers(this, 0, players-1, 0, players-1);
00086
00087
00088 for (int w=0; w<weeks; w++) {
00089 SetVarArgs p(groups);
00090 for (int g=0; g < groups; g++)
00091 p[g] = group(w,g);
00092
00093 rel(this,SOT_DUNION,p,allPlayers);
00094 }
00095
00096
00097 for (int w=0; w<weeks; w++) {
00098 for (int g=0; g<groups; g++) {
00099 SetVar v = group(w,g);
00100 for (int i=(w+1)*groups; i<weeks*groups; i++) {
00101 SetVar atMostOne(this,IntSet::empty,0,players-1,0,1);
00102 rel(this, v, SOT_INTER, groupsS[i], SRT_EQ, atMostOne);
00103 }
00104 }
00105 }
00106
00107 if (!o.naive) {
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120 for (int w=0; w < weeks; w++) {
00121 for (int p=0; p < players; p++) {
00122 BoolVarArgs bs(groups);
00123 for (int g=0; g<groups; g++) {
00124 BoolVar b(this,0,1);
00125 dom(this, group(w,g), SRT_SUP, p, b);
00126 bs[g] = b;
00127 }
00128 linear(this, bs, IRT_EQ, 1);
00129 }
00130 }
00131
00132
00133
00134 atmostOne(this, groupsS, playersInGroup);
00135
00136
00137 for (int w=0; w<weeks; w++) {
00138 for (int g=0; g<groups-1; g++) {
00139 IntVar minG1(this, 0, players-1);
00140 IntVar minG2(this, 0, players-1);
00141 SetVar g1 = group(w,g);
00142 SetVar g2 = group(w,g+1);
00143 min(this, g1, minG1);
00144 min(this, g2, minG2);
00145 rel(this, minG1, IRT_LE, minG2);
00146 }
00147 }
00148
00149
00150
00151 for (int w=0; w<weeks-1; w++) {
00152 SetVar g1(this, IntSet::empty, 1, players-1);
00153 SetVar g2(this, IntSet::empty, 1, players-1);
00154 SetVar zero1(this, IntSet::empty,0,0);
00155 SetVar zero2(this, IntSet::empty,0,0);
00156 rel(this, g1, SOT_DUNION, zero1, SRT_EQ, group(w,0));
00157 rel(this, g2, SOT_DUNION, zero2, SRT_EQ, group(w+1,0));
00158 IntVar minG1(this, 0, players-1);
00159 IntVar minG2(this, 0, players-1);
00160 min(this, g1, minG1);
00161 min(this, g2, minG2);
00162 rel(this, minG1, IRT_LE, minG2);
00163 }
00164
00165
00166
00167 for (int w=0; w<weeks; w++) {
00168 for (int p=0; p<players; p++) {
00169 SetVar thisPlayer(this, p,p, 0, players-1);
00170 SetVarArgs thisWeek(groups);
00171 for (int g=0; g<groups; g++)
00172 thisWeek[g] = group(w,g);
00173 selectSet(this, thisWeek, groupInv(w,p), thisPlayer);
00174 }
00175 }
00176
00177
00178
00179 for (int w=0; w<weeks; w++) {
00180 for (int p=0; p<groups; p++) {
00181 rel(this, groupInv(w,p), IRT_LQ, p);
00182 }
00183 }
00184
00185 }
00186
00187 branch(this, groupsS, SETBVAR_MIN_UNKNOWN_ELEM, SETBVAL_MIN);
00188 }
00189
00190 Golf(bool share, Golf& s) : Example(share,s),
00191 groups(s.groups), playersInGroup(s.playersInGroup),
00192 weeks(s.weeks), players(s.players) {
00193 groupsS.update(this, share, s.groupsS);
00194 }
00195
00196 virtual Space*
00197 copy(bool share) {
00198 return new Golf(share,*this);
00199 }
00200
00201 virtual void
00202 print(void) {
00203
00204 std::cout << "Tournament plan" << std::endl;
00205
00206 for (int w=0; w<weeks; w++) {
00207 std::cout << "Week " << w << ": " << std::endl << " ";
00208 for (int g=0; g<groups; g++) {
00209 SetVarGlbValues glb(group(w,g));
00210 std::cout << "(" << glb.val();
00211 ++glb;
00212 while(glb()) {
00213 std::cout << " " << glb.val();
00214 ++glb;
00215 }
00216 std::cout << ")";
00217 if (g < groups-1) std::cout << " ";
00218 if (g > 0 && g % 4 == 0) std::cout << std::endl << " ";
00219 }
00220 std::cout << std::endl;
00221 }
00222
00223 }
00224 };
00225
00226 int
00227 main(int argc, char** argv) {
00228 Options o("Golf");
00229 o.parse(argc,argv);
00230 o.solutions = 1;
00231 if (o.size >= n_examples) {
00232 std::cerr << "Error: size must be between 0 and " << n_examples - 1
00233 << std::endl;
00234 return 1;
00235 }
00236 Example::run<Golf,DFS>(o);
00237 return 0;
00238 }
00239
00240
00241