this repo has no description
dekker.one
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
58namespace Test { namespace Branch {
59
60 /// Test function for tie-break limit function
61 double tbl(const Gecode::Space&, double w, double b) {
62 return (w + (b-w)/2.0);
63 }
64
65 /// Space for executing integer tests
66 class IntTestSpace : public Gecode::Space {
67 public:
68 /// Variables to be tested
69 Gecode::IntVarArray x;
70 /// Variable selection criteria
71 Gecode::IntVarBranch vara, varb;
72 /// Varlue selection criterion
73 Gecode::IntValBranch val;
74 /// Initialize test space
75 IntTestSpace(int n, Gecode::IntSet& d)
76 : x(*this, n, d),
77 vara(Gecode::INT_VAR_NONE()), varb(Gecode::INT_VAR_NONE()),
78 val(Gecode::INT_VAL_MIN()) {}
79 /// Constructor for cloning \a s
80 IntTestSpace(IntTestSpace& s)
81 : Gecode::Space(s), vara(s.vara), varb(s.varb), val(s.val) {
82 x.update(*this, s.x);
83 }
84 /// Copy space during cloning
85 virtual Gecode::Space* copy(void) {
86 return new IntTestSpace(*this);
87 }
88 };
89
90 /// Space for executing Boolean tests
91 class BoolTestSpace : public Gecode::Space {
92 public:
93 /// Variables to be tested
94 Gecode::BoolVarArray x;
95 /// Initialize test space
96 BoolTestSpace(int n)
97 : x(*this, n, 0, 1) {}
98 /// Constructor for cloning \a s
99 BoolTestSpace(BoolTestSpace& s)
100 : Gecode::Space(s) {
101 x.update(*this, s.x);
102 }
103 /// Copy space during cloning
104 virtual Gecode::Space* copy(void) {
105 return new BoolTestSpace(*this);
106 }
107 };
108
109#ifdef GECODE_HAS_SET_VARS
110 /// Space for executing Set tests
111 class SetTestSpace : public Gecode::Space {
112 public:
113 /// Variables to be tested
114 Gecode::SetVarArray x;
115 /// Initialize test space
116 SetTestSpace(int n, Gecode::IntSet& d)
117 : x(*this, n, Gecode::IntSet::empty, d) {}
118 /// Constructor for cloning \a s
119 SetTestSpace(SetTestSpace& s)
120 : Gecode::Space(s) {
121 x.update(*this, s.x);
122 }
123 /// Copy space during cloning
124 virtual Gecode::Space* copy(void) {
125 return new SetTestSpace(*this);
126 }
127 };
128#endif
129
130#ifdef GECODE_HAS_FLOAT_VARS
131 /// Space for executing Float tests
132 class FloatTestSpace : public Gecode::Space {
133 public:
134 /// Variables to be tested
135 Gecode::FloatVarArray x;
136 /// Initialize test space
137 FloatTestSpace(int n, Gecode::FloatVal& d)
138 : x(*this, n, d.min(), d.max()) {}
139 /// Constructor for cloning \a s
140 FloatTestSpace(FloatTestSpace& s)
141 : Gecode::Space(s) {
142 x.update(*this, s.x);
143 }
144 /// Copy space during cloning
145 virtual Gecode::Space* copy(void) {
146 return new FloatTestSpace(*this);
147 }
148 };
149#endif
150
151 /** \name Collection of possible arguments for integer branchers
152 *
153 * \relates IntTestSpace BoolTestSpace
154 */
155 //@{
156 /// Names for integer variable selections
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 };
190 /// Number of integer variable selections
191 const int n_int_var_branch =
192 sizeof(int_var_branch_name)/sizeof(const char*);
193 /// Names for Boolean variable selections
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 };
209 /// Number of integer variable selections
210 const int n_bool_var_branch =
211 sizeof(bool_var_branch_name)/sizeof(const char*);
212 /// Test function for branch merit function
213 double int_merit(const Gecode::Space&, Gecode::IntVar x, int) {
214 return x.min();
215 }
216 /// Test function for branch merit function
217 double bool_merit(const Gecode::Space&, Gecode::BoolVar x, int) {
218 return x.min();
219 }
220 /// Names for integer value selections
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 };
234 /// Number of integer value selections
235 const int n_int_val_branch =
236 sizeof(int_val_branch_name)/sizeof(const char*);
237 /// Names for Boolean value selections
238 const char* bool_val_branch_name[] = {
239 "BOOL_VAL_MIN",
240 "BOOL_VAL_MAX",
241 "BOOL_VAL_RND",
242 "BOOL_VAL"
243 };
244 /// Number of Boolean value selections
245 const int n_bool_val_branch =
246 sizeof(bool_val_branch_name)/sizeof(const char*);
247 /// Test function for branch value function
248 int int_val(const Gecode::Space&, Gecode::IntVar x, int) {
249 return x.min();
250 }
251 /// Test function for branch value function
252 int bool_val(const Gecode::Space&, Gecode::BoolVar x, int) {
253 return x.min();
254 }
255 //@}
256
257#ifdef GECODE_HAS_SET_VARS
258 /** \name Collection of possible arguments for set branchers
259 *
260 * \relates SetTestSpace
261 */
262 //@{
263 /// Names for set variable selections
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 };
293 /// Number of set variable selections
294 const int n_set_var_branch =
295 sizeof(set_var_branch_name)/sizeof(const char*);
296 /// Test function for branch merit function
297 double set_merit(const Gecode::Space&, Gecode::SetVar, int) {
298 return 2.0;
299 }
300 /// Names for set value selections
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 };
312 /// Number of set value selections
313 const int n_set_val_branch =
314 sizeof(set_val_branch_name)/sizeof(const char*);
315 /// Test function for branch value function
316 int set_val(const Gecode::Space&, Gecode::SetVar x, int) {
317 Gecode::SetVarUnknownRanges r(x);
318 return r.min();
319 }
320 //@}
321#endif
322
323#ifdef GECODE_HAS_FLOAT_VARS
324 /** \name Collection of possible arguments for float branchers
325 *
326 * \relates FloatTestSpace
327 */
328 //@{
329 /// Names for float variable selections
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 };
359 /// Number of float variable selections
360 const int n_float_var_branch =
361 sizeof(float_var_branch_name)/sizeof(const char*);
362 /// Test function for branch merit function
363 double float_merit(const Gecode::Space&, Gecode::FloatVar x, int) {
364 return static_cast<double>(x.degree());
365 }
366 /// Names for float value selections
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 };
373 /// Number of float value selections
374 const int n_float_val_branch =
375 sizeof(float_val_branch_name)/sizeof(const char*);
376 /// Test function for branch value function
377 Gecode::FloatNumBranch float_val(const Gecode::Space&,
378 Gecode::FloatVar x, int) {
379 Gecode::FloatNumBranch nl; nl.n=x.med(); nl.l=true;
380 return nl;
381 }
382 //@}
383#endif
384
385 /// Information about one test-run
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
401std::ostream&
402operator<<(std::ostream& os, const Test::Branch::RunInfo& ri) {
403 ri.print(os);
404 return os;
405}
406
407
408namespace Test { namespace Branch {
409
410 /// Find number of solutions
411 template<class TestSpace>
412 int solutions(TestSpace* c, Gecode::Search::Options& o, Gecode::Support::RandomGenerator& rand, int maxNbSol = -1) {
413 o.a_d = rand(10);
414 o.c_d = 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 == nullptr) 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, true, true, &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 (_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 }
577 Gecode::Search::Options o;
578 results[solutions(c, o, _rand)].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
609 BoolTest::run(void) {
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, true, true, &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 (_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 }
707 Gecode::Search::Options o;
708 results[solutions(c, o, _rand)].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, true, true, &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 (_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 }
869 Gecode::Search::Options o;
870 results[solutions(c, o, _rand)].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
903 FloatTest::run(void) {
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, true, true, &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 (_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 }
1026 Gecode::Search::Options o;
1027 results[solutions(c, o, _rand, 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