this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2008
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/minimodel.hh>
35#include <gecode/search.hh>
36
37#include "test/test.hh"
38
39namespace Test {
40
41 /// Tests for search engines
42 namespace Search {
43
44 using namespace Gecode;
45 using namespace Gecode::Int;
46
47 /// Values for selecting branchers
48 enum HowToBranch {
49 HTB_NONE, ///< Do not branch
50 HTB_UNARY, ///< Branch with single alternative
51 HTB_BINARY, ///< Branch with two alternatives
52 HTB_NARY ///< Branch with many alternatives
53 };
54
55 /// Values for selecting how to constrain
56 enum HowToConstrain {
57 HTC_NONE, ///< Do not constrain
58 HTC_LEX_LE, ///< Constrain for lexically smallest
59 HTC_LEX_GR, ///< Constrain for lexically biggest
60 HTC_BAL_LE, ///< Constrain for smallest balance
61 HTC_BAL_GR ///< Constrain for largest balance
62 };
63
64 /// Values for selecting models
65 enum WhichModel {
66 WM_FAIL_IMMEDIATE, ///< Model that fails immediately
67 WM_FAIL_SEARCH, ///< Model without solutions
68 WM_SOLUTIONS ///< Model with solutions
69 };
70
71 /// Space with information
72 class TestSpace : public Space {
73 public:
74 /// Constructor for space creation
75 TestSpace(void) {}
76 /// Constructor for cloning \a s
77 TestSpace(TestSpace& s) : Space(s) {}
78 /// Return number of solutions
79 virtual int solutions(void) const = 0;
80 /// Verify that this is best solution
81 virtual bool best(void) const = 0;
82 /// Master configuration function that does not restart
83 virtual bool master(const MetaInfo& mi) {
84 if (mi.type() == MetaInfo::RESTART) {
85 if (mi.last() != nullptr)
86 constrain(*mi.last());
87 return false;
88 } else {
89 return false;
90 }
91 }
92 };
93
94 /// Space that immediately fails
95 class FailImmediate : public TestSpace {
96 public:
97 /// Variables used
98 IntVarArray x;
99 /// Constructor for space creation
100 FailImmediate(HowToBranch, HowToBranch, HowToBranch,
101 HowToConstrain=HTC_NONE)
102 : x(*this,1,0,0) {
103 rel(*this, x[0], IRT_EQ, 1);
104 }
105 /// Constructor for cloning \a s
106 FailImmediate(FailImmediate& s) : TestSpace(s) {
107 x.update(*this, s.x);
108 }
109 /// Copy during cloning
110 virtual Space* copy(void) {
111 return new FailImmediate(*this);
112 }
113 /// Add constraint for next better solution
114 virtual void constrain(const Space&) {
115 }
116 /// Return number of solutions
117 virtual int solutions(void) const {
118 return 0;
119 }
120 /// Verify that this is best solution
121 virtual bool best(void) const {
122 return false;
123 }
124 /// Return name
125 static std::string name(void) {
126 return "Fail";
127 }
128 };
129
130 /// Space that is immediately solved
131 class SolveImmediate : public TestSpace {
132 public:
133 /// Variables used
134 IntVarArray x;
135 /// Constructor for space creation
136 SolveImmediate(HowToBranch, HowToBranch, HowToBranch,
137 HowToConstrain=HTC_NONE)
138 : x(*this,1,0,0) {}
139 /// Constructor for cloning \a s
140 SolveImmediate(SolveImmediate& s) : TestSpace(s) {
141 x.update(*this, s.x);
142 }
143 /// Copy during cloning
144 virtual Space* copy(void) {
145 return new SolveImmediate(*this);
146 }
147 /// Add constraint for next better solution
148 virtual void constrain(const Space&) {
149 fail();
150 }
151 /// Return number of solutions
152 virtual int solutions(void) const {
153 return 1;
154 }
155 /// Verify that this is best solution
156 virtual bool best(void) const {
157 return true;
158 }
159 /// Return name
160 static std::string name(void) {
161 return "Solve";
162 }
163 };
164
165 /// Space that requires propagation and has solutions
166 class HasSolutions : public TestSpace {
167 public:
168 /// Variables used
169 IntVarArray x;
170 /// How to branch
171 HowToBranch htb1, htb2, htb3;
172 /// How to constrain
173 HowToConstrain htc;
174 /// Branch on \a x according to \a htb
175 void branch(const IntVarArgs& x, HowToBranch htb) {
176 switch (htb) {
177 case HTB_NONE:
178 break;
179 case HTB_UNARY:
180 assign(*this, x, INT_ASSIGN_MIN());
181 break;
182 case HTB_BINARY:
183 Gecode::branch(*this, x, INT_VAR_NONE(), INT_VAL_MIN());
184 break;
185 case HTB_NARY:
186 Gecode::branch(*this, x, INT_VAR_NONE(), INT_VALUES_MIN());
187 break;
188 }
189 }
190 /// Constructor for space creation
191 HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
192 HowToConstrain _htc=HTC_NONE)
193 : x(*this,6,0,5), htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {
194 distinct(*this, x);
195 rel(*this, x[2], IRT_LQ, 3); rel(*this, x[3], IRT_LQ, 3);
196 rel(*this, x[4], IRT_LQ, 1); rel(*this, x[5], IRT_LQ, 1);
197 IntVarArgs x1(2); x1[0]=x[0]; x1[1]=x[1]; branch(x1, htb1);
198 IntVarArgs x2(2); x2[0]=x[2]; x2[1]=x[3]; branch(x2, htb2);
199 IntVarArgs x3(2); x3[0]=x[4]; x3[1]=x[5]; branch(x3, htb3);
200 }
201 /// Constructor for cloning \a s
202 HasSolutions(HasSolutions& s)
203 : TestSpace(s),
204 htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
205 x.update(*this, s.x);
206 }
207 /// Copy during cloning
208 virtual Space* copy(void) {
209 return new HasSolutions(*this);
210 }
211 /// Add constraint for next better solution
212 virtual void constrain(const Space& _s) {
213 const HasSolutions& s = static_cast<const HasSolutions&>(_s);
214 switch (htc) {
215 case HTC_NONE:
216 break;
217 case HTC_LEX_LE:
218 case HTC_LEX_GR:
219 {
220 IntVarArgs y(6);
221 for (int i=0; i<6; i++)
222 y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
223 lex(*this, x, (htc == HTC_LEX_LE) ? IRT_LE : IRT_GR, y);
224 break;
225 }
226 case HTC_BAL_LE:
227 case HTC_BAL_GR:
228 {
229 IntVarArgs y(6);
230 for (int i=0; i<6; i++)
231 y[i] = IntVar(*this, s.x[i].val(), s.x[i].val());
232 IntVar xs(*this, -18, 18);
233 IntVar ys(*this, -18, 18);
234 rel(*this, x[0]+x[1]+x[2]-x[3]-x[4]-x[5] == xs);
235 rel(*this, y[0]+y[1]+y[2]-y[3]-y[4]-y[5] == ys);
236 rel(*this,
237 expr(*this,abs(xs)),
238 (htc == HTC_BAL_LE) ? IRT_LE : IRT_GR,
239 expr(*this,abs(ys)));
240 break;
241 }
242 }
243 }
244 /// Return number of solutions
245 virtual int solutions(void) const {
246 if (htb1 == HTB_NONE) {
247 assert((htb2 == HTB_NONE) && (htb3 == HTB_NONE));
248 return 1;
249 }
250 if ((htb1 == HTB_UNARY) || (htb2 == HTB_UNARY))
251 return 0;
252 if (htb3 == HTB_UNARY)
253 return 4;
254 return 8;
255 }
256 /// Verify that this is best solution
257 virtual bool best(void) const {
258 if ((htb1 == HTB_NONE) || (htb2 == HTB_NONE) || (htb3 == HTB_NONE) ||
259 (htb1 == HTB_UNARY) || (htb2 == HTB_UNARY) || (htb3 == HTB_UNARY))
260 return true;
261 switch (htc) {
262 case HTC_NONE:
263 return true;
264 case HTC_LEX_LE:
265 return ((x[0].val()==4) && (x[1].val()==5) &&
266 (x[2].val()==2) && (x[3].val()==3) &&
267 (x[4].val()==0) && (x[5].val()==1));
268 case HTC_LEX_GR:
269 return ((x[0].val()==5) && (x[1].val()==4) &&
270 (x[2].val()==3) && (x[3].val()==2) &&
271 (x[4].val()==1) && (x[5].val()==0));
272 case HTC_BAL_LE:
273 return ((x[0].val()==4) && (x[1].val()==5) &&
274 (x[2].val()==2) && (x[3].val()==3) &&
275 (x[4].val()==0) && (x[5].val()==1));
276 case HTC_BAL_GR:
277 return ((x[0].val()==4) && (x[1].val()==5) &&
278 (x[2].val()==3) && (x[3].val()==2) &&
279 (x[4].val()==0) && (x[5].val()==1));
280 default: GECODE_NEVER;
281 }
282 return false;
283 }
284 /// Return name
285 static std::string name(void) {
286 return "Sol";
287 }
288 /// Rule out that solution is found more than once during restarts
289 virtual bool master(const MetaInfo& mi) {
290 switch (mi.type()) {
291 case MetaInfo::RESTART:
292 if (mi.last() != nullptr) {
293 const HasSolutions* s
294 = static_cast<const HasSolutions*>(mi.last());
295 BoolVarArgs b;
296 for (int i=0; i<x.size(); i++)
297 b << expr(*this, x[i] == s->x[i]);
298 rel(*this, BOT_AND, b, 0);
299 }
300 break;
301 case MetaInfo::PORTFOLIO:
302 // Do not kill the brancher!
303 break;
304 default:
305 break;
306 }
307 return false;
308 }
309 };
310
311 /// %Base class for search tests
312 class Test : public Base {
313 public:
314 /// How to branch
315 HowToBranch htb1, htb2, htb3;
316 /// How to constrain
317 HowToConstrain htc;
318 /// Map unsigned integer to string
319 static std::string str(unsigned int i) {
320 std::stringstream s;
321 s << i;
322 return s.str();
323 }
324 /// Map branching to string
325 static std::string str(HowToBranch htb) {
326 switch (htb) {
327 case HTB_NONE: return "None";
328 case HTB_UNARY: return "Unary";
329 case HTB_BINARY: return "Binary";
330 case HTB_NARY: return "Nary";
331 default: GECODE_NEVER;
332 }
333 GECODE_NEVER;
334 return "";
335 }
336 /// Map constrain to string
337 static std::string str(HowToConstrain htc) {
338 switch (htc) {
339 case HTC_NONE: return "None";
340 case HTC_LEX_LE: return "LexLe";
341 case HTC_LEX_GR: return "LexGr";
342 case HTC_BAL_LE: return "BalLe";
343 case HTC_BAL_GR: return "BalGr";
344 default: GECODE_NEVER;
345 }
346 GECODE_NEVER;
347 return "";
348 }
349 /// Initialize test
350 Test(const std::string& s,
351 HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3,
352 HowToConstrain _htc=HTC_NONE)
353 : Base("Search::"+s),
354 htb1(_htb1), htb2(_htb2), htb3(_htb3), htc(_htc) {}
355 };
356
357 /// %Test for depth-first search
358 template<class Model>
359 class DFS : public Test {
360 private:
361 /// Minimal recomputation distance
362 unsigned int c_d;
363 /// Adaptive recomputation distance
364 unsigned int a_d;
365 /// Number of threads
366 unsigned int t;
367 public:
368 /// Initialize test
369 DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
370 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
371 : Test("DFS::"+Model::name()+"::"+
372 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
373 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
374 htb1,htb2,htb3), c_d(c_d0), a_d(a_d0), t(t0) {}
375 /// Run test
376 virtual bool run(void) {
377 Model* m = new Model(htb1,htb2,htb3);
378 Gecode::Search::FailStop f(2);
379 Gecode::Search::Options o;
380 o.c_d = c_d;
381 o.a_d = a_d;
382 o.threads = t;
383 o.stop = &f;
384 Gecode::DFS<Model> dfs(m,o);
385 int n = m->solutions();
386 delete m;
387 while (true) {
388 Model* s = dfs.next();
389 if (s != nullptr) {
390 n--; delete s;
391 }
392 if ((s == nullptr) && !dfs.stopped())
393 break;
394 f.limit(f.limit()+2);
395 }
396 return n == 0;
397 }
398 };
399
400 /// %Test for limited discrepancy search
401 template<class Model>
402 class LDS : public Test {
403 private:
404 /// Number of threads
405 unsigned int t;
406 public:
407 /// Initialize test
408 LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
409 unsigned int t0)
410 : Test("LDS::"+Model::name()+"::"+
411 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+str(t0),
412 htb1,htb2,htb3), t(t0) {}
413 /// Run test
414 virtual bool run(void) {
415 Model* m = new Model(htb1,htb2,htb3);
416 Gecode::Search::FailStop f(2);
417 Gecode::Search::Options o;
418 o.threads = t;
419 o.d_l = 50;
420 o.stop = &f;
421 Gecode::LDS<Model> lds(m,o);
422 int n = m->solutions();
423 delete m;
424 while (true) {
425 Model* s = lds.next();
426 if (s != nullptr) {
427 n--; delete s;
428 }
429 if ((s == nullptr) && !lds.stopped())
430 break;
431 f.limit(f.limit()+2);
432 }
433 return n == 0;
434 }
435 };
436
437 /// %Test for best solution search
438 template<class Model>
439 class BAB : public Test {
440 private:
441 /// Minimal recomputation distance
442 unsigned int c_d;
443 /// Adaptive recomputation distance
444 unsigned int a_d;
445 /// Number of threads
446 unsigned int t;
447 public:
448 /// Initialize test
449 BAB(HowToConstrain htc,
450 HowToBranch htb1, HowToBranch htb2, HowToBranch htb3,
451 unsigned int c_d0, unsigned int a_d0, unsigned int t0)
452 : Test("BAB::"+Model::name()+"::"+str(htc)+"::"+
453 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+
454 str(c_d0)+"::"+str(a_d0)+"::"+str(t0),
455 htb1,htb2,htb3,htc), c_d(c_d0), a_d(a_d0), t(t0) {}
456 /// Run test
457 virtual bool run(void) {
458 Model* m = new Model(htb1,htb2,htb3,htc);
459 Gecode::Search::FailStop f(2);
460 Gecode::Search::Options o;
461 o.c_d = c_d;
462 o.a_d = a_d;
463 o.threads = t;
464 o.stop = &f;
465 Gecode::BAB<Model> bab(m,o);
466 delete m;
467 Model* b = nullptr;
468 while (true) {
469 Model* s = bab.next();
470 if (s != nullptr) {
471 delete b; b=s;
472 }
473 if ((s == nullptr) && !bab.stopped())
474 break;
475 f.limit(f.limit()+2);
476 }
477 bool ok = (b == nullptr) || b->best();
478 delete b;
479 return ok;
480 }
481 };
482
483 /// %Test for restart-based search
484 template<class Model, template<class> class Engine>
485 class RBS : public Test {
486 private:
487 /// Number of threads
488 unsigned int t;
489 public:
490 /// Initialize test
491 RBS(const std::string& e, unsigned int t0)
492 : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
493 HTB_BINARY,HTB_BINARY,HTB_BINARY), t(t0) {}
494 /// Run test
495 virtual bool run(void) {
496 Model* m = new Model(htb1,htb2,htb3);
497 Gecode::Search::FailStop f(2);
498 Gecode::Search::Options o;
499 o.threads = t;
500 o.stop = &f;
501 o.d_l = 100;
502 o.cutoff = Gecode::Search::Cutoff::geometric(1,2);
503 Gecode::RBS<Model,Engine> rbs(m,o);
504 int n = m->solutions();
505 delete m;
506 while (true) {
507 Model* s = rbs.next();
508 if (s != nullptr) {
509 n--; delete s;
510 }
511 if ((s == nullptr) && !rbs.stopped())
512 break;
513 f.limit(f.limit()+2);
514 }
515 return n == 0;
516 }
517 };
518
519 /// %Test for portfolio-based search
520 template<class Model, template<class> class Engine>
521 class PBS : public Test {
522 private:
523 /// Whether best solution search is used
524 bool best;
525 /// Number of assets
526 unsigned int a;
527 /// Number of threads
528 unsigned int t;
529 public:
530 /// Initialize test
531 PBS(const std::string& e, bool b, unsigned int a0, unsigned int t0)
532 : Test("PBS::"+e+"::"+Model::name()+"::"+str(a0)+"::"+str(t0),
533 HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), a(a0), t(t0) {}
534 /// Run test
535 virtual bool run(void) {
536 Model* m = new Model(htb1,htb2,htb3);
537 Gecode::Search::FailStop f(2);
538 Gecode::Search::Options o;
539 o.assets = a;
540 o.threads = t;
541 o.d_l = 100;
542 o.stop = &f;
543 Gecode::PBS<Model,Engine> pbs(m,o);
544 if (best) {
545 Model* b = nullptr;
546 while (true) {
547 Model* s = pbs.next();
548 if (s != nullptr) {
549 delete b; b=s;
550 }
551 if ((s == nullptr) && !pbs.stopped())
552 break;
553 f.limit(f.limit()+2);
554 }
555 bool ok = (b == nullptr) || b->best();
556 delete b;
557 return ok;
558 } else {
559 int n = ((t > 1) ? std::min(a,t) : a) * m->solutions();
560 delete m;
561 while (true) {
562 Model* s = pbs.next();
563 if (s != nullptr) {
564 n--; delete s;
565 }
566 if ((s == nullptr) && !pbs.stopped())
567 break;
568 f.limit(f.limit()+2);
569 }
570 return n >= 0;
571 }
572 }
573 };
574
575 /// %Test for portfolio-based search using SEBs
576 template<class Model>
577 class SEBPBS : public Test {
578 private:
579 /// Whether best solution search is used
580 bool best;
581 /// Number of master threads
582 unsigned int mt;
583 /// Number of slave threads
584 unsigned int st;
585 public:
586 /// Initialize test
587 SEBPBS(const std::string& e, bool b, unsigned int mt0, unsigned int st0)
588 : Test("PBS::SEB::"+e+"::"+Model::name()+"::"+str(mt0)+"::"+str(st0),
589 HTB_BINARY,HTB_BINARY,HTB_BINARY), best(b), mt(mt0), st(st0) {}
590 /// Run test
591 virtual bool run(void) {
592 using namespace Gecode;
593 Model* m = new Model(htb1,htb2,htb3);
594 Gecode::Search::FailStop f(2);
595
596 Gecode::Search::Options mo;
597 mo.threads = mt;
598 mo.d_l = 100;
599 mo.stop = &f;
600
601 Gecode::Search::Options so;
602 so.threads = st;
603 so.d_l = 100;
604 so.cutoff = Gecode::Search::Cutoff::constant(1000000);
605 if (best) {
606 SEBs sebs(3);
607 sebs[0] = bab<Model>(so);
608 sebs[1] = bab<Model>(so);
609 sebs[2] = rbs<Model,Gecode::BAB>(so);
610 Gecode::PBS<Model,Gecode::BAB> pbs(m, sebs, mo);
611 delete m;
612
613 Model* b = nullptr;
614 while (true) {
615 Model* s = pbs.next();
616 if (s != nullptr) {
617 delete b; b=s;
618 }
619 if ((s == nullptr) && !pbs.stopped())
620 break;
621 f.limit(f.limit()+2);
622 }
623 bool ok = (b == nullptr) || b->best();
624 delete b;
625 return ok;
626 } else {
627 SEBs sebs(3);
628 sebs[0] = dfs<Model>(so);
629 sebs[1] = lds<Model>(so);
630 sebs[2] = rbs<Model,Gecode::DFS>(so);
631 Gecode::PBS<Model,Gecode::DFS> pbs(m, sebs, mo);
632
633 int n = 3 * m->solutions();
634 delete m;
635
636 while (true) {
637 Model* s = pbs.next();
638 if (s != nullptr) {
639 n--; delete s;
640 }
641 if ((s == nullptr) && !pbs.stopped())
642 break;
643 f.limit(f.limit()+2);
644 }
645 return n >= 0;
646 }
647 }
648 };
649
650 /// Iterator for branching types
651 class BranchTypes {
652 private:
653 /// Array of branching types
654 static const HowToBranch htbs[3];
655 /// Current position in branching type array
656 int i;
657 public:
658 /// Initialize iterator
659 BranchTypes(void) : i(0) {}
660 /// Test whether iterator is done
661 bool operator()(void) const {
662 return i<3;
663 }
664 /// Increment to next branching type
665 void operator++(void) {
666 i++;
667 }
668 /// Return current branching type
669 HowToBranch htb(void) const {
670 return htbs[i];
671 }
672 };
673
674 const HowToBranch BranchTypes::htbs[3] = {HTB_UNARY, HTB_BINARY, HTB_NARY};
675
676 /// Iterator for constrain types
677 class ConstrainTypes {
678 private:
679 /// Array of constrain types
680 static const HowToConstrain htcs[4];
681 /// Current position in constrain type array
682 int i;
683 public:
684 /// Initialize iterator
685 ConstrainTypes(void) : i(0) {}
686 /// Test whether iterator is done
687 bool operator()(void) const {
688 return i<4;
689 }
690 /// Increment to next constrain type
691 void operator++(void) {
692 i++;
693 }
694 /// Return current constrain type
695 HowToConstrain htc(void) const {
696 return htcs[i];
697 }
698 };
699
700 const HowToConstrain ConstrainTypes::htcs[4] =
701 {HTC_LEX_LE, HTC_LEX_GR, HTC_BAL_LE, HTC_BAL_GR};
702
703
704 /// Help class to create and register tests
705 class Create {
706 public:
707 /// Perform creation and registration
708 Create(void) {
709 // Depth-first search
710 for (unsigned int t = 1; t<=4; t++)
711 for (unsigned int c_d = 1; c_d<10; c_d++)
712 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
713 for (BranchTypes htb1; htb1(); ++htb1)
714 for (BranchTypes htb2; htb2(); ++htb2)
715 for (BranchTypes htb3; htb3(); ++htb3)
716 (void) new DFS<HasSolutions>
717 (htb1.htb(),htb2.htb(),htb3.htb(),c_d, a_d, t);
718 new DFS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
719 c_d, a_d, t);
720 new DFS<SolveImmediate>(HTB_NONE, HTB_NONE, HTB_NONE,
721 c_d, a_d, t);
722 new DFS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE,
723 c_d, a_d, t);
724 }
725
726 // Limited discrepancy search
727 for (unsigned int t = 1; t<=4; t++) {
728 for (BranchTypes htb1; htb1(); ++htb1)
729 for (BranchTypes htb2; htb2(); ++htb2)
730 for (BranchTypes htb3; htb3(); ++htb3)
731 (void) new LDS<HasSolutions>(htb1.htb(),htb2.htb(),htb3.htb()
732 ,t);
733 new LDS<FailImmediate>(HTB_NONE, HTB_NONE, HTB_NONE, t);
734 new LDS<HasSolutions>(HTB_NONE, HTB_NONE, HTB_NONE, t);
735 }
736
737 // Best solution search
738 for (unsigned int t = 1; t<=4; t++)
739 for (unsigned int c_d = 1; c_d<10; c_d++)
740 for (unsigned int a_d = 1; a_d<=c_d; a_d++) {
741 for (ConstrainTypes htc; htc(); ++htc)
742 for (BranchTypes htb1; htb1(); ++htb1)
743 for (BranchTypes htb2; htb2(); ++htb2)
744 for (BranchTypes htb3; htb3(); ++htb3) {
745 (void) new BAB<HasSolutions>
746 (htc.htc(),htb1.htb(),htb2.htb(),htb3.htb(),
747 c_d,a_d,t);
748 }
749 (void) new BAB<FailImmediate>
750 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
751 (void) new BAB<SolveImmediate>
752 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
753 (void) new BAB<HasSolutions>
754 (HTC_NONE,HTB_NONE,HTB_NONE,HTB_NONE,c_d,a_d,t);
755 }
756 // Restart-based search
757 for (unsigned int t=1; t<=4; t++) {
758 (void) new RBS<HasSolutions,Gecode::DFS>("DFS",t);
759 (void) new RBS<HasSolutions,Gecode::LDS>("LDS",t);
760 (void) new RBS<HasSolutions,Gecode::BAB>("BAB",t);
761 (void) new RBS<FailImmediate,Gecode::DFS>("DFS",t);
762 (void) new RBS<FailImmediate,Gecode::LDS>("LDS",t);
763 (void) new RBS<FailImmediate,Gecode::BAB>("BAB",t);
764 (void) new RBS<SolveImmediate,Gecode::DFS>("DFS",t);
765 (void) new RBS<SolveImmediate,Gecode::LDS>("LDS",t);
766 (void) new RBS<SolveImmediate,Gecode::BAB>("BAB",t);
767 }
768 // Portfolio-based search
769 for (unsigned int a=1; a<=4; a++)
770 for (unsigned int t=1; t<=2*a; t++) {
771 (void) new PBS<HasSolutions,Gecode::DFS>("DFS",false,a,t);
772 (void) new PBS<HasSolutions,Gecode::LDS>("LDS",false,a,t);
773 (void) new PBS<HasSolutions,Gecode::BAB>("BAB",true,a,t);
774 (void) new PBS<FailImmediate,Gecode::DFS>("DFS",false,a,t);
775 (void) new PBS<FailImmediate,Gecode::LDS>("LDS",false,a,t);
776 (void) new PBS<FailImmediate,Gecode::BAB>("BAB",true,a,t);
777 (void) new PBS<SolveImmediate,Gecode::DFS>("DFS",false,a,t);
778 (void) new PBS<SolveImmediate,Gecode::LDS>("LDS",false,a,t);
779 (void) new PBS<SolveImmediate,Gecode::BAB>("BAB",true,a,t);
780 }
781 // Portfolio-based search using SEBs
782 for (unsigned int mt=1; mt<=3; mt += 2)
783 for (unsigned int st=1; st<=8; st++) {
784 (void) new SEBPBS<HasSolutions>("BAB",true,mt,st);
785 (void) new SEBPBS<FailImmediate>("BAB",true,mt,st);
786 (void) new SEBPBS<SolveImmediate>("BAB",true,mt,st);
787 (void) new SEBPBS<HasSolutions>("DFS+LDS",false,mt,st);
788 (void) new SEBPBS<FailImmediate>("DFS+LDS",false,mt,st);
789 (void) new SEBPBS<SolveImmediate>("DFS+LDS",false,mt,st);
790 }
791 }
792 };
793
794 Create c;
795 }
796
797}
798
799// STATISTICS: test-search