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