Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
branch.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  *
7  * Contributing authors:
8  * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
9  *
10  * Copyright:
11  * Mikael Lagerkvist, 2005
12  * Christian Schulte, 2009
13  * Vincent Barichard, 2012
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include "test/branch.hh"
41 
42 #include <algorithm>
43 #include <map>
44 #include <vector>
45 #include <iostream>
46 
47 #include <gecode/kernel.hh>
48 #include <gecode/int.hh>
49 #ifdef GECODE_HAS_SET_VARS
50 #include <gecode/set.hh>
51 #endif
52 #ifdef GECODE_HAS_FLOAT_VARS
53 #include <gecode/float.hh>
54 #endif
55 
56 #include <gecode/search.hh>
57 
58 namespace Test { namespace Branch {
59 
61  double tbl(const Gecode::Space&, double w, double b) {
62  return (w + (b-w)/2.0);
63  }
64 
66  class IntTestSpace : public Gecode::Space {
67  public:
76  : x(*this, n, d),
77  vara(Gecode::INT_VAR_NONE()), varb(Gecode::INT_VAR_NONE()),
78  val(Gecode::INT_VAL_MIN()) {}
81  : Gecode::Space(s), vara(s.vara), varb(s.varb), val(s.val) {
82  x.update(*this, s.x);
83  }
85  virtual Gecode::Space* copy(void) {
86  return new IntTestSpace(*this);
87  }
88  };
89 
91  class BoolTestSpace : public Gecode::Space {
92  public:
97  : x(*this, n, 0, 1) {}
100  : Gecode::Space(s) {
101  x.update(*this, s.x);
102  }
104  virtual Gecode::Space* copy(void) {
105  return new BoolTestSpace(*this);
106  }
107  };
108 
109 #ifdef GECODE_HAS_SET_VARS
111  class SetTestSpace : public Gecode::Space {
112  public:
117  : x(*this, n, Gecode::IntSet::empty, d) {}
120  : Gecode::Space(s) {
121  x.update(*this, s.x);
122  }
124  virtual Gecode::Space* copy(void) {
125  return new SetTestSpace(*this);
126  }
127  };
128 #endif
129 
130 #ifdef GECODE_HAS_FLOAT_VARS
132  class FloatTestSpace : public Gecode::Space {
133  public:
138  : x(*this, n, d.min(), d.max()) {}
141  : Gecode::Space(s) {
142  x.update(*this, s.x);
143  }
145  virtual Gecode::Space* copy(void) {
146  return new FloatTestSpace(*this);
147  }
148  };
149 #endif
150 
157  const char* int_var_branch_name[] = {
158  "SINGLE VARIABLE",
159  "INT_VAR_NONE",
160  "INT_VAR_RND",
161  "INT_VAR_MERIT_MIN",
162  "INT_VAR_MERIT_MAX",
163  "INT_VAR_DEGREE_MIN",
164  "INT_VAR_DEGREE_MAX",
165  "INT_VAR_AFC_MIN",
166  "INT_VAR_AFC_MAX",
167  "INT_VAR_ACTION_MIN",
168  "INT_VAR_ACTION_MAX",
169  "INT_VAR_CHB_MIN",
170  "INT_VAR_CHB_MAX",
171  "INT_VAR_MIN_MIN",
172  "INT_VAR_MIN_MAX",
173  "INT_VAR_MAX_MIN",
174  "INT_VAR_MAX_MAX",
175  "INT_VAR_SIZE_MIN",
176  "INT_VAR_SIZE_MAX",
177  "INT_VAR_DEGREE_SIZE_MIN",
178  "INT_VAR_DEGREE_SIZE_MAX",
179  "INT_VAR_AFC_SIZE_MIN",
180  "INT_VAR_AFC_SIZE_MAX",
181  "INT_VAR_ACTION_SIZE_MIN",
182  "INT_VAR_ACTION_SIZE_MAX",
183  "INT_VAR_CHB_SIZE_MIN",
184  "INT_VAR_CHB_SIZE_MAX",
185  "INT_VAR_REGRET_MIN_MIN",
186  "INT_VAR_REGRET_MIN_MAX",
187  "INT_VAR_REGRET_MAX_MIN",
188  "INT_VAR_REGRET_MAX_MAX"
189  };
191  const int n_int_var_branch =
192  sizeof(int_var_branch_name)/sizeof(const char*);
194  const char* bool_var_branch_name[] = {
195  "SINGLE VARIABLE",
196  "BOOL_VAR_NONE",
197  "BOOL_VAR_RND",
198  "BOOL_VAR_MERIT_MIN",
199  "BOOL_VAR_MERIT_MAX",
200  "BOOL_VAR_DEGREE_MIN",
201  "BOOL_VAR_DEGREE_MAX",
202  "BOOL_VAR_AFC_MIN",
203  "BOOL_VAR_AFC_MAX",
204  "BOOL_VAR_ACTION_MIN",
205  "BOOL_VAR_ACTION_MAX",
206  "BOOL_VAR_CHB_MIN",
207  "BOOL_VAR_CHB_MAX"
208  };
210  const int n_bool_var_branch =
211  sizeof(bool_var_branch_name)/sizeof(const char*);
213  double int_merit(const Gecode::Space&, Gecode::IntVar x, int) {
214  return x.min();
215  }
217  double bool_merit(const Gecode::Space&, Gecode::BoolVar x, int) {
218  return x.min();
219  }
221  const char* int_val_branch_name[] = {
222  "INT_VAL_MIN",
223  "INT_VAL_MED",
224  "INT_VAL_MAX",
225  "INT_VAL_RND",
226  "INT_VAL_SPLIT_MIN",
227  "INT_VAL_SPLIT_MAX",
228  "INT_VAL_RANGE_MIN",
229  "INT_VAL_RANGE_MAX",
230  "INT_VAL",
231  "INT_VALUES_MIN",
232  "INT_VALUES_MAX"
233  };
235  const int n_int_val_branch =
236  sizeof(int_val_branch_name)/sizeof(const char*);
238  const char* bool_val_branch_name[] = {
239  "BOOL_VAL_MIN",
240  "BOOL_VAL_MAX",
241  "BOOL_VAL_RND",
242  "BOOL_VAL"
243  };
245  const int n_bool_val_branch =
246  sizeof(bool_val_branch_name)/sizeof(const char*);
248  int int_val(const Gecode::Space&, Gecode::IntVar x, int) {
249  return x.min();
250  }
253  return x.min();
254  }
256 
257 #ifdef GECODE_HAS_SET_VARS
264  const char* set_var_branch_name[] = {
265  "SINGLE VARIABLE",
266  "SET_VAR_NONE",
267  "SET_VAR_RND",
268  "SET_VAR_MERIT_MIN",
269  "SET_VAR_MERIT_MAX",
270  "SET_VAR_DEGREE_MIN",
271  "SET_VAR_DEGREE_MAX",
272  "SET_VAR_AFC_MIN",
273  "SET_VAR_AFC_MAX",
274  "SET_VAR_ACTION_MIN",
275  "SET_VAR_ACTION_MAX",
276  "SET_VAR_CHB_MIN",
277  "SET_VAR_CHB_MAX",
278  "SET_VAR_MIN_MIN",
279  "SET_VAR_MIN_MAX",
280  "SET_VAR_MAX_MIN",
281  "SET_VAR_MAX_MAX",
282  "SET_VAR_SIZE_MIN",
283  "SET_VAR_SIZE_MAX",
284  "SET_VAR_DEGREE_SIZE_MIN",
285  "SET_VAR_DEGREE_SIZE_MAX",
286  "SET_VAR_AFC_SIZE_MIN",
287  "SET_VAR_AFC_SIZE_MAX",
288  "SET_VAR_ACTION_SIZE_MIN",
289  "SET_VAR_ACTION_SIZE_MAX",
290  "SET_VAR_CHB_SIZE_MIN",
291  "SET_VAR_CHB_SIZE_MAX"
292  };
294  const int n_set_var_branch =
295  sizeof(set_var_branch_name)/sizeof(const char*);
297  double set_merit(const Gecode::Space&, Gecode::SetVar, int) {
298  return 2.0;
299  }
301  const char* set_val_branch_name[] = {
302  "SET_VAL_MIN_INC",
303  "SET_VAL_MIN_EXC",
304  "SET_VAL_MED_INC",
305  "SET_VAL_MED_EXC",
306  "SET_VAL_MAX_INC",
307  "SET_VAL_MAX_EXC",
308  "SET_VAL_RND_INC",
309  "SET_VAL_RND_EXC",
310  "SET_VAL"
311  };
313  const int n_set_val_branch =
314  sizeof(set_val_branch_name)/sizeof(const char*);
316  int set_val(const Gecode::Space&, Gecode::SetVar x, int) {
318  return r.min();
319  }
321 #endif
322 
323 #ifdef GECODE_HAS_FLOAT_VARS
330  const char* float_var_branch_name[] = {
331  "SINGLE VARIABLE",
332  "FLOAT_VAR_NONE",
333  "FLOAT_VAR_RND",
334  "FLOAT_VAR_MERIT_MIN",
335  "FLOAT_VAR_MERIT_MAX",
336  "FLOAT_VAR_DEGREE_MIN",
337  "FLOAT_VAR_DEGREE_MAX",
338  "FLOAT_VAR_AFC_MIN",
339  "FLOAT_VAR_AFC_MAX",
340  "FLOAT_VAR_ACTION_MIN",
341  "FLOAT_VAR_ACTION_MAX",
342  "FLOAT_VAR_CHB_MIN",
343  "FLOAT_VAR_CHB_MAX",
344  "FLOAT_VAR_MIN_MIN",
345  "FLOAT_VAR_MIN_MAX",
346  "FLOAT_VAR_MAX_MIN",
347  "FLOAT_VAR_MAX_MAX",
348  "FLOAT_VAR_SIZE_MIN",
349  "FLOAT_VAR_SIZE_MAX",
350  "FLOAT_VAR_DEGREE_SIZE_MIN",
351  "FLOAT_VAR_DEGREE_SIZE_MAX",
352  "FLOAT_VAR_AFC_SIZE_MIN",
353  "FLOAT_VAR_AFC_SIZE_MAX",
354  "FLOAT_VAR_ACTION_SIZE_MIN",
355  "FLOAT_VAR_ACTION_SIZE_MAX",
356  "FLOAT_VAR_CHB_SIZE_MIN",
357  "FLOAT_VAR_CHB_SIZE_MAX"
358  };
360  const int n_float_var_branch =
361  sizeof(float_var_branch_name)/sizeof(const char*);
364  return static_cast<double>(x.degree());
365  }
367  const char* float_val_branch_name[] = {
368  "FLOAT_VAL_SPLIT_MIN",
369  "FLOAT_VAL_SPLIT_MAX",
370  "FLOAT_VAL_SPLIT_RND",
371  "FLOAT_VAL"
372  };
374  const int n_float_val_branch =
375  sizeof(float_val_branch_name)/sizeof(const char*);
378  Gecode::FloatVar x, int) {
379  Gecode::FloatNumBranch nl; nl.n=x.med(); nl.l=true;
380  return nl;
381  }
383 #endif
384 
386  class RunInfo {
387  public:
388  std::string var, val;
389  unsigned int a_d, c_d;
390  RunInfo(const std::string& vara, const std::string& varb,
391  const std::string& valname,
392  const Gecode::Search::Options& o)
393  : var(vara + "::" + varb), val(valname), a_d(o.a_d), c_d(o.c_d) {}
394  void print(std::ostream& o) const {
395  o << "(" << var << ", " << val << ", " << a_d << ", " << c_d << ")";
396  }
397  };
398 
399 }}
400 
401 std::ostream&
402 operator<<(std::ostream& os, const Test::Branch::RunInfo& ri) {
403  ri.print(os);
404  return os;
405 }
406 
407 
408 namespace Test { namespace Branch {
409 
411  template<class TestSpace>
412  int solutions(TestSpace* c, Gecode::Search::Options& o, int maxNbSol = -1) {
413  o.a_d = Base::rand(10);
414  o.c_d = Base::rand(10);
415  Gecode::DFS<TestSpace> e_s(c, o);
416  delete c;
417 
418  // Find number of solutions
419  int s = 0;
420  do {
421  Gecode::Space* ex = e_s.next();
422  if (ex == NULL) break;
423  delete ex;
424  ++s;
425  if ((maxNbSol >= 0) && (maxNbSol == s)) break;
426  } while (true);
427  return s;
428  }
429 
430  IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
431  : Base("Int::Branch::"+s), arity(a), dom(d) {
432  }
433 
434  bool
435  IntTest::run(void) {
436  using std::map;
437  using std::vector;
438  using std::string;
439  using std::ostream;
440  using namespace Gecode;
441 
442  // Results of tests run
443  map<int, vector<RunInfo> > results;
444  // Set up root space
445  IntTestSpace* root = new IntTestSpace(arity,dom);
446  post(*root, root->x);
447  results.clear();
448 
449  IntArgs d(arity);
450  for (int i=arity; i--; )
451  d[i]=i;
452 
453  for (int vara = 0; vara<n_int_var_branch; vara++) {
454  for (int varb = 1; varb<n_int_var_branch; varb++) {
455  for (int val = 0; val<n_int_val_branch; val++) {
456  Rnd r(1);
457 
458  IntValBranch ivb;
459  switch (val) {
460  case 0: ivb = INT_VAL_MIN(); break;
461  case 1: ivb = INT_VAL_MED(); break;
462  case 2: ivb = INT_VAL_MAX(); break;
463  case 3: ivb = INT_VAL_RND(r); break;
464  case 4: ivb = INT_VAL_SPLIT_MIN(); break;
465  case 5: ivb = INT_VAL_SPLIT_MAX(); break;
466  case 6: ivb = INT_VAL_RANGE_MIN(); break;
467  case 7: ivb = INT_VAL_RANGE_MAX(); break;
468  case 8: ivb = INT_VAL(&int_val); break;
469  case 9: ivb = INT_VALUES_MIN(); break;
470  case 10: ivb = INT_VALUES_MAX(); break;
471  }
472 
473  IntTestSpace* c = static_cast<IntTestSpace*>(root->clone());
474 
475  if ((vara == 0) && (val < 11)) {
476  for (int i=0; i<c->x.size(); i++)
477  branch(*c, c->x[i], ivb);
478  } else {
479  Rnd ra(1);
480  IntVarBranch ivba;
481  IntAction iaa(*c, c->x, 0.9);
482  IntCHB ica(*c, c->x);
483  switch (vara) {
484  case 0: ivba = INT_VAR_NONE(); break;
485  case 1: ivba = INT_VAR_NONE(); break;
486  case 2: ivba = INT_VAR_RND(ra); break;
487  case 3: ivba = INT_VAR_MERIT_MIN(&int_merit); break;
488  case 4: ivba = INT_VAR_MERIT_MAX(&int_merit); break;
489  case 5: ivba = INT_VAR_DEGREE_MIN(); break;
490  case 6: ivba = INT_VAR_DEGREE_MAX(); break;
491  case 7: ivba = INT_VAR_AFC_MIN(0.5); break;
492  case 8: ivba = INT_VAR_AFC_MAX(0.5); break;
493  case 9: ivba = INT_VAR_ACTION_MIN(iaa); break;
494  case 10: ivba = INT_VAR_ACTION_MAX(iaa); break;
495  case 11: ivba = INT_VAR_CHB_MIN(ica); break;
496  case 12: ivba = INT_VAR_CHB_MAX(ica); break;
497  case 13: ivba = INT_VAR_MIN_MIN(); break;
498  case 14: ivba = INT_VAR_MIN_MAX(); break;
499  case 15: ivba = INT_VAR_MAX_MIN(); break;
500  case 16: ivba = INT_VAR_MAX_MAX(); break;
501  case 17: ivba = INT_VAR_SIZE_MIN(); break;
502  case 18: ivba = INT_VAR_SIZE_MAX(); break;
503  case 19: ivba = INT_VAR_DEGREE_SIZE_MIN(); break;
504  case 20: ivba = INT_VAR_DEGREE_SIZE_MAX(); break;
505  case 21: ivba = INT_VAR_AFC_SIZE_MIN(); break;
506  case 22: ivba = INT_VAR_AFC_SIZE_MAX(); break;
507  case 23: ivba = INT_VAR_ACTION_SIZE_MIN(iaa); break;
508  case 24: ivba = INT_VAR_ACTION_SIZE_MAX(iaa); break;
509  case 25: ivba = INT_VAR_CHB_SIZE_MIN(ica); break;
510  case 26: ivba = INT_VAR_CHB_SIZE_MAX(ica); break;
511  case 27: ivba = INT_VAR_REGRET_MIN_MIN(); break;
512  case 28: ivba = INT_VAR_REGRET_MIN_MAX(); break;
513  case 29: ivba = INT_VAR_REGRET_MAX_MIN(); break;
514  case 30: ivba = INT_VAR_REGRET_MAX_MAX(); break;
515  }
516 
517  Rnd rb(2);
518  IntVarBranch ivbb;
519  IntAction iab(*c, c->x, 0.9, &int_merit);
520  IntCHB icb(*c, c->x, &int_merit);
521  switch (varb) {
522  case 0: ivbb = INT_VAR_NONE(); break;
523  case 1: ivbb = INT_VAR_NONE(); break;
524  case 2: ivbb = INT_VAR_RND(rb); break;
525  case 3: ivbb = INT_VAR_MERIT_MIN(&int_merit,&tbl); break;
526  case 4: ivbb = INT_VAR_MERIT_MAX(&int_merit,&tbl); break;
527  case 5: ivbb = INT_VAR_DEGREE_MIN(&tbl); break;
528  case 6: ivbb = INT_VAR_DEGREE_MAX(&tbl); break;
529  case 7: ivbb = INT_VAR_AFC_MIN(0.5,&tbl); break;
530  case 8: ivbb = INT_VAR_AFC_MAX(0.5,&tbl); break;
531  case 9: ivbb = INT_VAR_ACTION_MIN(iab,&tbl); break;
532  case 10: ivbb = INT_VAR_ACTION_MAX(iab,&tbl); break;
533  case 11: ivbb = INT_VAR_CHB_MIN(icb,&tbl); break;
534  case 12: ivbb = INT_VAR_CHB_MAX(icb,&tbl); break;
535  case 13: ivbb = INT_VAR_MIN_MIN(&tbl); break;
536  case 14: ivbb = INT_VAR_MIN_MAX(&tbl); break;
537  case 15: ivbb = INT_VAR_MAX_MIN(&tbl); break;
538  case 16: ivbb = INT_VAR_MAX_MAX(&tbl); break;
539  case 17: ivbb = INT_VAR_SIZE_MIN(&tbl); break;
540  case 18: ivbb = INT_VAR_SIZE_MAX(&tbl); break;
541  case 19: ivbb = INT_VAR_DEGREE_SIZE_MIN(&tbl); break;
542  case 20: ivbb = INT_VAR_DEGREE_SIZE_MAX(&tbl); break;
543  case 21: ivbb = INT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
544  case 22: ivbb = INT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
545  case 23: ivbb = INT_VAR_ACTION_SIZE_MIN(iab,&tbl); break;
546  case 24: ivbb = INT_VAR_ACTION_SIZE_MAX(iab,&tbl); break;
547  case 25: ivbb = INT_VAR_CHB_SIZE_MIN(icb,&tbl); break;
548  case 26: ivbb = INT_VAR_CHB_SIZE_MAX(icb,&tbl); break;
549  case 27: ivbb = INT_VAR_REGRET_MIN_MIN(&tbl); break;
550  case 28: ivbb = INT_VAR_REGRET_MIN_MAX(&tbl); break;
551  case 29: ivbb = INT_VAR_REGRET_MAX_MIN(&tbl); break;
552  case 30: ivbb = INT_VAR_REGRET_MAX_MAX(&tbl); break;
553  }
554 
555  switch (Base::rand(9U)) {
556  case 0U:
557  branch(*c, c->x, ivba, ivb); break;
558  case 1U:
559  branch(*c, c->x, ivbb, ivb); break;
560  case 2U:
561  branch(*c, c->x, tiebreak(ivba,ivbb), ivb); break;
562  case 3U:
563  branch(*c, c->x, tiebreak(ivbb,ivba), ivb); break;
564  case 4U:
565  branch(*c, c->x, tiebreak(ivba,ivba,ivbb), ivb); break;
566  case 5U:
567  branch(*c, c->x, tiebreak(ivba,ivbb,ivbb), ivb); break;
568  case 6U:
569  branch(*c, c->x, tiebreak(ivbb,ivba,ivba), ivb); break;
570  case 7U:
571  branch(*c, c->x, tiebreak(ivba,ivba,ivbb,ivba), ivb); break;
572  case 8U:
573  branch(*c, c->x, tiebreak(ivbb,ivba,ivbb,ivba), ivb); break;
574  }
575 
576  }
578  results[solutions(c,o)].push_back
579  (RunInfo(int_var_branch_name[vara],
580  int_var_branch_name[varb],
581  int_val_branch_name[val],
582  o));
583  }
584  }
585  }
586  if (results.size() > 1)
587  goto failed;
588  delete root;
589  return true;
590  failed:
591  std::cout << "FAILURE" << std::endl;
592  for (map<int, vector<RunInfo> >::iterator it = results.begin();
593  it != results.end(); ++it) {
594  std::cout << "Number of solutions: " << it->first << std::endl;
595  for (unsigned int i = 0; i < it->second.size(); ++i)
596  std::cout << it->second[i] << " ";
597  std::cout << std::endl;
598  }
599 
600  delete root;
601  return results.size() == 1;
602  }
603 
604  BoolTest::BoolTest(const std::string& s, int a)
605  : Base("Bool::Branch::"+s), arity(a) {
606  }
607 
608  bool
610  using std::map;
611  using std::vector;
612  using std::string;
613  using std::ostream;
614  using namespace Gecode;
615 
616  // Results of tests run
617  map<int, vector<RunInfo> > results;
618  // Set up root space
619  BoolTestSpace* root = new BoolTestSpace(arity);
620  post(*root, root->x);
621  results.clear();
622 
623  for (int vara = 0; vara<n_bool_var_branch; vara++) {
624  for (int varb = 1; varb<n_bool_var_branch; varb++) {
625  for (int val = 0; val<n_bool_val_branch; val++) {
626 
627  Rnd r(1);
628 
629  BoolValBranch bvb;
630  switch (val) {
631  case 0: bvb = BOOL_VAL_MIN(); break;
632  case 1: bvb = BOOL_VAL_MAX(); break;
633  case 2: bvb = BOOL_VAL_RND(r); break;
634  case 3: bvb = BOOL_VAL(&bool_val); break;
635  }
636 
637  BoolTestSpace* c = static_cast<BoolTestSpace*>(root->clone());
638 
639  if (vara == 0) {
640  for (int i=0; i<c->x.size(); i++)
641  branch(*c, c->x[i], bvb);
642  } else {
643 
644 
645  Rnd ra(1);
646  BoolVarBranch bvba;
647  BoolAction baa(*c, c->x, 0.9);
648  BoolCHB bca(*c, c->x);
649  switch (vara) {
650  case 0: bvba = BOOL_VAR_NONE(); break;
651  case 1: bvba = BOOL_VAR_NONE(); break;
652  case 2: bvba = BOOL_VAR_RND(ra); break;
653  case 3: bvba = BOOL_VAR_MERIT_MIN(&bool_merit); break;
654  case 4: bvba = BOOL_VAR_MERIT_MAX(&bool_merit); break;
655  case 5: bvba = BOOL_VAR_DEGREE_MIN(); break;
656  case 6: bvba = BOOL_VAR_DEGREE_MAX(); break;
657  case 7: bvba = BOOL_VAR_AFC_MIN(0.5); break;
658  case 8: bvba = BOOL_VAR_AFC_MAX(0.5); break;
659  case 9: bvba = BOOL_VAR_ACTION_MIN(baa); break;
660  case 10: bvba = BOOL_VAR_ACTION_MAX(baa); break;
661  case 11: bvba = BOOL_VAR_CHB_MIN(bca); break;
662  case 12: bvba = BOOL_VAR_CHB_MAX(bca); break;
663  }
664 
665  Rnd rb(2);
666  BoolVarBranch bvbb;
667  BoolAction bab(*c, c->x, 0.9, &bool_merit);
668  BoolCHB bcb(*c, c->x, &bool_merit);
669  switch (varb) {
670  case 0: bvbb = BOOL_VAR_NONE(); break;
671  case 1: bvbb = BOOL_VAR_NONE(); break;
672  case 2: bvbb = BOOL_VAR_RND(rb); break;
673  case 3: bvbb = BOOL_VAR_MERIT_MIN(&bool_merit,&tbl); break;
674  case 4: bvbb = BOOL_VAR_MERIT_MAX(&bool_merit,&tbl); break;
675  case 5: bvbb = BOOL_VAR_DEGREE_MIN(&tbl); break;
676  case 6: bvbb = BOOL_VAR_DEGREE_MAX(&tbl); break;
677  case 7: bvbb = BOOL_VAR_AFC_MIN(0.5,&tbl); break;
678  case 8: bvbb = BOOL_VAR_AFC_MAX(0.5,&tbl); break;
679  case 9: bvbb = BOOL_VAR_ACTION_MIN(bab,&tbl); break;
680  case 10: bvbb = BOOL_VAR_ACTION_MAX(bab,&tbl); break;
681  case 11: bvbb = BOOL_VAR_CHB_MIN(bcb,&tbl); break;
682  case 12: bvbb = BOOL_VAR_CHB_MAX(bcb,&tbl); break;
683  }
684 
685  switch (Base::rand(9U)) {
686  case 0U:
687  branch(*c, c->x, bvba, bvb); break;
688  case 1U:
689  branch(*c, c->x, bvbb, bvb); break;
690  case 2U:
691  branch(*c, c->x, tiebreak(bvba,bvbb), bvb); break;
692  case 3U:
693  branch(*c, c->x, tiebreak(bvbb,bvba), bvb); break;
694  case 4U:
695  branch(*c, c->x, tiebreak(bvba,bvba,bvbb), bvb); break;
696  case 5U:
697  branch(*c, c->x, tiebreak(bvba,bvbb,bvbb), bvb); break;
698  case 6U:
699  branch(*c, c->x, tiebreak(bvbb,bvba,bvba), bvb); break;
700  case 7U:
701  branch(*c, c->x, tiebreak(bvba,bvba,bvbb,bvba), bvb); break;
702  case 8U:
703  branch(*c, c->x, tiebreak(bvbb,bvba,bvbb,bvba), bvb); break;
704  }
705 
706  }
708  results[solutions(c,o)].push_back
709  (RunInfo(int_var_branch_name[vara],
710  int_var_branch_name[varb],
711  int_val_branch_name[val],
712  o));
713  }
714  }
715  }
716  if (results.size() > 1)
717  goto failed;
718  delete root;
719  return true;
720  failed:
721  std::cout << "FAILURE" << std::endl;
722  for (map<int, vector<RunInfo> >::iterator it = results.begin();
723  it != results.end(); ++it) {
724  std::cout << "Number of solutions: " << it->first << std::endl;
725  for (unsigned int i = 0; i < it->second.size(); ++i)
726  std::cout << it->second[i] << " ";
727  std::cout << std::endl;
728  }
729 
730  delete root;
731  return results.size() == 1;
732  }
733 
734 #ifdef GECODE_HAS_SET_VARS
735  SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
736  : Base("Set::Branch::"+s), arity(a), dom(d) {
737  }
738 
739  bool
740  SetTest::run(void) {
741  using std::map;
742  using std::vector;
743  using std::string;
744  using std::ostream;
745  using namespace Gecode;
746 
747  // Results of tests run
748  map<int, vector<RunInfo> > results;
749  // Set up root space
750  SetTestSpace* root = new SetTestSpace(arity,dom);
751  post(*root, root->x);
752  root->status();
753  results.clear();
754 
755  for (int vara = 0; vara<n_set_var_branch; vara++) {
756  for (int varb = 1; varb<n_set_var_branch; varb++) {
757  for (int val = 0; val<n_set_val_branch; val++) {
758  Rnd r(1);
759 
760  SetValBranch svb;
761  switch (val) {
762  case 0: svb = SET_VAL_MIN_INC(); break;
763  case 1: svb = SET_VAL_MIN_EXC(); break;
764  case 2: svb = SET_VAL_MED_INC(); break;
765  case 3: svb = SET_VAL_MED_EXC(); break;
766  case 4: svb = SET_VAL_MAX_INC(); break;
767  case 5: svb = SET_VAL_MAX_EXC(); break;
768  case 6: svb = SET_VAL_RND_INC(r); break;
769  case 7: svb = SET_VAL_RND_EXC(r); break;
770  case 8: svb = SET_VAL(&set_val); break;
771  }
772 
773  SetTestSpace* c = static_cast<SetTestSpace*>(root->clone());
774 
775  if (vara == 0) {
776  for (int i=0; i<c->x.size(); i++)
777  branch(*c, c->x[i], svb);
778  } else {
779  Rnd ra(1);
780  SetVarBranch svba;
781  SetAction saa(*c, c->x, 0.9);
782  SetCHB sca(*c, c->x);
783  switch (vara) {
784  case 0: break;
785  case 1: svba = SET_VAR_NONE(); break;
786  case 2: svba = SET_VAR_RND(ra); break;
787  case 3: svba = SET_VAR_MERIT_MIN(&set_merit); break;
788  case 4: svba = SET_VAR_MERIT_MAX(&set_merit); break;
789  case 5: svba = SET_VAR_DEGREE_MIN(); break;
790  case 6: svba = SET_VAR_DEGREE_MAX(); break;
791  case 7: svba = SET_VAR_AFC_MIN(0.5); break;
792  case 8: svba = SET_VAR_AFC_MAX(0.5); break;
793  case 9: svba = SET_VAR_ACTION_MIN(saa); break;
794  case 10: svba = SET_VAR_ACTION_MAX(saa); break;
795  case 11: svba = SET_VAR_CHB_MIN(sca); break;
796  case 12: svba = SET_VAR_CHB_MAX(sca); break;
797  case 13: svba = SET_VAR_MIN_MIN(); break;
798  case 14: svba = SET_VAR_MIN_MAX(); break;
799  case 15: svba = SET_VAR_MAX_MIN(); break;
800  case 16: svba = SET_VAR_MAX_MAX(); break;
801  case 17: svba = SET_VAR_SIZE_MIN(); break;
802  case 18: svba = SET_VAR_SIZE_MAX(); break;
803  case 19: svba = SET_VAR_DEGREE_SIZE_MIN(); break;
804  case 20: svba = SET_VAR_DEGREE_SIZE_MAX(); break;
805  case 21: svba = SET_VAR_AFC_SIZE_MIN(); break;
806  case 22: svba = SET_VAR_AFC_SIZE_MAX(); break;
807  case 23: svba = SET_VAR_ACTION_SIZE_MIN(saa); break;
808  case 24: svba = SET_VAR_ACTION_SIZE_MAX(saa); break;
809  case 25: svba = SET_VAR_CHB_SIZE_MIN(sca); break;
810  case 26: svba = SET_VAR_CHB_SIZE_MAX(sca); break;
811  }
812 
813  Rnd rb(2);
814  SetVarBranch svbb;
815  SetAction sab(*c, c->x, 0.9, &set_merit);
816  SetCHB scb(*c, c->x, &set_merit);
817  switch (varb) {
818  case 0: break;
819  case 1: svbb = SET_VAR_NONE(); break;
820  case 2: svbb = SET_VAR_RND(rb); break;
821  case 3: svbb = SET_VAR_MERIT_MIN(&set_merit,&tbl); break;
822  case 4: svbb = SET_VAR_MERIT_MAX(&set_merit,&tbl); break;
823  case 5: svbb = SET_VAR_DEGREE_MIN(&tbl); break;
824  case 6: svbb = SET_VAR_DEGREE_MAX(&tbl); break;
825  case 7: svbb = SET_VAR_AFC_MIN(0.5,&tbl); break;
826  case 8: svbb = SET_VAR_AFC_MAX(0.5,&tbl); break;
827  case 9: svbb = SET_VAR_ACTION_MIN(sab,&tbl); break;
828  case 10: svbb = SET_VAR_ACTION_MAX(sab,&tbl); break;
829  case 11: svbb = SET_VAR_CHB_MIN(scb,&tbl); break;
830  case 12: svbb = SET_VAR_CHB_MAX(scb,&tbl); break;
831  case 13: svbb = SET_VAR_MIN_MIN(&tbl); break;
832  case 14: svbb = SET_VAR_MIN_MAX(&tbl); break;
833  case 15: svbb = SET_VAR_MAX_MIN(&tbl); break;
834  case 16: svbb = SET_VAR_MAX_MAX(&tbl); break;
835  case 17: svbb = SET_VAR_SIZE_MIN(&tbl); break;
836  case 18: svbb = SET_VAR_SIZE_MAX(&tbl); break;
837  case 19: svbb = SET_VAR_DEGREE_SIZE_MIN(&tbl); break;
838  case 20: svbb = SET_VAR_DEGREE_SIZE_MAX(&tbl); break;
839  case 21: svbb = SET_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
840  case 22: svbb = SET_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
841  case 23: svbb = SET_VAR_ACTION_SIZE_MIN(sab,&tbl); break;
842  case 24: svbb = SET_VAR_ACTION_SIZE_MAX(sab,&tbl); break;
843  case 25: svbb = SET_VAR_CHB_SIZE_MIN(scb,&tbl); break;
844  case 26: svbb = SET_VAR_CHB_SIZE_MAX(scb,&tbl); break;
845  }
846 
847  switch (Base::rand(9U)) {
848  case 0U:
849  branch(*c, c->x, svba, svb); break;
850  case 1U:
851  branch(*c, c->x, svbb, svb); break;
852  case 2U:
853  branch(*c, c->x, tiebreak(svba,svbb), svb); break;
854  case 3U:
855  branch(*c, c->x, tiebreak(svbb,svba), svb); break;
856  case 4U:
857  branch(*c, c->x, tiebreak(svba,svba,svbb), svb); break;
858  case 5U:
859  branch(*c, c->x, tiebreak(svba,svbb,svbb), svb); break;
860  case 6U:
861  branch(*c, c->x, tiebreak(svbb,svba,svba), svb); break;
862  case 7U:
863  branch(*c, c->x, tiebreak(svba,svba,svbb,svba), svb); break;
864  case 8U:
865  branch(*c, c->x, tiebreak(svbb,svba,svbb,svba), svb); break;
866  }
867 
868  }
870  results[solutions(c,o)].push_back
871  (RunInfo(set_var_branch_name[vara],
872  set_var_branch_name[varb],
873  set_val_branch_name[val],
874  o));
875  }
876  }
877  }
878  if (results.size() > 1)
879  goto failed;
880  delete root;
881  return true;
882  failed:
883  std::cout << "FAILURE" << std::endl;
884  for (map<int, vector<RunInfo> >::iterator it = results.begin();
885  it != results.end(); ++it) {
886  std::cout << "Number of solutions: " << it->first << std::endl;
887  for (unsigned int i = 0; i < it->second.size(); ++i)
888  std::cout << it->second[i] << " ";
889  std::cout << std::endl;
890  }
891 
892  delete root;
893  return results.size() == 1;
894  }
895 #endif
896 
897 #ifdef GECODE_HAS_FLOAT_VARS
898  FloatTest::FloatTest(const std::string& s, int a, const Gecode::FloatVal& d, int nbs)
899  : Base("Float::Branch::"+s), arity(a), dom(d), nbSols(nbs) {
900  }
901 
902  bool
904  using std::map;
905  using std::vector;
906  using std::string;
907  using std::ostream;
908  using namespace Gecode;
909 
910  // Results of tests run
911  map<int, vector<RunInfo> > results;
912  // Set up root space
913  FloatTestSpace* root = new FloatTestSpace(arity,dom);
914  post(*root, root->x);
915  root->status();
916  results.clear();
917 
918  for (int vara = 0; vara<n_float_var_branch; vara++) {
919  for (int varb = 1; varb<n_float_var_branch; varb++) {
920  for (int val = 0; val<n_float_val_branch; val++) {
921  Rnd r(1);
922 
923  FloatValBranch fvb;
924  switch (val) {
925  case 0: fvb = FLOAT_VAL_SPLIT_MIN(); break;
926  case 1: fvb = FLOAT_VAL_SPLIT_MAX(); break;
927  case 2: fvb = FLOAT_VAL_SPLIT_RND(r); break;
928  case 3: fvb = FLOAT_VAL(&float_val); break;
929  }
930 
931  FloatTestSpace* c = static_cast<FloatTestSpace*>(root->clone());
932  if (vara == 0) {
933  for (int i=0; i<c->x.size(); i++)
934  branch(*c, c->x[i], fvb);
935  } else {
936  Rnd ra(1);
937  FloatVarBranch fvba;
938  FloatAction faa(*c, c->x, 0.9);
939  FloatCHB fca(*c, c->x);
940  switch (vara) {
941  case 0: break;
942  case 1: fvba = FLOAT_VAR_NONE(); break;
943  case 2: fvba = FLOAT_VAR_RND(ra); break;
944  case 3: fvba = FLOAT_VAR_MERIT_MIN(&float_merit); break;
945  case 4: fvba = FLOAT_VAR_MERIT_MAX(&float_merit); break;
946  case 5: fvba = FLOAT_VAR_DEGREE_MIN(); break;
947  case 6: fvba = FLOAT_VAR_DEGREE_MAX(); break;
948  case 7: fvba = FLOAT_VAR_AFC_MIN(0.5); break;
949  case 8: fvba = FLOAT_VAR_AFC_MAX(0.5); break;
950  case 9: fvba = FLOAT_VAR_ACTION_MIN(faa); break;
951  case 10: fvba = FLOAT_VAR_ACTION_MAX(faa); break;
952  case 11: fvba = FLOAT_VAR_CHB_MIN(fca); break;
953  case 12: fvba = FLOAT_VAR_CHB_MAX(fca); break;
954  case 13: fvba = FLOAT_VAR_MIN_MIN(); break;
955  case 14: fvba = FLOAT_VAR_MIN_MAX(); break;
956  case 15: fvba = FLOAT_VAR_MAX_MIN(); break;
957  case 16: fvba = FLOAT_VAR_MAX_MAX(); break;
958  case 17: fvba = FLOAT_VAR_SIZE_MIN(); break;
959  case 18: fvba = FLOAT_VAR_SIZE_MAX(); break;
960  case 19: fvba = FLOAT_VAR_DEGREE_SIZE_MIN(); break;
961  case 20: fvba = FLOAT_VAR_DEGREE_SIZE_MAX(); break;
962  case 21: fvba = FLOAT_VAR_AFC_SIZE_MIN(); break;
963  case 22: fvba = FLOAT_VAR_AFC_SIZE_MAX(); break;
964  case 23: fvba = FLOAT_VAR_ACTION_SIZE_MIN(faa); break;
965  case 24: fvba = FLOAT_VAR_ACTION_SIZE_MAX(faa); break;
966  case 25: fvba = FLOAT_VAR_CHB_SIZE_MIN(fca); break;
967  case 26: fvba = FLOAT_VAR_CHB_SIZE_MAX(fca); break;
968  }
969 
970  Rnd rb(2);
971  FloatVarBranch fvbb;
972  FloatAction fab(*c, c->x, 0.9, &float_merit);
973  FloatCHB fcb(*c, c->x, &float_merit);
974  switch (varb) {
975  case 0: break;
976  case 1: fvbb = FLOAT_VAR_NONE(); break;
977  case 2: fvbb = FLOAT_VAR_RND(rb); break;
978  case 3: fvbb = FLOAT_VAR_MERIT_MIN(&float_merit,&tbl); break;
979  case 4: fvbb = FLOAT_VAR_MERIT_MAX(&float_merit,&tbl); break;
980  case 5: fvbb = FLOAT_VAR_DEGREE_MIN(&tbl); break;
981  case 6: fvbb = FLOAT_VAR_DEGREE_MAX(&tbl); break;
982  case 7: fvbb = FLOAT_VAR_AFC_MIN(0.5,&tbl); break;
983  case 8: fvbb = FLOAT_VAR_AFC_MAX(0.5,&tbl); break;
984  case 9: fvbb = FLOAT_VAR_ACTION_MIN(fab,&tbl); break;
985  case 10: fvbb = FLOAT_VAR_ACTION_MAX(fab,&tbl); break;
986  case 11: fvbb = FLOAT_VAR_CHB_MIN(fcb,&tbl); break;
987  case 12: fvbb = FLOAT_VAR_CHB_MAX(fcb,&tbl); break;
988  case 13: fvbb = FLOAT_VAR_MIN_MIN(&tbl); break;
989  case 14: fvbb = FLOAT_VAR_MIN_MAX(&tbl); break;
990  case 15: fvbb = FLOAT_VAR_MAX_MIN(&tbl); break;
991  case 16: fvbb = FLOAT_VAR_MAX_MAX(&tbl); break;
992  case 17: fvbb = FLOAT_VAR_SIZE_MIN(&tbl); break;
993  case 18: fvbb = FLOAT_VAR_SIZE_MAX(&tbl); break;
994  case 19: fvbb = FLOAT_VAR_DEGREE_SIZE_MIN(&tbl); break;
995  case 20: fvbb = FLOAT_VAR_DEGREE_SIZE_MAX(&tbl); break;
996  case 21: fvbb = FLOAT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
997  case 22: fvbb = FLOAT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
998  case 23: fvbb = FLOAT_VAR_ACTION_SIZE_MIN(fab,&tbl); break;
999  case 24: fvbb = FLOAT_VAR_ACTION_SIZE_MAX(fab,&tbl); break;
1000  case 25: fvbb = FLOAT_VAR_CHB_SIZE_MIN(fcb,&tbl); break;
1001  case 26: fvbb = FLOAT_VAR_CHB_SIZE_MAX(fcb,&tbl); break;
1002  }
1003 
1004  switch (Base::rand(9U)) {
1005  case 0U:
1006  branch(*c, c->x, fvba, fvb); break;
1007  case 1U:
1008  branch(*c, c->x, fvbb, fvb); break;
1009  case 2U:
1010  branch(*c, c->x, tiebreak(fvba,fvbb), fvb); break;
1011  case 3U:
1012  branch(*c, c->x, tiebreak(fvbb,fvba), fvb); break;
1013  case 4U:
1014  branch(*c, c->x, tiebreak(fvba,fvba,fvbb), fvb); break;
1015  case 5U:
1016  branch(*c, c->x, tiebreak(fvba,fvbb,fvbb), fvb); break;
1017  case 6U:
1018  branch(*c, c->x, tiebreak(fvbb,fvba,fvba), fvb); break;
1019  case 7U:
1020  branch(*c, c->x, tiebreak(fvba,fvba,fvbb,fvba), fvb); break;
1021  case 8U:
1022  branch(*c, c->x, tiebreak(fvbb,fvba,fvbb,fvba), fvb); break;
1023  }
1024 
1025  }
1027  results[solutions(c,o,nbSols)].push_back
1028  (RunInfo(float_var_branch_name[vara],
1029  float_var_branch_name[varb],
1030  float_val_branch_name[val],
1031  o));
1032  }
1033  }
1034  }
1035  if (results.size() > 1)
1036  goto failed;
1037  delete root;
1038  return true;
1039  failed:
1040  std::cout << "FAILURE" << std::endl;
1041  for (map<int, vector<RunInfo> >::iterator it = results.begin();
1042  it != results.end(); ++it) {
1043  std::cout << "Number of solutions: " << it->first << std::endl;
1044  for (unsigned int i = 0; i < it->second.size(); ++i)
1045  std::cout << it->second[i] << " ";
1046  std::cout << std::endl;
1047  }
1048 
1049  delete root;
1050  return results.size() == 1;
1051  }
1052 #endif
1053 
1054 }}
1055 
1056 // STATISTICS: test-branch
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Recording actions for Boolean variables.
Definition: int.hh:4407
Recording CHB for Boolean variables.
Definition: int.hh:4502
Which values to select for branching first.
Definition: int.hh:4889
Boolean variable array.
Definition: int.hh:808
Which Boolean variable to select for branching.
Definition: int.hh:4656
Boolean integer variables.
Definition: int.hh:512
Depth-first search engine.
Definition: search.hh:1036
Recording actions for float variables.
Definition: float.hh:1555
Recording CHB for float variables.
Definition: float.hh:1607
Value description class for branching.
Definition: float.hh:1462
bool l
Whether to try the lower or upper half first.
Definition: float.hh:1467
FloatNum n
The middle value for branching.
Definition: float.hh:1465
Which values to select for branching first.
Definition: float.hh:1820
Float value type.
Definition: float.hh:334
FloatValImpType x
Implementation of float value.
Definition: float.hh:425
Float variable array.
Definition: float.hh:1030
Which variable to select for branching.
Definition: float.hh:1668
Float variables.
Definition: float.hh:870
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const FloatView &x)
Print float variable view.
Recording actions for integer variables.
Definition: int.hh:4362
Passing integer arguments.
Definition: int.hh:628
Recording CHB for integer variables.
Definition: int.hh:4458
Integer sets.
Definition: int.hh:174
Which values to select for branching first.
Definition: int.hh:4854
Integer variable array.
Definition: int.hh:763
Which integer variable to select for branching.
Definition: int.hh:4570
Integer variables.
Definition: int.hh:371
Random number generator.
Definition: rnd.hpp:42
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:46
Search engine options
Definition: search.hh:746
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:753
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:755
Recording actions for set variables.
Definition: set.hh:1183
Recording CHB for set variables.
Definition: set.hh:1235
Which values to select for branching first.
Definition: set.hh:1447
Set variable array
Definition: set.hh:570
Which variable to select for branching.
Definition: set.hh:1296
Iterator for the unknown ranges of a set variable.
Definition: set.hh:334
Set variables
Definition: set.hh:127
Computation spaces.
Definition: core.hpp:1742
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1013
Base class for all tests to be run
Definition: test.hh:103
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition: test.hh:134
Space for executing Boolean tests.
Definition: branch.cpp:91
BoolTestSpace(BoolTestSpace &s)
Constructor for cloning s.
Definition: branch.cpp:99
BoolTestSpace(int n)
Initialize test space.
Definition: branch.cpp:96
Gecode::BoolVarArray x
Variables to be tested.
Definition: branch.cpp:94
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: branch.cpp:104
BoolTest(const std::string &s, int a)
Construct and register test.
Definition: branch.cpp:604
int arity
Number of variables.
Definition: branch.hh:88
virtual bool run(void)
Perform test.
Definition: branch.cpp:609
virtual void post(Gecode::Space &home, Gecode::BoolVarArray &x)=0
Post propagators on variables x.
Space for executing Float tests.
Definition: branch.cpp:132
Gecode::FloatNumBranch float_val(const Gecode::Space &, Gecode::FloatVar x, int)
Test function for branch value function.
Definition: branch.cpp:377
FloatTestSpace(FloatTestSpace &s)
Constructor for cloning s.
Definition: branch.cpp:140
double float_merit(const Gecode::Space &, Gecode::FloatVar x, int)
Test function for branch merit function.
Definition: branch.cpp:363
Gecode::FloatVarArray x
Variables to be tested.
Definition: branch.cpp:135
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: branch.cpp:145
FloatTestSpace(int n, Gecode::FloatVal &d)
Initialize test space.
Definition: branch.cpp:137
Gecode::FloatVal dom
Domain of variables.
Definition: branch.hh:129
int arity
Number of variables.
Definition: branch.hh:127
int nbSols
Maximum number of solutions searched during solving.
Definition: branch.hh:131
FloatTest(const std::string &s, int a, const Gecode::FloatVal &d, int nbs)
Construct and register test.
Definition: branch.cpp:898
virtual void post(Gecode::Space &home, Gecode::FloatVarArray &x)=0
Post propagators on variables x.
virtual bool run(void)
Perform test.
Definition: branch.cpp:903
Space for executing integer tests.
Definition: branch.cpp:66
double bool_merit(const Gecode::Space &, Gecode::BoolVar x, int)
Test function for branch merit function.
Definition: branch.cpp:217
IntTestSpace(int n, Gecode::IntSet &d)
Initialize test space.
Definition: branch.cpp:75
Gecode::IntVarBranch varb
Definition: branch.cpp:71
Gecode::IntValBranch val
Varlue selection criterion.
Definition: branch.cpp:73
IntTestSpace(IntTestSpace &s)
Constructor for cloning s.
Definition: branch.cpp:80
Gecode::IntVarBranch vara
Variable selection criteria.
Definition: branch.cpp:71
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: branch.cpp:85
int int_val(const Gecode::Space &, Gecode::IntVar x, int)
Test function for branch value function.
Definition: branch.cpp:248
Gecode::IntVarArray x
Variables to be tested.
Definition: branch.cpp:69
double int_merit(const Gecode::Space &, Gecode::IntVar x, int)
Test function for branch merit function.
Definition: branch.cpp:213
int bool_val(const Gecode::Space &, Gecode::BoolVar x, int)
Test function for branch value function.
Definition: branch.cpp:252
IntTest(const std::string &s, int a, const Gecode::IntSet &d)
Construct and register test.
Definition: branch.cpp:430
int arity
Number of variables.
Definition: branch.hh:69
virtual bool run(void)
Perform test.
Definition: branch.cpp:435
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)=0
Post propagators on variables x.
Gecode::IntSet dom
Domain of variables.
Definition: branch.hh:71
Information about one test-run.
Definition: branch.cpp:386
void print(std::ostream &o) const
Definition: branch.cpp:394
unsigned int c_d
Definition: branch.cpp:389
std::string var
Definition: branch.cpp:388
unsigned int a_d
Definition: branch.cpp:389
std::string val
Definition: branch.cpp:388
RunInfo(const std::string &vara, const std::string &varb, const std::string &valname, const Gecode::Search::Options &o)
Definition: branch.cpp:390
Space for executing Set tests.
Definition: branch.cpp:111
double set_merit(const Gecode::Space &, Gecode::SetVar, int)
Test function for branch merit function.
Definition: branch.cpp:297
Gecode::SetVarArray x
Variables to be tested.
Definition: branch.cpp:114
int set_val(const Gecode::Space &, Gecode::SetVar x, int)
Test function for branch value function.
Definition: branch.cpp:316
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: branch.cpp:124
SetTestSpace(SetTestSpace &s)
Constructor for cloning s.
Definition: branch.cpp:119
SetTestSpace(int n, Gecode::IntSet &d)
Initialize test space.
Definition: branch.cpp:116
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x)=0
Post propagators on variables x.
int arity
Number of variables.
Definition: branch.hh:106
SetTest(const std::string &s, int a, const Gecode::IntSet &d)
Construct and register test.
Definition: branch.cpp:735
virtual bool run(void)
Perform test.
Definition: branch.cpp:740
Gecode::IntSet dom
Domain of variables.
Definition: branch.hh:108
FloatValBranch FLOAT_VAL_SPLIT_MAX(void)
Select values greater than mean of smallest and largest value.
Definition: val.hpp:60
FloatValBranch FLOAT_VAL(FloatBranchVal v, FloatBranchCommit c)
Definition: val.hpp:70
FloatValBranch FLOAT_VAL_SPLIT_RND(Rnd r)
Select values randomly which are not greater or not smaller than mean of largest and smallest value.
Definition: val.hpp:65
FloatValBranch FLOAT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:55
FloatVarBranch FLOAT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Select variable with largest degree divided by domain size.
Definition: var.hpp:222
FloatVarBranch FLOAT_VAR_DEGREE_SIZE_MIN(BranchTbl tbl)
Select variable with smallest degree divided by domain size.
Definition: var.hpp:217
FloatVarBranch FLOAT_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking)
Definition: var.hpp:112
FloatVarBranch FLOAT_VAR_AFC_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count with decay factor d.
Definition: var.hpp:127
FloatVarBranch FLOAT_VAR_SIZE_MAX(BranchTbl tbl)
Select variable with largest domain size.
Definition: var.hpp:212
FloatVarBranch FLOAT_VAR_MAX_MAX(BranchTbl tbl)
Select variable with largest max.
Definition: var.hpp:202
FloatVarBranch FLOAT_VAR_AFC_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smalllest accumulated failure count divided by domain size with decay factor d.
Definition: var.hpp:227
FloatVarBranch FLOAT_VAR_CHB_SIZE_MAX(BranchTbl tbl)
Select variable with largest CHB Q-score divided by domain size.
Definition: var.hpp:277
FloatVarBranch FLOAT_VAR_CHB_MIN(BranchTbl tbl)
Select variable with lowest CHB Q-score.
Definition: var.hpp:167
FloatVarBranch FLOAT_VAR_CHB_SIZE_MIN(BranchTbl tbl)
Select variable with smallest CHB Q-score divided by domain size.
Definition: var.hpp:267
FloatVarBranch FLOAT_VAR_ACTION_MAX(double d, BranchTbl tbl)
Select variable with highest action with decay factor d.
Definition: var.hpp:157
FloatVarBranch FLOAT_VAR_CHB_MAX(BranchTbl tbl)
Select variable with highest CHB Q-score.
Definition: var.hpp:177
FloatVarBranch FLOAT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:187
FloatVarBranch FLOAT_VAR_MAX_MIN(BranchTbl tbl)
Select variable with smallest max.
Definition: var.hpp:197
FloatVarBranch FLOAT_VAR_ACTION_MIN(double d, BranchTbl tbl)
Select variable with lowest action with decay factor d.
Definition: var.hpp:147
FloatVarBranch FLOAT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:97
FloatVarBranch FLOAT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:122
FloatVarBranch FLOAT_VAR_ACTION_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest action divided by domain size with decay factor d.
Definition: var.hpp:257
FloatVarBranch FLOAT_VAR_MIN_MAX(BranchTbl tbl)
Select variable with largest min.
Definition: var.hpp:192
FloatVarBranch FLOAT_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
Definition: var.hpp:237
FloatVarBranch FLOAT_VAR_MERIT_MIN(FloatBranchMerit bm, BranchTbl tbl)
Select variable with least merit according to branch merit function bm.
Definition: var.hpp:102
FloatVarBranch FLOAT_VAR_DEGREE_MIN(BranchTbl tbl)
Select variable with smallest degree.
Definition: var.hpp:117
FloatVarBranch FLOAT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:207
FloatVarBranch FLOAT_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:137
FloatVarBranch FLOAT_VAR_ACTION_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smallest action divided by domain size with decay factor d.
Definition: var.hpp:247
FloatVarBranch FLOAT_VAR_MERIT_MAX(FloatBranchMerit bm, BranchTbl tbl)
Select variable with highest merit according to branch merit function bm.
Definition: var.hpp:107
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
int bab(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for branch-and-bound search of root.
Definition: gist.hpp:208
Space(void)
Default constructor.
Definition: core.cpp:115
void branch(Home home, SetVar x, SetValBranch vals, SetVarValPrint vvp)
Branch over x with value selection vals.
Definition: branch.cpp:101
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3224
IntValBranch INT_VAL_SPLIT_MIN(void)
Select values not greater than mean of smallest and largest value.
Definition: val.hpp:75
IntValBranch INT_VAL_RANGE_MIN(void)
Select the smallest range of the variable domain if it has several ranges, otherwise select values no...
Definition: val.hpp:85
IntValBranch INT_VAL_RANGE_MAX(void)
Select the largest range of the variable domain if it has several ranges, otherwise select values gre...
Definition: val.hpp:90
BoolValBranch BOOL_VAL(BoolBranchVal v, BoolBranchCommit c)
Select value as defined by the value function v and commit function c Uses a commit function as defau...
Definition: val.hpp:145
IntValBranch INT_VALUES_MAX(void)
Try all values starting from largest.
Definition: val.hpp:105
IntValBranch INT_VAL_MED(void)
Select greatest value not greater than the median.
Definition: val.hpp:60
IntValBranch INT_VAL(IntBranchVal v, IntBranchCommit c)
Select value as defined by the value function v and commit function c Uses a commit function as defau...
Definition: val.hpp:95
BoolValBranch BOOL_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:130
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition: val.hpp:100
IntValBranch INT_VAL_MAX(void)
Select largest value.
Definition: val.hpp:65
BoolValBranch BOOL_VAL_MAX(void)
Select largest value.
Definition: val.hpp:135
IntValBranch INT_VAL_SPLIT_MAX(void)
Select values greater than mean of smallest and largest value.
Definition: val.hpp:80
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
BoolValBranch BOOL_VAL_RND(Rnd r)
Select random value.
Definition: val.hpp:140
IntValBranch INT_VAL_RND(Rnd r)
Select random value.
Definition: val.hpp:70
BoolVarBranch BOOL_VAR_CHB_MIN(BoolCHB c, BranchTbl tbl)
Select variable with lowest CHB Q-score.
Definition: var.hpp:434
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
Definition: var.hpp:236
IntVarBranch INT_VAR_CHB_SIZE_MIN(IntCHB c, BranchTbl tbl)
Select variable with smallest CHB Q-score divided by domain size.
Definition: var.hpp:266
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:121
IntVarBranch INT_VAR_REGRET_MIN_MIN(BranchTbl tbl)
Select variable with smallest min-regret.
Definition: var.hpp:286
IntVarBranch INT_VAR_ACTION_MAX(double d, BranchTbl tbl)
Select variable with highest action with decay factor d.
Definition: var.hpp:156
IntVarBranch INT_VAR_REGRET_MIN_MAX(BranchTbl tbl)
Select variable with largest min-regret.
Definition: var.hpp:291
IntVarBranch INT_VAR_ACTION_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest action divided by domain size with decay factor d.
Definition: var.hpp:256
BoolVarBranch BOOL_VAR_MERIT_MIN(BoolBranchMerit bm, BranchTbl tbl)
Select variable with least merit according to branch merit function bm.
Definition: var.hpp:374
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:96
IntVarBranch INT_VAR_CHB_MIN(IntCHB c, BranchTbl tbl)
Select variable with lowest CHB Q-score.
Definition: var.hpp:166
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:364
IntVarBranch INT_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:136
IntVarBranch INT_VAR_AFC_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count with decay factor d.
Definition: var.hpp:126
IntVarBranch INT_VAR_REGRET_MAX_MAX(BranchTbl tbl)
Select variable with largest max-regret.
Definition: var.hpp:301
IntVarBranch INT_VAR_CHB_MAX(IntCHB c, BranchTbl tbl)
Select variable with largest CHB Q-score.
Definition: var.hpp:176
BoolVarBranch BOOL_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking)
Definition: var.hpp:369
BoolVarBranch BOOL_VAR_ACTION_MIN(double d, BranchTbl tbl)
Select variable with lowest action with decay factor d.
Definition: var.hpp:414
BoolVarBranch BOOL_VAR_DEGREE_MIN(BranchTbl tbl)
Select variable with smallest degree.
Definition: var.hpp:384
IntVarBranch INT_VAR_MAX_MIN(BranchTbl tbl)
Select variable with smallest max.
Definition: var.hpp:196
BoolVarBranch BOOL_VAR_AFC_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count with decay factor d.
Definition: var.hpp:394
BoolVarBranch BOOL_VAR_AFC_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count with decay factor d.
Definition: var.hpp:404
BoolVarBranch BOOL_VAR_CHB_MAX(BoolCHB c, BranchTbl tbl)
Select variable with largest CHB Q-score.
Definition: var.hpp:444
IntVarBranch INT_VAR_MAX_MAX(BranchTbl tbl)
Select variable with largest max.
Definition: var.hpp:201
IntVarBranch INT_VAR_ACTION_MIN(double d, BranchTbl tbl)
Select variable with lowest action with decay factor d.
Definition: var.hpp:146
IntVarBranch INT_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking)
Definition: var.hpp:101
IntVarBranch INT_VAR_AFC_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smallest accumulated failure count divided by domain size with decay factor d.
Definition: var.hpp:226
IntVarBranch INT_VAR_DEGREE_MIN(BranchTbl tbl)
Select variable with smallest degree.
Definition: var.hpp:116
IntVarBranch INT_VAR_REGRET_MAX_MIN(BranchTbl tbl)
Select variable with smallest max-regret.
Definition: var.hpp:296
IntVarBranch INT_VAR_MERIT_MIN(IntBranchMerit bm, BranchTbl tbl)
Select variable with least merit according to branch merit function bm.
Definition: var.hpp:106
IntVarBranch INT_VAR_CHB_SIZE_MAX(IntCHB c, BranchTbl tbl)
Select variable with largest CHB Q-score divided by domain size.
Definition: var.hpp:276
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Select variable with largest degree divided by domain size.
Definition: var.hpp:221
IntVarBranch INT_VAR_MERIT_MAX(IntBranchMerit bm, BranchTbl tbl)
Select variable with highest merit according to branch merit function bm.
Definition: var.hpp:111
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:206
BoolVarBranch BOOL_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:389
IntVarBranch INT_VAR_ACTION_SIZE_MIN(double d, BranchTbl tbl)
Select variable with smallest action divided by domain size with decay factor d.
Definition: var.hpp:246
BoolVarBranch BOOL_VAR_ACTION_MAX(double d, BranchTbl tbl)
Select variable with highest action with decay factor d.
Definition: var.hpp:424
IntVarBranch INT_VAR_MIN_MAX(BranchTbl tbl)
Select variable with largest min.
Definition: var.hpp:191
BoolVarBranch BOOL_VAR_MERIT_MAX(BoolBranchMerit bm, BranchTbl tbl)
Select variable with highest merit according to branch merit function bm.
Definition: var.hpp:379
IntVarBranch INT_VAR_DEGREE_SIZE_MIN(BranchTbl tbl)
Select variable with smallest degree divided by domain size.
Definition: var.hpp:216
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl)
Select variable with smallest min.
Definition: var.hpp:186
IntVarBranch INT_VAR_SIZE_MAX(BranchTbl tbl)
Select variable with largest domain size.
Definition: var.hpp:211
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
double tbl(const Gecode::Space &, double w, double b)
Test function for tie-break limit function.
Definition: branch.cpp:61
int solutions(TestSpace *c, Gecode::Search::Options &o, int maxNbSol=-1)
Find number of solutions.
Definition: branch.cpp:412
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
LDSB< TieBreak > tiebreak("TieBreak")
General test support.
Definition: afc.cpp:39
Region r
Definition: region.cpp:65
SetValBranch SET_VAL_MED_INC(void)
Definition: val.hpp:65
SetValBranch SET_VAL_RND_INC(Rnd r)
Definition: val.hpp:85
SetValBranch SET_VAL_MAX_INC(void)
Definition: val.hpp:75
SetValBranch SET_VAL(SetBranchVal v, SetBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: val.hpp:95
SetValBranch SET_VAL_MED_EXC(void)
Definition: val.hpp:70
SetValBranch SET_VAL_RND_EXC(Rnd r)
Definition: val.hpp:90
SetValBranch SET_VAL_MIN_INC(void)
Definition: val.hpp:55
SetValBranch SET_VAL_MIN_EXC(void)
Definition: val.hpp:60
SetValBranch SET_VAL_MAX_EXC(void)
Definition: val.hpp:80
SetVarBranch SET_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Definition: var.hpp:221
SetVarBranch SET_VAR_ACTION_MAX(double d, BranchTbl tbl)
Definition: var.hpp:156
SetVarBranch SET_VAR_ACTION_MIN(double d, BranchTbl tbl)
Definition: var.hpp:146
SetVarBranch SET_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Definition: var.hpp:236
SetVarBranch SET_VAR_CHB_SIZE_MIN(BranchTbl tbl)
Definition: var.hpp:266
SetVarBranch SET_VAR_ACTION_SIZE_MAX(double d, BranchTbl tbl)
Definition: var.hpp:256
SetVarBranch SET_VAR_AFC_MAX(double d, BranchTbl tbl)
Definition: var.hpp:136
SetVarBranch SET_VAR_NONE(void)
Definition: var.hpp:96
SetVarBranch SET_VAR_MAX_MIN(BranchTbl tbl)
Definition: var.hpp:196
SetVarBranch SET_VAR_MERIT_MAX(SetBranchMerit bm, BranchTbl tbl)
Definition: var.hpp:111
SetVarBranch SET_VAR_SIZE_MAX(BranchTbl tbl)
Definition: var.hpp:211
SetVarBranch SET_VAR_SIZE_MIN(BranchTbl tbl)
Definition: var.hpp:206
SetVarBranch SET_VAR_DEGREE_MAX(BranchTbl tbl)
Definition: var.hpp:121
SetVarBranch SET_VAR_CHB_MIN(BranchTbl tbl)
Definition: var.hpp:166
SetVarBranch SET_VAR_RND(Rnd r)
Definition: var.hpp:101
SetVarBranch SET_VAR_CHB_SIZE_MAX(BranchTbl tbl)
Definition: var.hpp:276
SetVarBranch SET_VAR_CHB_MAX(BranchTbl tbl)
Definition: var.hpp:176
SetVarBranch SET_VAR_MIN_MAX(BranchTbl tbl)
Definition: var.hpp:191
SetVarBranch SET_VAR_ACTION_SIZE_MIN(double d, BranchTbl tbl)
Definition: var.hpp:246
SetVarBranch SET_VAR_MIN_MIN(BranchTbl tbl)
Definition: var.hpp:186
SetVarBranch SET_VAR_DEGREE_MIN(BranchTbl tbl)
Definition: var.hpp:116
SetVarBranch SET_VAR_AFC_SIZE_MIN(double d, BranchTbl tbl)
Definition: var.hpp:226
SetVarBranch SET_VAR_DEGREE_SIZE_MIN(BranchTbl tbl)
Definition: var.hpp:216
SetVarBranch SET_VAR_AFC_MIN(double d, BranchTbl tbl)
Definition: var.hpp:126
SetVarBranch SET_VAR_MERIT_MIN(SetBranchMerit bm, BranchTbl tbl)
Definition: var.hpp:106
SetVarBranch SET_VAR_MAX_MAX(BranchTbl tbl)
Definition: var.hpp:201