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 "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 for (int w=0; w < weeks; w++) {
00119 for (int p=0; p < players; p++) {
00120 BoolVarArgs bs(groups);
00121 for (int g=0; g<groups; g++) {
00122 BoolVar b(this,0,1);
00123 dom(this, group(w,g), SRT_SUP, p, b);
00124 bs[g] = b;
00125 }
00126 linear(this, bs, IRT_EQ, 1);
00127 }
00128 }
00129
00130
00131 for (int w=0; w<weeks; w++) {
00132 for (int g=0; g<groups-1; g++) {
00133 IntVar minG1(this, 0, players-1);
00134 IntVar minG2(this, 0, players-1);
00135 SetVar g1 = group(w,g);
00136 SetVar g2 = group(w,g+1);
00137 minElement(this, g1, minG1);
00138 minElement(this, g2, minG2);
00139 rel(this, minG1, IRT_LE, minG2);
00140 }
00141 }
00142
00143
00144
00145 for (int w=0; w<weeks-1; w++) {
00146 SetVar g1(this, IntSet::empty, 1, players-1);
00147 SetVar g2(this, IntSet::empty, 1, players-1);
00148 SetVar zero1(this, IntSet::empty,0,0);
00149 SetVar zero2(this, IntSet::empty,0,0);
00150 rel(this, g1, SOT_DUNION, zero1, SRT_EQ, group(w,0));
00151 rel(this, g2, SOT_DUNION, zero2, SRT_EQ, group(w+1,0));
00152 IntVar minG1(this, 0, players-1);
00153 IntVar minG2(this, 0, players-1);
00154 minElement(this, g1, minG1);
00155 minElement(this, g2, minG2);
00156 rel(this, minG1, IRT_LE, minG2);
00157 }
00158
00159
00160
00161 for (int w=0; w<weeks; w++) {
00162 for (int p=0; p<players; p++) {
00163 SetVar thisPlayer(this, p,p, 0, players-1);
00164 SetVarArgs thisWeek(groups);
00165 for (int g=0; g<groups; g++)
00166 thisWeek[g] = group(w,g);
00167 selectSets(this, thisWeek, groupInv(w,p), thisPlayer);
00168 }
00169 }
00170
00171
00172
00173 for (int w=0; w<weeks; w++) {
00174 for (int p=0; p<groups; p++) {
00175 rel(this, groupInv(w,p), IRT_LQ, p);
00176 }
00177 }
00178
00179 }
00180
00181 branch(this, groupsS, SETBVAR_MIN_UNKNOWN_ELEM, SETBVAL_MIN);
00182 }
00183
00184 Golf(bool share, Golf& s) : Example(share,s),
00185 groups(s.groups), playersInGroup(s.playersInGroup),
00186 weeks(s.weeks), players(s.players) {
00187 groupsS.update(this, share, s.groupsS);
00188 }
00189
00190 virtual Space*
00191 copy(bool share) {
00192 return new Golf(share,*this);
00193 }
00194
00195 virtual void
00196 print(void) {
00197
00198 std::cout << "Tournament plan" << std::endl;
00199
00200 for (int w=0; w<weeks; w++) {
00201 std::cout << "Week " << w << ": " << std::endl << " ";
00202 for (int g=0; g<groups; g++) {
00203 SetVarGlbValues glb(group(w,g));
00204 std::cout << "(" << glb.val();
00205 ++glb;
00206 while(glb()) {
00207 std::cout << " " << glb.val();
00208 ++glb;
00209 }
00210 std::cout << ")";
00211 if (g < groups-1) std::cout << " ";
00212 if (g > 0 && g % 4 == 0) std::cout << std::endl << " ";
00213 }
00214 std::cout << std::endl;
00215 }
00216
00217 }
00218 };
00219
00220 int
00221 main(int argc, char** argv) {
00222 Options o("Golf");
00223 o.parse(argc,argv);
00224 o.solutions = 1;
00225 if (o.size >= n_examples) {
00226 std::cerr << "Error: size must be between 0 and " << n_examples - 1
00227 << std::endl;
00228 return 1;
00229 }
00230 Example::run<Golf,DFS>(o);
00231 return 0;
00232 }
00233
00234
00235