Generated on Sat May 25 2013 18:00:33 for Gecode by doxygen 1.8.3.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-03-13 08:45:17 +0100 (Wed, 13 Mar 2013) $ by $Author: schulte $
17  * $Revision: 13522 $
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 
115  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 
136  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 
161  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 
239  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 
301  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  return x.med();
346  }
348 #endif
349 
351  class RunInfo {
352  public:
353  std::string var, val;
354  unsigned int a_d, c_d;
355  RunInfo(const std::string& vara, const std::string& varb,
356  const std::string& valname,
357  const Gecode::Search::Options& o)
358  : var(vara + "::" + varb), val(valname), a_d(o.a_d), c_d(o.c_d) {}
359  void print(std::ostream& o) const {
360  o << "(" << var << ", " << val << ", " << a_d << ", " << c_d << ")";
361  }
362  };
363 
364 }}
365 
366 std::ostream&
367 operator<<(std::ostream& os, const Test::Branch::RunInfo& ri) {
368  ri.print(os);
369  return os;
370 }
371 
372 
373 namespace Test { namespace Branch {
374 
376  template<class TestSpace>
377  int solutions(TestSpace* c, Gecode::Search::Options& o, int maxNbSol = -1) {
378  o.a_d = Base::rand(10);
379  o.c_d = Base::rand(10);
380  Gecode::DFS<TestSpace> e_s(c, o);
381  delete c;
382 
383  // Find number of solutions
384  int s = 0;
385  do {
386  Gecode::Space* ex = e_s.next();
387  if (ex == NULL) break;
388  delete ex;
389  ++s;
390  if ((maxNbSol >= 0) && (maxNbSol == s)) break;
391  } while (true);
392  return s;
393  }
394 
395  IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
396  : Base("Int::Branch::"+s), arity(a), dom(d) {
397  }
398 
399  bool
400  IntTest::run(void) {
401  using std::map;
402  using std::vector;
403  using std::string;
404  using std::ostream;
405  using namespace Gecode;
406 
407  // Results of tests run
408  map<int, vector<RunInfo> > results;
409  // Set up root space
410  IntTestSpace* root = new IntTestSpace(arity,dom);
411  post(*root, root->x);
412  results.clear();
413 
414  IntArgs d(arity);
415  for (int i=arity; i--; )
416  d[i]=i;
417 
418  for (int vara = 0; vara<n_int_var_branch; vara++) {
419  for (int varb = 1; varb<n_int_var_branch; varb++) {
420  for (int val = 0; val<n_int_val_branch; val++) {
421  Rnd r(1);
422 
423  IntValBranch ivb;
424  switch (val) {
425  case 0: ivb = INT_VAL_MIN(); break;
426  case 1: ivb = INT_VAL_MED(); break;
427  case 2: ivb = INT_VAL_MAX(); break;
428  case 3: ivb = INT_VAL_RND(r); break;
429  case 4: ivb = INT_VAL_SPLIT_MIN(); break;
430  case 5: ivb = INT_VAL_SPLIT_MAX(); break;
431  case 6: ivb = INT_VAL_RANGE_MIN(); break;
432  case 7: ivb = INT_VAL_RANGE_MAX(); break;
433  case 8: ivb = INT_VAL(&int_val); break;
434  case 9: ivb = INT_VALUES_MIN(); break;
435  case 10: ivb = INT_VALUES_MAX(); break;
436  case 11: ivb = INT_VAL_NEAR_MIN(d); break;
437  case 12: ivb = INT_VAL_NEAR_MAX(d); break;
438  case 13: ivb = INT_VAL_NEAR_INC(d); break;
439  case 14: ivb = INT_VAL_NEAR_DEC(d); break;
440  }
441 
442  IntTestSpace* c = static_cast<IntTestSpace*>(root->clone(false));
443 
444  if ((vara == 0) && (val < 11)) {
445  for (int i=0; i<c->x.size(); i++)
446  branch(*c, c->x[i], ivb);
447  } else {
448  Rnd ra(1);
449  IntVarBranch ivba;
450  IntActivity iaa(*c, c->x, 0.9);
451  switch (vara) {
452  case 0: ivba = INT_VAR_NONE(); break;
453  case 1: ivba = INT_VAR_NONE(); break;
454  case 2: ivba = INT_VAR_RND(ra); break;
455  case 3: ivba = INT_VAR_MERIT_MIN(&int_merit); break;
456  case 4: ivba = INT_VAR_MERIT_MAX(&int_merit); break;
457  case 5: ivba = INT_VAR_DEGREE_MIN(); break;
458  case 6: ivba = INT_VAR_DEGREE_MAX(); break;
459  case 7: ivba = INT_VAR_AFC_MIN(0.5); break;
460  case 8: ivba = INT_VAR_AFC_MAX(0.5); break;
461  case 9: ivba = INT_VAR_ACTIVITY_MIN(iaa); break;
462  case 10: ivba = INT_VAR_ACTIVITY_MAX(iaa); break;
463  case 11: ivba = INT_VAR_MIN_MIN(); break;
464  case 12: ivba = INT_VAR_MIN_MAX(); break;
465  case 13: ivba = INT_VAR_MAX_MIN(); break;
466  case 14: ivba = INT_VAR_MAX_MAX(); break;
467  case 15: ivba = INT_VAR_SIZE_MIN(); break;
468  case 16: ivba = INT_VAR_SIZE_MAX(); break;
469  case 17: ivba = INT_VAR_DEGREE_SIZE_MIN(); break;
470  case 18: ivba = INT_VAR_DEGREE_SIZE_MAX(); break;
471  case 19: ivba = INT_VAR_AFC_SIZE_MIN(); break;
472  case 20: ivba = INT_VAR_AFC_SIZE_MAX(); break;
473  case 21: ivba = INT_VAR_ACTIVITY_SIZE_MIN(iaa); break;
474  case 22: ivba = INT_VAR_ACTIVITY_SIZE_MAX(iaa); break;
475  case 23: ivba = INT_VAR_REGRET_MIN_MIN(); break;
476  case 24: ivba = INT_VAR_REGRET_MIN_MAX(); break;
477  case 25: ivba = INT_VAR_REGRET_MAX_MIN(); break;
478  case 26: ivba = INT_VAR_REGRET_MAX_MAX(); break;
479  }
480 
481  Rnd rb(2);
482  IntVarBranch ivbb;
483  IntActivity iab(*c, c->x, 0.9);
484  switch (varb) {
485  case 0: ivbb = INT_VAR_NONE(); break;
486  case 1: ivbb = INT_VAR_NONE(); break;
487  case 2: ivbb = INT_VAR_RND(rb); break;
488  case 3: ivbb = INT_VAR_MERIT_MIN(&int_merit,&tbl); break;
489  case 4: ivbb = INT_VAR_MERIT_MAX(&int_merit,&tbl); break;
490  case 5: ivbb = INT_VAR_DEGREE_MIN(&tbl); break;
491  case 6: ivbb = INT_VAR_DEGREE_MAX(&tbl); break;
492  case 7: ivbb = INT_VAR_AFC_MIN(0.5,&tbl); break;
493  case 8: ivbb = INT_VAR_AFC_MAX(0.5,&tbl); break;
494  case 9: ivbb = INT_VAR_ACTIVITY_MIN(iab,&tbl); break;
495  case 10: ivbb = INT_VAR_ACTIVITY_MAX(iab,&tbl); break;
496  case 11: ivbb = INT_VAR_MIN_MIN(&tbl); break;
497  case 12: ivbb = INT_VAR_MIN_MAX(&tbl); break;
498  case 13: ivbb = INT_VAR_MAX_MIN(&tbl); break;
499  case 14: ivbb = INT_VAR_MAX_MAX(&tbl); break;
500  case 15: ivbb = INT_VAR_SIZE_MIN(&tbl); break;
501  case 16: ivbb = INT_VAR_SIZE_MAX(&tbl); break;
502  case 17: ivbb = INT_VAR_DEGREE_SIZE_MIN(&tbl); break;
503  case 18: ivbb = INT_VAR_DEGREE_SIZE_MAX(&tbl); break;
504  case 19: ivbb = INT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
505  case 20: ivbb = INT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
506  case 21: ivbb = INT_VAR_ACTIVITY_SIZE_MIN(iab,&tbl); break;
507  case 22: ivbb = INT_VAR_ACTIVITY_SIZE_MAX(iab,&tbl); break;
508  case 23: ivbb = INT_VAR_REGRET_MIN_MIN(&tbl); break;
509  case 24: ivbb = INT_VAR_REGRET_MIN_MAX(&tbl); break;
510  case 25: ivbb = INT_VAR_REGRET_MAX_MIN(&tbl); break;
511  case 26: ivbb = INT_VAR_REGRET_MAX_MAX(&tbl); break;
512  }
513 
514  switch (Base::rand(9U)) {
515  case 0U:
516  branch(*c, c->x, ivba, ivb); break;
517  case 1U:
518  branch(*c, c->x, ivbb, ivb); break;
519  case 2U:
520  branch(*c, c->x, tiebreak(ivba,ivbb), ivb); break;
521  case 3U:
522  branch(*c, c->x, tiebreak(ivbb,ivba), ivb); break;
523  case 4U:
524  branch(*c, c->x, tiebreak(ivba,ivba,ivbb), ivb); break;
525  case 5U:
526  branch(*c, c->x, tiebreak(ivba,ivbb,ivbb), ivb); break;
527  case 6U:
528  branch(*c, c->x, tiebreak(ivbb,ivba,ivba), ivb); break;
529  case 7U:
530  branch(*c, c->x, tiebreak(ivba,ivba,ivbb,ivba), ivb); break;
531  case 8U:
532  branch(*c, c->x, tiebreak(ivbb,ivba,ivbb,ivba), ivb); break;
533  }
534 
535  }
537  results[solutions(c,o)].push_back
538  (RunInfo(int_var_branch_name[vara],
539  int_var_branch_name[varb],
540  int_val_branch_name[val],
541  o));
542  }
543  }
544  }
545  if (results.size() > 1)
546  goto failed;
547  delete root;
548  return true;
549  failed:
550  std::cout << "FAILURE" << std::endl;
551  for (map<int, vector<RunInfo> >::iterator it = results.begin();
552  it != results.end(); ++it) {
553  std::cout << "Number of solutions: " << it->first << std::endl;
554  for (unsigned int i = 0; i < it->second.size(); ++i)
555  std::cout << it->second[i] << " ";
556  std::cout << std::endl;
557  }
558 
559  delete root;
560  return results.size() == 1;
561  }
562 
563  BoolTest::BoolTest(const std::string& s, int a)
564  : Base("Bool::Branch::"+s), arity(a) {
565  }
566 
567  bool
569  using std::map;
570  using std::vector;
571  using std::string;
572  using std::ostream;
573  using namespace Gecode;
574 
575  // Results of tests run
576  map<int, vector<RunInfo> > results;
577  // Set up root space
578  BoolTestSpace* root = new BoolTestSpace(arity);
579  post(*root, root->x);
580  results.clear();
581 
582  IntArgs d(arity);
583  for (int i=arity; i--; )
584  d[i]=i % 2;
585 
586  for (int vara = 0; vara<n_int_var_branch; vara++) {
587  for (int varb = 1; varb<n_int_var_branch; varb++) {
588  for (int val = 0; val<n_int_val_branch; val++) {
589 
590  Rnd r(1);
591 
592  IntValBranch ivb;
593  switch (val) {
594  case 0: ivb = INT_VAL_MIN(); break;
595  case 1: ivb = INT_VAL_MED(); break;
596  case 2: ivb = INT_VAL_MAX(); break;
597  case 3: ivb = INT_VAL_RND(r); break;
598  case 4: ivb = INT_VAL_SPLIT_MIN(); break;
599  case 5: ivb = INT_VAL_SPLIT_MAX(); break;
600  case 6: ivb = INT_VAL_RANGE_MIN(); break;
601  case 7: ivb = INT_VAL_RANGE_MAX(); break;
602  case 8: ivb = INT_VAL(&bool_val); break;
603  case 9: ivb = INT_VALUES_MIN(); break;
604  case 10: ivb = INT_VALUES_MAX(); break;
605  case 11: ivb = INT_VAL_NEAR_MIN(d); break;
606  case 12: ivb = INT_VAL_NEAR_MAX(d); break;
607  case 13: ivb = INT_VAL_NEAR_INC(d); break;
608  case 14: ivb = INT_VAL_NEAR_DEC(d); break;
609  }
610 
611  BoolTestSpace* c = static_cast<BoolTestSpace*>(root->clone(false));
612 
613  if ((vara == 0) && (val < 11)) {
614  for (int i=0; i<c->x.size(); i++)
615  branch(*c, c->x[i], ivb);
616  } else {
617 
618 
619  Rnd ra(1);
620  IntVarBranch ivba;
621  IntActivity iaa(*c, c->x, 0.9);
622  switch (vara) {
623  case 0: ivba = INT_VAR_NONE(); break;
624  case 1: ivba = INT_VAR_NONE(); break;
625  case 2: ivba = INT_VAR_RND(ra); break;
626  case 3: ivba = INT_VAR_MERIT_MIN(&bool_merit); break;
627  case 4: ivba = INT_VAR_MERIT_MAX(&bool_merit); break;
628  case 5: ivba = INT_VAR_DEGREE_MIN(); break;
629  case 6: ivba = INT_VAR_DEGREE_MAX(); break;
630  case 7: ivba = INT_VAR_AFC_MIN(0.5); break;
631  case 8: ivba = INT_VAR_AFC_MAX(0.5); break;
632  case 9: ivba = INT_VAR_ACTIVITY_MIN(iaa); break;
633  case 10: ivba = INT_VAR_ACTIVITY_MAX(iaa); break;
634  case 11: ivba = INT_VAR_MIN_MIN(); break;
635  case 12: ivba = INT_VAR_MIN_MAX(); break;
636  case 13: ivba = INT_VAR_MAX_MIN(); break;
637  case 14: ivba = INT_VAR_MAX_MAX(); break;
638  case 15: ivba = INT_VAR_SIZE_MIN(); break;
639  case 16: ivba = INT_VAR_SIZE_MAX(); break;
640  case 17: ivba = INT_VAR_DEGREE_SIZE_MIN(); break;
641  case 18: ivba = INT_VAR_DEGREE_SIZE_MAX(); break;
642  case 19: ivba = INT_VAR_AFC_SIZE_MIN(); break;
643  case 20: ivba = INT_VAR_AFC_SIZE_MAX(); break;
644  case 21: ivba = INT_VAR_ACTIVITY_SIZE_MIN(iaa); break;
645  case 22: ivba = INT_VAR_ACTIVITY_SIZE_MAX(iaa); break;
646  case 23: ivba = INT_VAR_REGRET_MIN_MIN(); break;
647  case 24: ivba = INT_VAR_REGRET_MIN_MAX(); break;
648  case 25: ivba = INT_VAR_REGRET_MAX_MIN(); break;
649  case 26: ivba = INT_VAR_REGRET_MAX_MAX(); break;
650  }
651 
652  Rnd rb(2);
653  IntVarBranch ivbb;
654  IntActivity iab(*c, c->x, 0.9);
655  switch (varb) {
656  case 0: ivbb = INT_VAR_NONE(); break;
657  case 1: ivbb = INT_VAR_NONE(); break;
658  case 2: ivbb = INT_VAR_RND(rb); break;
659  case 3: ivbb = INT_VAR_MERIT_MIN(&bool_merit,&tbl); break;
660  case 4: ivbb = INT_VAR_MERIT_MAX(&bool_merit,&tbl); break;
661  case 5: ivbb = INT_VAR_DEGREE_MIN(&tbl); break;
662  case 6: ivbb = INT_VAR_DEGREE_MAX(&tbl); break;
663  case 7: ivbb = INT_VAR_AFC_MIN(0.5,&tbl); break;
664  case 8: ivbb = INT_VAR_AFC_MAX(0.5,&tbl); break;
665  case 9: ivbb = INT_VAR_ACTIVITY_MIN(iab,&tbl); break;
666  case 10: ivbb = INT_VAR_ACTIVITY_MAX(iab,&tbl); break;
667  case 11: ivbb = INT_VAR_MIN_MIN(&tbl); break;
668  case 12: ivbb = INT_VAR_MIN_MAX(&tbl); break;
669  case 13: ivbb = INT_VAR_MAX_MIN(&tbl); break;
670  case 14: ivbb = INT_VAR_MAX_MAX(&tbl); break;
671  case 15: ivbb = INT_VAR_SIZE_MIN(&tbl); break;
672  case 16: ivbb = INT_VAR_SIZE_MAX(&tbl); break;
673  case 17: ivbb = INT_VAR_DEGREE_SIZE_MIN(&tbl); break;
674  case 18: ivbb = INT_VAR_DEGREE_SIZE_MAX(&tbl); break;
675  case 19: ivbb = INT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
676  case 20: ivbb = INT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
677  case 21: ivbb = INT_VAR_ACTIVITY_SIZE_MIN(iab,&tbl); break;
678  case 22: ivbb = INT_VAR_ACTIVITY_SIZE_MAX(iab,&tbl); break;
679  case 23: ivbb = INT_VAR_REGRET_MIN_MIN(&tbl); break;
680  case 24: ivbb = INT_VAR_REGRET_MIN_MAX(&tbl); break;
681  case 25: ivbb = INT_VAR_REGRET_MAX_MIN(&tbl); break;
682  case 26: ivbb = INT_VAR_REGRET_MAX_MAX(&tbl); break;
683  }
684 
685  switch (Base::rand(9U)) {
686  case 0U:
687  branch(*c, c->x, ivba, ivb); break;
688  case 1U:
689  branch(*c, c->x, ivbb, ivb); break;
690  case 2U:
691  branch(*c, c->x, tiebreak(ivba,ivbb), ivb); break;
692  case 3U:
693  branch(*c, c->x, tiebreak(ivbb,ivba), ivb); break;
694  case 4U:
695  branch(*c, c->x, tiebreak(ivba,ivba,ivbb), ivb); break;
696  case 5U:
697  branch(*c, c->x, tiebreak(ivba,ivbb,ivbb), ivb); break;
698  case 6U:
699  branch(*c, c->x, tiebreak(ivbb,ivba,ivba), ivb); break;
700  case 7U:
701  branch(*c, c->x, tiebreak(ivba,ivba,ivbb,ivba), ivb); break;
702  case 8U:
703  branch(*c, c->x, tiebreak(ivbb,ivba,ivbb,ivba), ivb); 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(false));
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  SetActivity saa(*c, c->x, 0.9);
782  switch (vara) {
783  case 0: break;
784  case 1: svba = SET_VAR_NONE(); break;
785  case 2: svba = SET_VAR_RND(ra); break;
786  case 3: svba = SET_VAR_MERIT_MIN(&set_merit); break;
787  case 4: svba = SET_VAR_MERIT_MAX(&set_merit); break;
788  case 5: svba = SET_VAR_DEGREE_MIN(); break;
789  case 6: svba = SET_VAR_DEGREE_MAX(); break;
790  case 7: svba = SET_VAR_AFC_MIN(0.5); break;
791  case 8: svba = SET_VAR_AFC_MAX(0.5); break;
792  case 9: svba = SET_VAR_ACTIVITY_MIN(saa); break;
793  case 10: svba = SET_VAR_ACTIVITY_MAX(saa); break;
794  case 11: svba = SET_VAR_MIN_MIN(); break;
795  case 12: svba = SET_VAR_MIN_MAX(); break;
796  case 13: svba = SET_VAR_MAX_MIN(); break;
797  case 14: svba = SET_VAR_MAX_MAX(); break;
798  case 15: svba = SET_VAR_SIZE_MIN(); break;
799  case 16: svba = SET_VAR_SIZE_MAX(); break;
800  case 17: svba = SET_VAR_DEGREE_SIZE_MIN(); break;
801  case 18: svba = SET_VAR_DEGREE_SIZE_MAX(); break;
802  case 19: svba = SET_VAR_AFC_SIZE_MIN(); break;
803  case 20: svba = SET_VAR_AFC_SIZE_MAX(); break;
804  case 21: svba = SET_VAR_ACTIVITY_SIZE_MIN(saa); break;
805  case 22: svba = SET_VAR_ACTIVITY_SIZE_MAX(saa); break;
806  }
807 
808  Rnd rb(2);
809  SetVarBranch svbb;
810  SetActivity sab(*c, c->x, 0.9);
811  switch (varb) {
812  case 0: break;
813  case 1: svbb = SET_VAR_NONE(); break;
814  case 2: svbb = SET_VAR_RND(rb); break;
815  case 3: svbb = SET_VAR_MERIT_MIN(&set_merit,&tbl); break;
816  case 4: svbb = SET_VAR_MERIT_MAX(&set_merit,&tbl); break;
817  case 5: svbb = SET_VAR_DEGREE_MIN(&tbl); break;
818  case 6: svbb = SET_VAR_DEGREE_MAX(&tbl); break;
819  case 7: svbb = SET_VAR_AFC_MIN(0.5,&tbl); break;
820  case 8: svbb = SET_VAR_AFC_MAX(0.5,&tbl); break;
821  case 9: svbb = SET_VAR_ACTIVITY_MIN(sab,&tbl); break;
822  case 10: svbb = SET_VAR_ACTIVITY_MAX(sab,&tbl); break;
823  case 11: svbb = SET_VAR_MIN_MIN(&tbl); break;
824  case 12: svbb = SET_VAR_MIN_MAX(&tbl); break;
825  case 13: svbb = SET_VAR_MAX_MIN(&tbl); break;
826  case 14: svbb = SET_VAR_MAX_MAX(&tbl); break;
827  case 15: svbb = SET_VAR_SIZE_MIN(&tbl); break;
828  case 16: svbb = SET_VAR_SIZE_MAX(&tbl); break;
829  case 17: svbb = SET_VAR_DEGREE_SIZE_MIN(&tbl); break;
830  case 18: svbb = SET_VAR_DEGREE_SIZE_MAX(&tbl); break;
831  case 19: svbb = SET_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
832  case 20: svbb = SET_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
833  case 21: svbb = SET_VAR_ACTIVITY_SIZE_MIN(sab,&tbl); break;
834  case 22: svbb = SET_VAR_ACTIVITY_SIZE_MAX(sab,&tbl); break;
835  }
836 
837  switch (Base::rand(9U)) {
838  case 0U:
839  branch(*c, c->x, svba, svb); break;
840  case 1U:
841  branch(*c, c->x, svbb, svb); break;
842  case 2U:
843  branch(*c, c->x, tiebreak(svba,svbb), svb); break;
844  case 3U:
845  branch(*c, c->x, tiebreak(svbb,svba), svb); break;
846  case 4U:
847  branch(*c, c->x, tiebreak(svba,svba,svbb), svb); break;
848  case 5U:
849  branch(*c, c->x, tiebreak(svba,svbb,svbb), svb); break;
850  case 6U:
851  branch(*c, c->x, tiebreak(svbb,svba,svba), svb); break;
852  case 7U:
853  branch(*c, c->x, tiebreak(svba,svba,svbb,svba), svb); break;
854  case 8U:
855  branch(*c, c->x, tiebreak(svbb,svba,svbb,svba), svb); break;
856  }
857 
858  }
860  results[solutions(c,o)].push_back
861  (RunInfo(set_var_branch_name[vara],
862  set_var_branch_name[varb],
863  set_val_branch_name[val],
864  o));
865  }
866  }
867  }
868  if (results.size() > 1)
869  goto failed;
870  delete root;
871  return true;
872  failed:
873  std::cout << "FAILURE" << std::endl;
874  for (map<int, vector<RunInfo> >::iterator it = results.begin();
875  it != results.end(); ++it) {
876  std::cout << "Number of solutions: " << it->first << std::endl;
877  for (unsigned int i = 0; i < it->second.size(); ++i)
878  std::cout << it->second[i] << " ";
879  std::cout << std::endl;
880  }
881 
882  delete root;
883  return results.size() == 1;
884  }
885 #endif
886 
887 #ifdef GECODE_HAS_FLOAT_VARS
888  FloatTest::FloatTest(const std::string& s, int a, const Gecode::FloatVal& d, int nbs)
889  : Base("Float::Branch::"+s), arity(a), dom(d), nbSols(nbs) {
890  }
891 
892  bool
894  using std::map;
895  using std::vector;
896  using std::string;
897  using std::ostream;
898  using namespace Gecode;
899 
900  // Results of tests run
901  map<int, vector<RunInfo> > results;
902  // Set up root space
903  FloatTestSpace* root = new FloatTestSpace(arity,dom);
904  post(*root, root->x);
905  root->status();
906  results.clear();
907 
908  for (int vara = 0; vara<n_float_var_branch; vara++) {
909  for (int varb = 1; varb<n_float_var_branch; varb++) {
910  for (int val = 0; val<n_float_val_branch; val++) {
911  Rnd r(1);
912 
913  FloatValBranch fvb;
914  switch (val) {
915  case 0: fvb = FLOAT_VAL_SPLIT_MIN(); break;
916  case 1: fvb = FLOAT_VAL_SPLIT_MAX(); break;
917  case 2: fvb = FLOAT_VAL_SPLIT_RND(r); break;
918  case 3: fvb = FLOAT_VAL(&float_val); break;
919  }
920 
921  FloatTestSpace* c = static_cast<FloatTestSpace*>(root->clone(false));
922  if (vara == 0) {
923  for (int i=0; i<c->x.size(); i++)
924  branch(*c, c->x[i], fvb);
925  } else {
926  Rnd ra(1);
927  FloatVarBranch fvba;
928  FloatActivity faa(*c, c->x, 0.9);
929  switch (vara) {
930  case 0: break;
931  case 1: fvba = FLOAT_VAR_NONE(); break;
932  case 2: fvba = FLOAT_VAR_RND(ra); break;
933  case 3: fvba = FLOAT_VAR_MERIT_MIN(&float_merit); break;
934  case 4: fvba = FLOAT_VAR_MERIT_MAX(&float_merit); break;
935  case 5: fvba = FLOAT_VAR_DEGREE_MIN(); break;
936  case 6: fvba = FLOAT_VAR_DEGREE_MAX(); break;
937  case 7: fvba = FLOAT_VAR_AFC_MIN(0.5); break;
938  case 8: fvba = FLOAT_VAR_AFC_MAX(0.5); break;
939  case 9: fvba = FLOAT_VAR_ACTIVITY_MIN(faa); break;
940  case 10: fvba = FLOAT_VAR_ACTIVITY_MAX(faa); break;
941  case 11: fvba = FLOAT_VAR_MIN_MIN(); break;
942  case 12: fvba = FLOAT_VAR_MIN_MAX(); break;
943  case 13: fvba = FLOAT_VAR_MAX_MIN(); break;
944  case 14: fvba = FLOAT_VAR_MAX_MAX(); break;
945  case 15: fvba = FLOAT_VAR_SIZE_MIN(); break;
946  case 16: fvba = FLOAT_VAR_SIZE_MAX(); break;
947  case 17: fvba = FLOAT_VAR_DEGREE_SIZE_MIN(); break;
948  case 18: fvba = FLOAT_VAR_DEGREE_SIZE_MAX(); break;
949  case 19: fvba = FLOAT_VAR_AFC_SIZE_MIN(); break;
950  case 20: fvba = FLOAT_VAR_AFC_SIZE_MAX(); break;
951  case 21: fvba = FLOAT_VAR_ACTIVITY_SIZE_MIN(faa); break;
952  case 22: fvba = FLOAT_VAR_ACTIVITY_SIZE_MAX(faa); break;
953  }
954 
955  Rnd rb(2);
956  FloatVarBranch fvbb;
957  FloatActivity fab(*c, c->x, 0.9);
958  switch (varb) {
959  case 0: break;
960  case 1: fvbb = FLOAT_VAR_NONE(); break;
961  case 2: fvbb = FLOAT_VAR_RND(rb); break;
962  case 3: fvbb = FLOAT_VAR_MERIT_MIN(&float_merit,&tbl); break;
963  case 4: fvbb = FLOAT_VAR_MERIT_MAX(&float_merit,&tbl); break;
964  case 5: fvbb = FLOAT_VAR_DEGREE_MIN(&tbl); break;
965  case 6: fvbb = FLOAT_VAR_DEGREE_MAX(&tbl); break;
966  case 7: fvbb = FLOAT_VAR_AFC_MIN(0.5,&tbl); break;
967  case 8: fvbb = FLOAT_VAR_AFC_MAX(0.5,&tbl); break;
968  case 9: fvbb = FLOAT_VAR_ACTIVITY_MIN(fab,&tbl); break;
969  case 10: fvbb = FLOAT_VAR_ACTIVITY_MAX(fab,&tbl); break;
970  case 11: fvbb = FLOAT_VAR_MIN_MIN(&tbl); break;
971  case 12: fvbb = FLOAT_VAR_MIN_MAX(&tbl); break;
972  case 13: fvbb = FLOAT_VAR_MAX_MIN(&tbl); break;
973  case 14: fvbb = FLOAT_VAR_MAX_MAX(&tbl); break;
974  case 15: fvbb = FLOAT_VAR_SIZE_MIN(&tbl); break;
975  case 16: fvbb = FLOAT_VAR_SIZE_MAX(&tbl); break;
976  case 17: fvbb = FLOAT_VAR_DEGREE_SIZE_MIN(&tbl); break;
977  case 18: fvbb = FLOAT_VAR_DEGREE_SIZE_MAX(&tbl); break;
978  case 19: fvbb = FLOAT_VAR_AFC_SIZE_MIN(1.0,&tbl); break;
979  case 20: fvbb = FLOAT_VAR_AFC_SIZE_MAX(1.0,&tbl); break;
980  case 21: fvbb = FLOAT_VAR_ACTIVITY_SIZE_MIN(fab,&tbl); break;
981  case 22: fvbb = FLOAT_VAR_ACTIVITY_SIZE_MAX(fab,&tbl); break;
982  }
983 
984  switch (Base::rand(9U)) {
985  case 0U:
986  branch(*c, c->x, fvba, fvb); break;
987  case 1U:
988  branch(*c, c->x, fvbb, fvb); break;
989  case 2U:
990  branch(*c, c->x, tiebreak(fvba,fvbb), fvb); break;
991  case 3U:
992  branch(*c, c->x, tiebreak(fvbb,fvba), fvb); break;
993  case 4U:
994  branch(*c, c->x, tiebreak(fvba,fvba,fvbb), fvb); break;
995  case 5U:
996  branch(*c, c->x, tiebreak(fvba,fvbb,fvbb), fvb); break;
997  case 6U:
998  branch(*c, c->x, tiebreak(fvbb,fvba,fvba), fvb); break;
999  case 7U:
1000  branch(*c, c->x, tiebreak(fvba,fvba,fvbb,fvba), fvb); break;
1001  case 8U:
1002  branch(*c, c->x, tiebreak(fvbb,fvba,fvbb,fvba), fvb); break;
1003  }
1004 
1005  }
1007  results[solutions(c,o,nbSols)].push_back
1008  (RunInfo(float_var_branch_name[vara],
1009  float_var_branch_name[varb],
1010  float_val_branch_name[val],
1011  o));
1012  }
1013  }
1014  }
1015  if (results.size() > 1)
1016  goto failed;
1017  delete root;
1018  return true;
1019  failed:
1020  std::cout << "FAILURE" << std::endl;
1021  for (map<int, vector<RunInfo> >::iterator it = results.begin();
1022  it != results.end(); ++it) {
1023  std::cout << "Number of solutions: " << it->first << std::endl;
1024  for (unsigned int i = 0; i < it->second.size(); ++i)
1025  std::cout << it->second[i] << " ";
1026  std::cout << std::endl;
1027  }
1028 
1029  delete root;
1030  return results.size() == 1;
1031  }
1032 #endif
1033 
1034 }}
1035 
1036 // STATISTICS: test-branch