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 #include "test/branch.hh"
00041
00042 #include <algorithm>
00043 #include <map>
00044 #include <vector>
00045 #include <iostream>
00046
00047 #include <gecode/kernel.hh>
00048 #include <gecode/int.hh>
00049 #ifdef GECODE_HAS_SET_VARS
00050 #include <gecode/set.hh>
00051 #endif
00052 #ifdef GECODE_HAS_FLOAT_VARS
00053 #include <gecode/float.hh>
00054 #endif
00055
00056 #include <gecode/search.hh>
00057
00058 namespace Test { namespace Branch {
00059
00061 double tbl(const Gecode::Space&, double w, double b) {
00062 return (w + (b-w)/2.0);
00063 }
00064
00066 class IntTestSpace : public Gecode::Space {
00067 public:
00069 Gecode::IntVarArray x;
00071 Gecode::IntVarBranch vara, varb;
00073 Gecode::IntValBranch val;
00075 IntTestSpace(int n, Gecode::IntSet& d)
00076 : x(*this, n, d),
00077 vara(Gecode::INT_VAR_NONE()), varb(Gecode::INT_VAR_NONE()),
00078 val(Gecode::INT_VAL_MIN()) {}
00080 IntTestSpace(IntTestSpace& s)
00081 : Gecode::Space(s), vara(s.vara), varb(s.varb), val(s.val) {
00082 x.update(*this, s.x);
00083 }
00085 virtual Gecode::Space* copy(void) {
00086 return new IntTestSpace(*this);
00087 }
00088 };
00089
00091 class BoolTestSpace : public Gecode::Space {
00092 public:
00094 Gecode::BoolVarArray x;
00096 BoolTestSpace(int n)
00097 : x(*this, n, 0, 1) {}
00099 BoolTestSpace(BoolTestSpace& s)
00100 : Gecode::Space(s) {
00101 x.update(*this, s.x);
00102 }
00104 virtual Gecode::Space* copy(void) {
00105 return new BoolTestSpace(*this);
00106 }
00107 };
00108
00109 #ifdef GECODE_HAS_SET_VARS
00110
00111 class SetTestSpace : public Gecode::Space {
00112 public:
00114 Gecode::SetVarArray x;
00116 SetTestSpace(int n, Gecode::IntSet& d)
00117 : x(*this, n, Gecode::IntSet::empty, d) {}
00119 SetTestSpace(SetTestSpace& s)
00120 : Gecode::Space(s) {
00121 x.update(*this, s.x);
00122 }
00124 virtual Gecode::Space* copy(void) {
00125 return new SetTestSpace(*this);
00126 }
00127 };
00128 #endif
00129
00130 #ifdef GECODE_HAS_FLOAT_VARS
00131
00132 class FloatTestSpace : public Gecode::Space {
00133 public:
00135 Gecode::FloatVarArray x;
00137 FloatTestSpace(int n, Gecode::FloatVal& d)
00138 : x(*this, n, d.min(), d.max()) {}
00140 FloatTestSpace(FloatTestSpace& s)
00141 : Gecode::Space(s) {
00142 x.update(*this, s.x);
00143 }
00145 virtual Gecode::Space* copy(void) {
00146 return new FloatTestSpace(*this);
00147 }
00148 };
00149 #endif
00150
00156
00157 const char* int_var_branch_name[] = {
00158 "SINGLE VARIABLE",
00159 "INT_VAR_NONE",
00160 "INT_VAR_RND",
00161 "INT_VAR_MERIT_MIN",
00162 "INT_VAR_MERIT_MAX",
00163 "INT_VAR_DEGREE_MIN",
00164 "INT_VAR_DEGREE_MAX",
00165 "INT_VAR_AFC_MIN",
00166 "INT_VAR_AFC_MAX",
00167 "INT_VAR_ACTION_MIN",
00168 "INT_VAR_ACTION_MAX",
00169 "INT_VAR_CHB_MIN",
00170 "INT_VAR_CHB_MAX",
00171 "INT_VAR_MIN_MIN",
00172 "INT_VAR_MIN_MAX",
00173 "INT_VAR_MAX_MIN",
00174 "INT_VAR_MAX_MAX",
00175 "INT_VAR_SIZE_MIN",
00176 "INT_VAR_SIZE_MAX",
00177 "INT_VAR_DEGREE_SIZE_MIN",
00178 "INT_VAR_DEGREE_SIZE_MAX",
00179 "INT_VAR_AFC_SIZE_MIN",
00180 "INT_VAR_AFC_SIZE_MAX",
00181 "INT_VAR_ACTION_SIZE_MIN",
00182 "INT_VAR_ACTION_SIZE_MAX",
00183 "INT_VAR_CHB_SIZE_MIN",
00184 "INT_VAR_CHB_SIZE_MAX",
00185 "INT_VAR_REGRET_MIN_MIN",
00186 "INT_VAR_REGRET_MIN_MAX",
00187 "INT_VAR_REGRET_MAX_MIN",
00188 "INT_VAR_REGRET_MAX_MAX"
00189 };
00191 const int n_int_var_branch =
00192 sizeof(int_var_branch_name)/sizeof(const char*);
00194 const char* bool_var_branch_name[] = {
00195 "SINGLE VARIABLE",
00196 "BOOL_VAR_NONE",
00197 "BOOL_VAR_RND",
00198 "BOOL_VAR_MERIT_MIN",
00199 "BOOL_VAR_MERIT_MAX",
00200 "BOOL_VAR_DEGREE_MIN",
00201 "BOOL_VAR_DEGREE_MAX",
00202 "BOOL_VAR_AFC_MIN",
00203 "BOOL_VAR_AFC_MAX",
00204 "BOOL_VAR_ACTION_MIN",
00205 "BOOL_VAR_ACTION_MAX",
00206 "BOOL_VAR_CHB_MIN",
00207 "BOOL_VAR_CHB_MAX"
00208 };
00210 const int n_bool_var_branch =
00211 sizeof(bool_var_branch_name)/sizeof(const char*);
00213 double int_merit(const Gecode::Space&, Gecode::IntVar x, int) {
00214 return x.min();
00215 }
00217 double bool_merit(const Gecode::Space&, Gecode::BoolVar x, int) {
00218 return x.min();
00219 }
00221 const char* int_val_branch_name[] = {
00222 "INT_VAL_MIN",
00223 "INT_VAL_MED",
00224 "INT_VAL_MAX",
00225 "INT_VAL_RND",
00226 "INT_VAL_SPLIT_MIN",
00227 "INT_VAL_SPLIT_MAX",
00228 "INT_VAL_RANGE_MIN",
00229 "INT_VAL_RANGE_MAX",
00230 "INT_VAL",
00231 "INT_VALUES_MIN",
00232 "INT_VALUES_MAX"
00233 };
00235 const int n_int_val_branch =
00236 sizeof(int_val_branch_name)/sizeof(const char*);
00238 const char* bool_val_branch_name[] = {
00239 "BOOL_VAL_MIN",
00240 "BOOL_VAL_MAX",
00241 "BOOL_VAL_RND",
00242 "BOOL_VAL"
00243 };
00245 const int n_bool_val_branch =
00246 sizeof(bool_val_branch_name)/sizeof(const char*);
00248 int int_val(const Gecode::Space&, Gecode::IntVar x, int) {
00249 return x.min();
00250 }
00252 int bool_val(const Gecode::Space&, Gecode::BoolVar x, int) {
00253 return x.min();
00254 }
00256
00257 #ifdef GECODE_HAS_SET_VARS
00258
00263
00264 const char* set_var_branch_name[] = {
00265 "SINGLE VARIABLE",
00266 "SET_VAR_NONE",
00267 "SET_VAR_RND",
00268 "SET_VAR_MERIT_MIN",
00269 "SET_VAR_MERIT_MAX",
00270 "SET_VAR_DEGREE_MIN",
00271 "SET_VAR_DEGREE_MAX",
00272 "SET_VAR_AFC_MIN",
00273 "SET_VAR_AFC_MAX",
00274 "SET_VAR_ACTION_MIN",
00275 "SET_VAR_ACTION_MAX",
00276 "SET_VAR_CHB_MIN",
00277 "SET_VAR_CHB_MAX",
00278 "SET_VAR_MIN_MIN",
00279 "SET_VAR_MIN_MAX",
00280 "SET_VAR_MAX_MIN",
00281 "SET_VAR_MAX_MAX",
00282 "SET_VAR_SIZE_MIN",
00283 "SET_VAR_SIZE_MAX",
00284 "SET_VAR_DEGREE_SIZE_MIN",
00285 "SET_VAR_DEGREE_SIZE_MAX",
00286 "SET_VAR_AFC_SIZE_MIN",
00287 "SET_VAR_AFC_SIZE_MAX",
00288 "SET_VAR_ACTION_SIZE_MIN",
00289 "SET_VAR_ACTION_SIZE_MAX",
00290 "SET_VAR_CHB_SIZE_MIN",
00291 "SET_VAR_CHB_SIZE_MAX"
00292 };
00294 const int n_set_var_branch =
00295 sizeof(set_var_branch_name)/sizeof(const char*);
00297 double set_merit(const Gecode::Space&, Gecode::SetVar, int) {
00298 return 2.0;
00299 }
00301 const char* set_val_branch_name[] = {
00302 "SET_VAL_MIN_INC",
00303 "SET_VAL_MIN_EXC",
00304 "SET_VAL_MED_INC",
00305 "SET_VAL_MED_EXC",
00306 "SET_VAL_MAX_INC",
00307 "SET_VAL_MAX_EXC",
00308 "SET_VAL_RND_INC",
00309 "SET_VAL_RND_EXC",
00310 "SET_VAL"
00311 };
00313 const int n_set_val_branch =
00314 sizeof(set_val_branch_name)/sizeof(const char*);
00316 int set_val(const Gecode::Space&, Gecode::SetVar x, int) {
00317 Gecode::SetVarUnknownRanges r(x);
00318 return r.min();
00319 }
00321 #endif
00322
00323 #ifdef GECODE_HAS_FLOAT_VARS
00324
00329
00330 const char* float_var_branch_name[] = {
00331 "SINGLE VARIABLE",
00332 "FLOAT_VAR_NONE",
00333 "FLOAT_VAR_RND",
00334 "FLOAT_VAR_MERIT_MIN",
00335 "FLOAT_VAR_MERIT_MAX",
00336 "FLOAT_VAR_DEGREE_MIN",
00337 "FLOAT_VAR_DEGREE_MAX",
00338 "FLOAT_VAR_AFC_MIN",
00339 "FLOAT_VAR_AFC_MAX",
00340 "FLOAT_VAR_ACTION_MIN",
00341 "FLOAT_VAR_ACTION_MAX",
00342 "FLOAT_VAR_CHB_MIN",
00343 "FLOAT_VAR_CHB_MAX",
00344 "FLOAT_VAR_MIN_MIN",
00345 "FLOAT_VAR_MIN_MAX",
00346 "FLOAT_VAR_MAX_MIN",
00347 "FLOAT_VAR_MAX_MAX",
00348 "FLOAT_VAR_SIZE_MIN",
00349 "FLOAT_VAR_SIZE_MAX",
00350 "FLOAT_VAR_DEGREE_SIZE_MIN",
00351 "FLOAT_VAR_DEGREE_SIZE_MAX",
00352 "FLOAT_VAR_AFC_SIZE_MIN",
00353 "FLOAT_VAR_AFC_SIZE_MAX",
00354 "FLOAT_VAR_ACTION_SIZE_MIN",
00355 "FLOAT_VAR_ACTION_SIZE_MAX",
00356 "FLOAT_VAR_CHB_SIZE_MIN",
00357 "FLOAT_VAR_CHB_SIZE_MAX"
00358 };
00360 const int n_float_var_branch =
00361 sizeof(float_var_branch_name)/sizeof(const char*);
00363 double float_merit(const Gecode::Space&, Gecode::FloatVar x, int) {
00364 return static_cast<double>(x.degree());
00365 }
00367 const char* float_val_branch_name[] = {
00368 "FLOAT_VAL_SPLIT_MIN",
00369 "FLOAT_VAL_SPLIT_MAX",
00370 "FLOAT_VAL_SPLIT_RND",
00371 "FLOAT_VAL"
00372 };
00374 const int n_float_val_branch =
00375 sizeof(float_val_branch_name)/sizeof(const char*);
00377 Gecode::FloatNumBranch float_val(const Gecode::Space&,
00378 Gecode::FloatVar x, int) {
00379 Gecode::FloatNumBranch nl; nl.n=x.med(); nl.l=true;
00380 return nl;
00381 }
00383 #endif
00384
00386 class RunInfo {
00387 public:
00388 std::string var, val;
00389 unsigned int a_d, c_d;
00390 RunInfo(const std::string& vara, const std::string& varb,
00391 const std::string& valname,
00392 const Gecode::Search::Options& o)
00393 : var(vara + "::" + varb), val(valname), a_d(o.a_d), c_d(o.c_d) {}
00394 void print(std::ostream& o) const {
00395 o << "(" << var << ", " << val << ", " << a_d << ", " << c_d << ")";
00396 }
00397 };
00398
00399 }}
00400
00401 std::ostream&
00402 operator<<(std::ostream& os, const Test::Branch::RunInfo& ri) {
00403 ri.print(os);
00404 return os;
00405 }
00406
00407
00408 namespace Test { namespace Branch {
00409
00411 template<class TestSpace>
00412 int solutions(TestSpace* c, Gecode::Search::Options& o, int maxNbSol = -1) {
00413 o.a_d = Base::rand(10);
00414 o.c_d = Base::rand(10);
00415 Gecode::DFS<TestSpace> e_s(c, o);
00416 delete c;
00417
00418
00419 int s = 0;
00420 do {
00421 Gecode::Space* ex = e_s.next();
00422 if (ex == NULL) break;
00423 delete ex;
00424 ++s;
00425 if ((maxNbSol >= 0) && (maxNbSol == s)) break;
00426 } while (true);
00427 return s;
00428 }
00429
00430 IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
00431 : Base("Int::Branch::"+s), arity(a), dom(d) {
00432 }
00433
00434 bool
00435 IntTest::run(void) {
00436 using std::map;
00437 using std::vector;
00438 using std::string;
00439 using std::ostream;
00440 using namespace Gecode;
00441
00442
00443 map<int, vector<RunInfo> > results;
00444
00445 IntTestSpace* root = new IntTestSpace(arity,dom);
00446 post(*root, root->x);
00447 results.clear();
00448
00449 IntArgs d(arity);
00450 for (int i=arity; i--; )
00451 d[i]=i;
00452
00453 for (int vara = 0; vara<n_int_var_branch; vara++) {
00454 for (int varb = 1; varb<n_int_var_branch; varb++) {
00455 for (int val = 0; val<n_int_val_branch; val++) {
00456 Rnd r(1);
00457
00458 IntValBranch ivb;
00459 switch (val) {
00460 case 0: ivb = INT_VAL_MIN(); break;
00461 case 1: ivb = INT_VAL_MED(); break;
00462 case 2: ivb = INT_VAL_MAX(); break;
00463 case 3: ivb = INT_VAL_RND(r); break;
00464 case 4: ivb = INT_VAL_SPLIT_MIN(); break;
00465 case 5: ivb = INT_VAL_SPLIT_MAX(); break;
00466 case 6: ivb = INT_VAL_RANGE_MIN(); break;
00467 case 7: ivb = INT_VAL_RANGE_MAX(); break;
00468 case 8: ivb = INT_VAL(&int_val); break;
00469 case 9: ivb = INT_VALUES_MIN(); break;
00470 case 10: ivb = INT_VALUES_MAX(); break;
00471 }
00472
00473 IntTestSpace* c = static_cast<IntTestSpace*>(root->clone());
00474
00475 if ((vara == 0) && (val < 11)) {
00476 for (int i=0; i<c->x.size(); i++)
00477 branch(*c, c->x[i], ivb);
00478 } else {
00479 Rnd ra(1);
00480 IntVarBranch ivba;
00481 IntAction iaa(*c, c->x, 0.9);
00482 IntCHB ica(*c, c->x);
00483 switch (vara) {
00484 case 0: ivba = INT_VAR_NONE(); break;
00485 case 1: ivba = INT_VAR_NONE(); break;
00486 case 2: ivba = INT_VAR_RND(ra); break;
00487 case 3: ivba = INT_VAR_MERIT_MIN(&int_merit); break;
00488 case 4: ivba = INT_VAR_MERIT_MAX(&int_merit); break;
00489 case 5: ivba = INT_VAR_DEGREE_MIN(); break;
00490 case 6: ivba = INT_VAR_DEGREE_MAX(); break;
00491 case 7: ivba = INT_VAR_AFC_MIN(0.5); break;
00492 case 8: ivba = INT_VAR_AFC_MAX(0.5); break;
00493 case 9: ivba = INT_VAR_ACTION_MIN(iaa); break;
00494 case 10: ivba = INT_VAR_ACTION_MAX(iaa); break;
00495 case 11: ivba = INT_VAR_CHB_MIN(ica); break;
00496 case 12: ivba = INT_VAR_CHB_MAX(ica); break;
00497 case 13: ivba = INT_VAR_MIN_MIN(); break;
00498 case 14: ivba = INT_VAR_MIN_MAX(); break;
00499 case 15: ivba = INT_VAR_MAX_MIN(); break;
00500 case 16: ivba = INT_VAR_MAX_MAX(); break;
00501 case 17: ivba = INT_VAR_SIZE_MIN(); break;
00502 case 18: ivba = INT_VAR_SIZE_MAX(); break;
00503 case 19: ivba = INT_VAR_DEGREE_SIZE_MIN(); break;
00504 case 20: ivba = INT_VAR_DEGREE_SIZE_MAX(); break;
00505 case 21: ivba = INT_VAR_AFC_SIZE_MIN(); break;
00506 case 22: ivba = INT_VAR_AFC_SIZE_MAX(); break;
00507 case 23: ivba = INT_VAR_ACTION_SIZE_MIN(iaa); break;
00508 case 24: ivba = INT_VAR_ACTION_SIZE_MAX(iaa); break;
00509 case 25: ivba = INT_VAR_CHB_SIZE_MIN(ica); break;
00510 case 26: ivba = INT_VAR_CHB_SIZE_MAX(ica); break;
00511 case 27: ivba = INT_VAR_REGRET_MIN_MIN(); break;
00512 case 28: ivba = INT_VAR_REGRET_MIN_MAX(); break;
00513 case 29: ivba = INT_VAR_REGRET_MAX_MIN(); break;
00514 case 30: ivba = INT_VAR_REGRET_MAX_MAX(); break;
00515 }
00516
00517 Rnd rb(2);
00518 IntVarBranch ivbb;
00519 IntAction iab(*c, c->x, 0.9, &int_merit);
00520 IntCHB icb(*c, c->x, &int_merit);
00521 switch (varb) {
00522 case 0: ivbb = INT_VAR_NONE(); break;
00523 case 1: ivbb = INT_VAR_NONE(); break;
00524 case 2: ivbb = INT_VAR_RND(rb); break;
00525 case 3: ivbb = INT_VAR_MERIT_MIN(&int_merit,&tbl); break;
00526 case 4: ivbb = INT_VAR_MERIT_MAX(&int_merit,&tbl); break;
00527 case 5: ivbb = INT_VAR_DEGREE_MIN(&tbl); break;
00528 case 6: ivbb = INT_VAR_DEGREE_MAX(&tbl); break;
00529 case 7: ivbb = INT_VAR_AFC_MIN(0.5,&tbl); break;
00530 case 8: ivbb = INT_VAR_AFC_MAX(0.5,&tbl); break;
00531 case 9: ivbb = INT_VAR_ACTION_MIN(iab,&tbl); break;
00532 case 10: ivbb = INT_VAR_ACTION_MAX(iab,&tbl); break;
00533 case 11: ivbb = INT_VAR_CHB_MIN(icb,&tbl); break;
00534 case 12: ivbb = INT_VAR_CHB_MAX(icb,&tbl); break;
00535 case 13: ivbb = INT_VAR_MIN_MIN(&tbl); break;
00536 case 14: ivbb = INT_VAR_MIN_MAX(&tbl); break;
00537 case 15: ivbb = INT_VAR_MAX_MIN(&tbl); break;
00538 case 16: ivbb = INT_VAR_MAX_MAX(&tbl); break;
00539 case 17: ivbb = INT_VAR_SIZE_MIN(&tbl); break;
00540 case 18: ivbb = INT_VAR_SIZE_MAX(&tbl); break;
00541 case 19: ivbb = INT_VAR_DEGREE_SIZE_MIN(&tbl); break;
00542 case 20: ivbb = INT_VAR_DEGREE_SIZE_MAX(&tbl); break;
00543 case 21: ivbb = INT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
00544 case 22: ivbb = INT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
00545 case 23: ivbb = INT_VAR_ACTION_SIZE_MIN(iab,&tbl); break;
00546 case 24: ivbb = INT_VAR_ACTION_SIZE_MAX(iab,&tbl); break;
00547 case 25: ivbb = INT_VAR_CHB_SIZE_MIN(icb,&tbl); break;
00548 case 26: ivbb = INT_VAR_CHB_SIZE_MAX(icb,&tbl); break;
00549 case 27: ivbb = INT_VAR_REGRET_MIN_MIN(&tbl); break;
00550 case 28: ivbb = INT_VAR_REGRET_MIN_MAX(&tbl); break;
00551 case 29: ivbb = INT_VAR_REGRET_MAX_MIN(&tbl); break;
00552 case 30: ivbb = INT_VAR_REGRET_MAX_MAX(&tbl); break;
00553 }
00554
00555 switch (Base::rand(9U)) {
00556 case 0U:
00557 branch(*c, c->x, ivba, ivb); break;
00558 case 1U:
00559 branch(*c, c->x, ivbb, ivb); break;
00560 case 2U:
00561 branch(*c, c->x, tiebreak(ivba,ivbb), ivb); break;
00562 case 3U:
00563 branch(*c, c->x, tiebreak(ivbb,ivba), ivb); break;
00564 case 4U:
00565 branch(*c, c->x, tiebreak(ivba,ivba,ivbb), ivb); break;
00566 case 5U:
00567 branch(*c, c->x, tiebreak(ivba,ivbb,ivbb), ivb); break;
00568 case 6U:
00569 branch(*c, c->x, tiebreak(ivbb,ivba,ivba), ivb); break;
00570 case 7U:
00571 branch(*c, c->x, tiebreak(ivba,ivba,ivbb,ivba), ivb); break;
00572 case 8U:
00573 branch(*c, c->x, tiebreak(ivbb,ivba,ivbb,ivba), ivb); break;
00574 }
00575
00576 }
00577 Gecode::Search::Options o;
00578 results[solutions(c,o)].push_back
00579 (RunInfo(int_var_branch_name[vara],
00580 int_var_branch_name[varb],
00581 int_val_branch_name[val],
00582 o));
00583 }
00584 }
00585 }
00586 if (results.size() > 1)
00587 goto failed;
00588 delete root;
00589 return true;
00590 failed:
00591 std::cout << "FAILURE" << std::endl;
00592 for (map<int, vector<RunInfo> >::iterator it = results.begin();
00593 it != results.end(); ++it) {
00594 std::cout << "Number of solutions: " << it->first << std::endl;
00595 for (unsigned int i = 0; i < it->second.size(); ++i)
00596 std::cout << it->second[i] << " ";
00597 std::cout << std::endl;
00598 }
00599
00600 delete root;
00601 return results.size() == 1;
00602 }
00603
00604 BoolTest::BoolTest(const std::string& s, int a)
00605 : Base("Bool::Branch::"+s), arity(a) {
00606 }
00607
00608 bool
00609 BoolTest::run(void) {
00610 using std::map;
00611 using std::vector;
00612 using std::string;
00613 using std::ostream;
00614 using namespace Gecode;
00615
00616
00617 map<int, vector<RunInfo> > results;
00618
00619 BoolTestSpace* root = new BoolTestSpace(arity);
00620 post(*root, root->x);
00621 results.clear();
00622
00623 for (int vara = 0; vara<n_bool_var_branch; vara++) {
00624 for (int varb = 1; varb<n_bool_var_branch; varb++) {
00625 for (int val = 0; val<n_bool_val_branch; val++) {
00626
00627 Rnd r(1);
00628
00629 BoolValBranch bvb;
00630 switch (val) {
00631 case 0: bvb = BOOL_VAL_MIN(); break;
00632 case 1: bvb = BOOL_VAL_MAX(); break;
00633 case 2: bvb = BOOL_VAL_RND(r); break;
00634 case 3: bvb = BOOL_VAL(&bool_val); break;
00635 }
00636
00637 BoolTestSpace* c = static_cast<BoolTestSpace*>(root->clone());
00638
00639 if (vara == 0) {
00640 for (int i=0; i<c->x.size(); i++)
00641 branch(*c, c->x[i], bvb);
00642 } else {
00643
00644
00645 Rnd ra(1);
00646 BoolVarBranch bvba;
00647 BoolAction baa(*c, c->x, 0.9);
00648 BoolCHB bca(*c, c->x);
00649 switch (vara) {
00650 case 0: bvba = BOOL_VAR_NONE(); break;
00651 case 1: bvba = BOOL_VAR_NONE(); break;
00652 case 2: bvba = BOOL_VAR_RND(ra); break;
00653 case 3: bvba = BOOL_VAR_MERIT_MIN(&bool_merit); break;
00654 case 4: bvba = BOOL_VAR_MERIT_MAX(&bool_merit); break;
00655 case 5: bvba = BOOL_VAR_DEGREE_MIN(); break;
00656 case 6: bvba = BOOL_VAR_DEGREE_MAX(); break;
00657 case 7: bvba = BOOL_VAR_AFC_MIN(0.5); break;
00658 case 8: bvba = BOOL_VAR_AFC_MAX(0.5); break;
00659 case 9: bvba = BOOL_VAR_ACTION_MIN(baa); break;
00660 case 10: bvba = BOOL_VAR_ACTION_MAX(baa); break;
00661 case 11: bvba = BOOL_VAR_CHB_MIN(bca); break;
00662 case 12: bvba = BOOL_VAR_CHB_MAX(bca); break;
00663 }
00664
00665 Rnd rb(2);
00666 BoolVarBranch bvbb;
00667 BoolAction bab(*c, c->x, 0.9, &bool_merit);
00668 BoolCHB bcb(*c, c->x, &bool_merit);
00669 switch (varb) {
00670 case 0: bvbb = BOOL_VAR_NONE(); break;
00671 case 1: bvbb = BOOL_VAR_NONE(); break;
00672 case 2: bvbb = BOOL_VAR_RND(rb); break;
00673 case 3: bvbb = BOOL_VAR_MERIT_MIN(&bool_merit,&tbl); break;
00674 case 4: bvbb = BOOL_VAR_MERIT_MAX(&bool_merit,&tbl); break;
00675 case 5: bvbb = BOOL_VAR_DEGREE_MIN(&tbl); break;
00676 case 6: bvbb = BOOL_VAR_DEGREE_MAX(&tbl); break;
00677 case 7: bvbb = BOOL_VAR_AFC_MIN(0.5,&tbl); break;
00678 case 8: bvbb = BOOL_VAR_AFC_MAX(0.5,&tbl); break;
00679 case 9: bvbb = BOOL_VAR_ACTION_MIN(bab,&tbl); break;
00680 case 10: bvbb = BOOL_VAR_ACTION_MAX(bab,&tbl); break;
00681 case 11: bvbb = BOOL_VAR_CHB_MIN(bcb,&tbl); break;
00682 case 12: bvbb = BOOL_VAR_CHB_MAX(bcb,&tbl); break;
00683 }
00684
00685 switch (Base::rand(9U)) {
00686 case 0U:
00687 branch(*c, c->x, bvba, bvb); break;
00688 case 1U:
00689 branch(*c, c->x, bvbb, bvb); break;
00690 case 2U:
00691 branch(*c, c->x, tiebreak(bvba,bvbb), bvb); break;
00692 case 3U:
00693 branch(*c, c->x, tiebreak(bvbb,bvba), bvb); break;
00694 case 4U:
00695 branch(*c, c->x, tiebreak(bvba,bvba,bvbb), bvb); break;
00696 case 5U:
00697 branch(*c, c->x, tiebreak(bvba,bvbb,bvbb), bvb); break;
00698 case 6U:
00699 branch(*c, c->x, tiebreak(bvbb,bvba,bvba), bvb); break;
00700 case 7U:
00701 branch(*c, c->x, tiebreak(bvba,bvba,bvbb,bvba), bvb); break;
00702 case 8U:
00703 branch(*c, c->x, tiebreak(bvbb,bvba,bvbb,bvba), bvb); break;
00704 }
00705
00706 }
00707 Gecode::Search::Options o;
00708 results[solutions(c,o)].push_back
00709 (RunInfo(int_var_branch_name[vara],
00710 int_var_branch_name[varb],
00711 int_val_branch_name[val],
00712 o));
00713 }
00714 }
00715 }
00716 if (results.size() > 1)
00717 goto failed;
00718 delete root;
00719 return true;
00720 failed:
00721 std::cout << "FAILURE" << std::endl;
00722 for (map<int, vector<RunInfo> >::iterator it = results.begin();
00723 it != results.end(); ++it) {
00724 std::cout << "Number of solutions: " << it->first << std::endl;
00725 for (unsigned int i = 0; i < it->second.size(); ++i)
00726 std::cout << it->second[i] << " ";
00727 std::cout << std::endl;
00728 }
00729
00730 delete root;
00731 return results.size() == 1;
00732 }
00733
00734 #ifdef GECODE_HAS_SET_VARS
00735 SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
00736 : Base("Set::Branch::"+s), arity(a), dom(d) {
00737 }
00738
00739 bool
00740 SetTest::run(void) {
00741 using std::map;
00742 using std::vector;
00743 using std::string;
00744 using std::ostream;
00745 using namespace Gecode;
00746
00747
00748 map<int, vector<RunInfo> > results;
00749
00750 SetTestSpace* root = new SetTestSpace(arity,dom);
00751 post(*root, root->x);
00752 root->status();
00753 results.clear();
00754
00755 for (int vara = 0; vara<n_set_var_branch; vara++) {
00756 for (int varb = 1; varb<n_set_var_branch; varb++) {
00757 for (int val = 0; val<n_set_val_branch; val++) {
00758 Rnd r(1);
00759
00760 SetValBranch svb;
00761 switch (val) {
00762 case 0: svb = SET_VAL_MIN_INC(); break;
00763 case 1: svb = SET_VAL_MIN_EXC(); break;
00764 case 2: svb = SET_VAL_MED_INC(); break;
00765 case 3: svb = SET_VAL_MED_EXC(); break;
00766 case 4: svb = SET_VAL_MAX_INC(); break;
00767 case 5: svb = SET_VAL_MAX_EXC(); break;
00768 case 6: svb = SET_VAL_RND_INC(r); break;
00769 case 7: svb = SET_VAL_RND_EXC(r); break;
00770 case 8: svb = SET_VAL(&set_val); break;
00771 }
00772
00773 SetTestSpace* c = static_cast<SetTestSpace*>(root->clone());
00774
00775 if (vara == 0) {
00776 for (int i=0; i<c->x.size(); i++)
00777 branch(*c, c->x[i], svb);
00778 } else {
00779 Rnd ra(1);
00780 SetVarBranch svba;
00781 SetAction saa(*c, c->x, 0.9);
00782 SetCHB sca(*c, c->x);
00783 switch (vara) {
00784 case 0: break;
00785 case 1: svba = SET_VAR_NONE(); break;
00786 case 2: svba = SET_VAR_RND(ra); break;
00787 case 3: svba = SET_VAR_MERIT_MIN(&set_merit); break;
00788 case 4: svba = SET_VAR_MERIT_MAX(&set_merit); break;
00789 case 5: svba = SET_VAR_DEGREE_MIN(); break;
00790 case 6: svba = SET_VAR_DEGREE_MAX(); break;
00791 case 7: svba = SET_VAR_AFC_MIN(0.5); break;
00792 case 8: svba = SET_VAR_AFC_MAX(0.5); break;
00793 case 9: svba = SET_VAR_ACTION_MIN(saa); break;
00794 case 10: svba = SET_VAR_ACTION_MAX(saa); break;
00795 case 11: svba = SET_VAR_CHB_MIN(sca); break;
00796 case 12: svba = SET_VAR_CHB_MAX(sca); break;
00797 case 13: svba = SET_VAR_MIN_MIN(); break;
00798 case 14: svba = SET_VAR_MIN_MAX(); break;
00799 case 15: svba = SET_VAR_MAX_MIN(); break;
00800 case 16: svba = SET_VAR_MAX_MAX(); break;
00801 case 17: svba = SET_VAR_SIZE_MIN(); break;
00802 case 18: svba = SET_VAR_SIZE_MAX(); break;
00803 case 19: svba = SET_VAR_DEGREE_SIZE_MIN(); break;
00804 case 20: svba = SET_VAR_DEGREE_SIZE_MAX(); break;
00805 case 21: svba = SET_VAR_AFC_SIZE_MIN(); break;
00806 case 22: svba = SET_VAR_AFC_SIZE_MAX(); break;
00807 case 23: svba = SET_VAR_ACTION_SIZE_MIN(saa); break;
00808 case 24: svba = SET_VAR_ACTION_SIZE_MAX(saa); break;
00809 case 25: svba = SET_VAR_CHB_SIZE_MIN(sca); break;
00810 case 26: svba = SET_VAR_CHB_SIZE_MAX(sca); break;
00811 }
00812
00813 Rnd rb(2);
00814 SetVarBranch svbb;
00815 SetAction sab(*c, c->x, 0.9, &set_merit);
00816 SetCHB scb(*c, c->x, &set_merit);
00817 switch (varb) {
00818 case 0: break;
00819 case 1: svbb = SET_VAR_NONE(); break;
00820 case 2: svbb = SET_VAR_RND(rb); break;
00821 case 3: svbb = SET_VAR_MERIT_MIN(&set_merit,&tbl); break;
00822 case 4: svbb = SET_VAR_MERIT_MAX(&set_merit,&tbl); break;
00823 case 5: svbb = SET_VAR_DEGREE_MIN(&tbl); break;
00824 case 6: svbb = SET_VAR_DEGREE_MAX(&tbl); break;
00825 case 7: svbb = SET_VAR_AFC_MIN(0.5,&tbl); break;
00826 case 8: svbb = SET_VAR_AFC_MAX(0.5,&tbl); break;
00827 case 9: svbb = SET_VAR_ACTION_MIN(sab,&tbl); break;
00828 case 10: svbb = SET_VAR_ACTION_MAX(sab,&tbl); break;
00829 case 11: svbb = SET_VAR_CHB_MIN(scb,&tbl); break;
00830 case 12: svbb = SET_VAR_CHB_MAX(scb,&tbl); break;
00831 case 13: svbb = SET_VAR_MIN_MIN(&tbl); break;
00832 case 14: svbb = SET_VAR_MIN_MAX(&tbl); break;
00833 case 15: svbb = SET_VAR_MAX_MIN(&tbl); break;
00834 case 16: svbb = SET_VAR_MAX_MAX(&tbl); break;
00835 case 17: svbb = SET_VAR_SIZE_MIN(&tbl); break;
00836 case 18: svbb = SET_VAR_SIZE_MAX(&tbl); break;
00837 case 19: svbb = SET_VAR_DEGREE_SIZE_MIN(&tbl); break;
00838 case 20: svbb = SET_VAR_DEGREE_SIZE_MAX(&tbl); break;
00839 case 21: svbb = SET_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
00840 case 22: svbb = SET_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
00841 case 23: svbb = SET_VAR_ACTION_SIZE_MIN(sab,&tbl); break;
00842 case 24: svbb = SET_VAR_ACTION_SIZE_MAX(sab,&tbl); break;
00843 case 25: svbb = SET_VAR_CHB_SIZE_MIN(scb,&tbl); break;
00844 case 26: svbb = SET_VAR_CHB_SIZE_MAX(scb,&tbl); break;
00845 }
00846
00847 switch (Base::rand(9U)) {
00848 case 0U:
00849 branch(*c, c->x, svba, svb); break;
00850 case 1U:
00851 branch(*c, c->x, svbb, svb); break;
00852 case 2U:
00853 branch(*c, c->x, tiebreak(svba,svbb), svb); break;
00854 case 3U:
00855 branch(*c, c->x, tiebreak(svbb,svba), svb); break;
00856 case 4U:
00857 branch(*c, c->x, tiebreak(svba,svba,svbb), svb); break;
00858 case 5U:
00859 branch(*c, c->x, tiebreak(svba,svbb,svbb), svb); break;
00860 case 6U:
00861 branch(*c, c->x, tiebreak(svbb,svba,svba), svb); break;
00862 case 7U:
00863 branch(*c, c->x, tiebreak(svba,svba,svbb,svba), svb); break;
00864 case 8U:
00865 branch(*c, c->x, tiebreak(svbb,svba,svbb,svba), svb); break;
00866 }
00867
00868 }
00869 Gecode::Search::Options o;
00870 results[solutions(c,o)].push_back
00871 (RunInfo(set_var_branch_name[vara],
00872 set_var_branch_name[varb],
00873 set_val_branch_name[val],
00874 o));
00875 }
00876 }
00877 }
00878 if (results.size() > 1)
00879 goto failed;
00880 delete root;
00881 return true;
00882 failed:
00883 std::cout << "FAILURE" << std::endl;
00884 for (map<int, vector<RunInfo> >::iterator it = results.begin();
00885 it != results.end(); ++it) {
00886 std::cout << "Number of solutions: " << it->first << std::endl;
00887 for (unsigned int i = 0; i < it->second.size(); ++i)
00888 std::cout << it->second[i] << " ";
00889 std::cout << std::endl;
00890 }
00891
00892 delete root;
00893 return results.size() == 1;
00894 }
00895 #endif
00896
00897 #ifdef GECODE_HAS_FLOAT_VARS
00898 FloatTest::FloatTest(const std::string& s, int a, const Gecode::FloatVal& d, int nbs)
00899 : Base("Float::Branch::"+s), arity(a), dom(d), nbSols(nbs) {
00900 }
00901
00902 bool
00903 FloatTest::run(void) {
00904 using std::map;
00905 using std::vector;
00906 using std::string;
00907 using std::ostream;
00908 using namespace Gecode;
00909
00910
00911 map<int, vector<RunInfo> > results;
00912
00913 FloatTestSpace* root = new FloatTestSpace(arity,dom);
00914 post(*root, root->x);
00915 root->status();
00916 results.clear();
00917
00918 for (int vara = 0; vara<n_float_var_branch; vara++) {
00919 for (int varb = 1; varb<n_float_var_branch; varb++) {
00920 for (int val = 0; val<n_float_val_branch; val++) {
00921 Rnd r(1);
00922
00923 FloatValBranch fvb;
00924 switch (val) {
00925 case 0: fvb = FLOAT_VAL_SPLIT_MIN(); break;
00926 case 1: fvb = FLOAT_VAL_SPLIT_MAX(); break;
00927 case 2: fvb = FLOAT_VAL_SPLIT_RND(r); break;
00928 case 3: fvb = FLOAT_VAL(&float_val); break;
00929 }
00930
00931 FloatTestSpace* c = static_cast<FloatTestSpace*>(root->clone());
00932 if (vara == 0) {
00933 for (int i=0; i<c->x.size(); i++)
00934 branch(*c, c->x[i], fvb);
00935 } else {
00936 Rnd ra(1);
00937 FloatVarBranch fvba;
00938 FloatAction faa(*c, c->x, 0.9);
00939 FloatCHB fca(*c, c->x);
00940 switch (vara) {
00941 case 0: break;
00942 case 1: fvba = FLOAT_VAR_NONE(); break;
00943 case 2: fvba = FLOAT_VAR_RND(ra); break;
00944 case 3: fvba = FLOAT_VAR_MERIT_MIN(&float_merit); break;
00945 case 4: fvba = FLOAT_VAR_MERIT_MAX(&float_merit); break;
00946 case 5: fvba = FLOAT_VAR_DEGREE_MIN(); break;
00947 case 6: fvba = FLOAT_VAR_DEGREE_MAX(); break;
00948 case 7: fvba = FLOAT_VAR_AFC_MIN(0.5); break;
00949 case 8: fvba = FLOAT_VAR_AFC_MAX(0.5); break;
00950 case 9: fvba = FLOAT_VAR_ACTION_MIN(faa); break;
00951 case 10: fvba = FLOAT_VAR_ACTION_MAX(faa); break;
00952 case 11: fvba = FLOAT_VAR_CHB_MIN(fca); break;
00953 case 12: fvba = FLOAT_VAR_CHB_MAX(fca); break;
00954 case 13: fvba = FLOAT_VAR_MIN_MIN(); break;
00955 case 14: fvba = FLOAT_VAR_MIN_MAX(); break;
00956 case 15: fvba = FLOAT_VAR_MAX_MIN(); break;
00957 case 16: fvba = FLOAT_VAR_MAX_MAX(); break;
00958 case 17: fvba = FLOAT_VAR_SIZE_MIN(); break;
00959 case 18: fvba = FLOAT_VAR_SIZE_MAX(); break;
00960 case 19: fvba = FLOAT_VAR_DEGREE_SIZE_MIN(); break;
00961 case 20: fvba = FLOAT_VAR_DEGREE_SIZE_MAX(); break;
00962 case 21: fvba = FLOAT_VAR_AFC_SIZE_MIN(); break;
00963 case 22: fvba = FLOAT_VAR_AFC_SIZE_MAX(); break;
00964 case 23: fvba = FLOAT_VAR_ACTION_SIZE_MIN(faa); break;
00965 case 24: fvba = FLOAT_VAR_ACTION_SIZE_MAX(faa); break;
00966 case 25: fvba = FLOAT_VAR_CHB_SIZE_MIN(fca); break;
00967 case 26: fvba = FLOAT_VAR_CHB_SIZE_MAX(fca); break;
00968 }
00969
00970 Rnd rb(2);
00971 FloatVarBranch fvbb;
00972 FloatAction fab(*c, c->x, 0.9, &float_merit);
00973 FloatCHB fcb(*c, c->x, &float_merit);
00974 switch (varb) {
00975 case 0: break;
00976 case 1: fvbb = FLOAT_VAR_NONE(); break;
00977 case 2: fvbb = FLOAT_VAR_RND(rb); break;
00978 case 3: fvbb = FLOAT_VAR_MERIT_MIN(&float_merit,&tbl); break;
00979 case 4: fvbb = FLOAT_VAR_MERIT_MAX(&float_merit,&tbl); break;
00980 case 5: fvbb = FLOAT_VAR_DEGREE_MIN(&tbl); break;
00981 case 6: fvbb = FLOAT_VAR_DEGREE_MAX(&tbl); break;
00982 case 7: fvbb = FLOAT_VAR_AFC_MIN(0.5,&tbl); break;
00983 case 8: fvbb = FLOAT_VAR_AFC_MAX(0.5,&tbl); break;
00984 case 9: fvbb = FLOAT_VAR_ACTION_MIN(fab,&tbl); break;
00985 case 10: fvbb = FLOAT_VAR_ACTION_MAX(fab,&tbl); break;
00986 case 11: fvbb = FLOAT_VAR_CHB_MIN(fcb,&tbl); break;
00987 case 12: fvbb = FLOAT_VAR_CHB_MAX(fcb,&tbl); break;
00988 case 13: fvbb = FLOAT_VAR_MIN_MIN(&tbl); break;
00989 case 14: fvbb = FLOAT_VAR_MIN_MAX(&tbl); break;
00990 case 15: fvbb = FLOAT_VAR_MAX_MIN(&tbl); break;
00991 case 16: fvbb = FLOAT_VAR_MAX_MAX(&tbl); break;
00992 case 17: fvbb = FLOAT_VAR_SIZE_MIN(&tbl); break;
00993 case 18: fvbb = FLOAT_VAR_SIZE_MAX(&tbl); break;
00994 case 19: fvbb = FLOAT_VAR_DEGREE_SIZE_MIN(&tbl); break;
00995 case 20: fvbb = FLOAT_VAR_DEGREE_SIZE_MAX(&tbl); break;
00996 case 21: fvbb = FLOAT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
00997 case 22: fvbb = FLOAT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
00998 case 23: fvbb = FLOAT_VAR_ACTION_SIZE_MIN(fab,&tbl); break;
00999 case 24: fvbb = FLOAT_VAR_ACTION_SIZE_MAX(fab,&tbl); break;
01000 case 25: fvbb = FLOAT_VAR_CHB_SIZE_MIN(fcb,&tbl); break;
01001 case 26: fvbb = FLOAT_VAR_CHB_SIZE_MAX(fcb,&tbl); break;
01002 }
01003
01004 switch (Base::rand(9U)) {
01005 case 0U:
01006 branch(*c, c->x, fvba, fvb); break;
01007 case 1U:
01008 branch(*c, c->x, fvbb, fvb); break;
01009 case 2U:
01010 branch(*c, c->x, tiebreak(fvba,fvbb), fvb); break;
01011 case 3U:
01012 branch(*c, c->x, tiebreak(fvbb,fvba), fvb); break;
01013 case 4U:
01014 branch(*c, c->x, tiebreak(fvba,fvba,fvbb), fvb); break;
01015 case 5U:
01016 branch(*c, c->x, tiebreak(fvba,fvbb,fvbb), fvb); break;
01017 case 6U:
01018 branch(*c, c->x, tiebreak(fvbb,fvba,fvba), fvb); break;
01019 case 7U:
01020 branch(*c, c->x, tiebreak(fvba,fvba,fvbb,fvba), fvb); break;
01021 case 8U:
01022 branch(*c, c->x, tiebreak(fvbb,fvba,fvbb,fvba), fvb); break;
01023 }
01024
01025 }
01026 Gecode::Search::Options o;
01027 results[solutions(c,o,nbSols)].push_back
01028 (RunInfo(float_var_branch_name[vara],
01029 float_var_branch_name[varb],
01030 float_val_branch_name[val],
01031 o));
01032 }
01033 }
01034 }
01035 if (results.size() > 1)
01036 goto failed;
01037 delete root;
01038 return true;
01039 failed:
01040 std::cout << "FAILURE" << std::endl;
01041 for (map<int, vector<RunInfo> >::iterator it = results.begin();
01042 it != results.end(); ++it) {
01043 std::cout << "Number of solutions: " << it->first << std::endl;
01044 for (unsigned int i = 0; i < it->second.size(); ++i)
01045 std::cout << it->second[i] << " ";
01046 std::cout << std::endl;
01047 }
01048
01049 delete root;
01050 return results.size() == 1;
01051 }
01052 #endif
01053
01054 }}
01055
01056