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