Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
search.cpp
Go to the documentation of this file.
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
42 namespace Search {
43
44 using namespace Gecode;
45 using namespace Gecode::Int;
46
54
63
70
72 class TestSpace : public Space {
73 public:
75 TestSpace(void) {}
79 virtual int solutions(void) const = 0;
81 virtual bool best(void) const = 0;
83 virtual bool master(const MetaInfo& mi) {
84 if (mi.type() == MetaInfo::RESTART) {
85 if (mi.last() != NULL)
86 constrain(*mi.last());
87 return false;
88 } else {
89 return false;
90 }
91 }
92 };
93
95 class FailImmediate : public TestSpace {
96 public:
102 : x(*this,1,0,0) {
103 rel(*this, x[0], IRT_EQ, 1);
104 }
107 x.update(*this, s.x);
108 }
110 virtual Space* copy(void) {
111 return new FailImmediate(*this);
112 }
114 virtual void constrain(const Space&) {
115 }
117 virtual int solutions(void) const {
118 return 0;
119 }
121 virtual bool best(void) const {
122 return false;
123 }
125 static std::string name(void) {
126 return "Fail";
127 }
128 };
129
131 class SolveImmediate : public TestSpace {
132 public:
141 x.update(*this, s.x);
142 }
144 virtual Space* copy(void) {
145 return new SolveImmediate(*this);
146 }
148 virtual void constrain(const Space&) {
149 fail();
150 }
152 virtual int solutions(void) const {
153 return 1;
154 }
156 virtual bool best(void) const {
157 return true;
158 }
160 static std::string name(void) {
161 return "Solve";
162 }
163 };
164
166 class HasSolutions : public TestSpace {
167 public:
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:
184 break;
185 case HTB_NARY:
187 break;
188 }
189 }
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 }
203 : TestSpace(s),
204 htb1(s.htb1), htb2(s.htb2), htb3(s.htb3), htc(s.htc) {
205 x.update(*this, s.x);
206 }
208 virtual Space* copy(void) {
209 return new HasSolutions(*this);
210 }
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 }
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 }
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 }
285 static std::string name(void) {
286 return "Sol";
287 }
289 virtual bool master(const MetaInfo& mi) {
290 switch (mi.type()) {
292 if (mi.last() != NULL) {
293 const HasSolutions* s
294 = static_cast<const HasSolutions*>(mi.last());
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;
302 // Do not kill the brancher!
303 break;
304 default:
305 break;
306 }
307 return false;
308 }
309 };
310
312 class Test : public Base {
313 public:
315 HowToBranch htb1, htb2, htb3;
319 static std::string str(unsigned int i) {
320 std::stringstream s;
321 s << i;
322 return s.str();
323 }
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 }
334 return "";
335 }
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 }
347 return "";
348 }
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
358 template<class Model>
359 class DFS : public Test {
360 private:
362 unsigned int c_d;
364 unsigned int a_d;
366 unsigned int t;
367 public:
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) {}
376 virtual bool run(void) {
377 Model* m = new Model(htb1,htb2,htb3);
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 != NULL) {
390 n--; delete s;
391 }
392 if ((s == NULL) && !dfs.stopped())
393 break;
394 f.limit(f.limit()+2);
395 }
396 return n == 0;
397 }
398 };
399
401 template<class Model>
402 class LDS : public Test {
403 private:
405 unsigned int t;
406 public:
409 unsigned int t0)
410 : Test("LDS::"+Model::name()+"::"+
411 str(htb1)+"::"+str(htb2)+"::"+str(htb3)+"::"+str(t0),
412 htb1,htb2,htb3), t(t0) {}
414 virtual bool run(void) {
415 Model* m = new Model(htb1,htb2,htb3);
418 o.threads = t;
419 o.d_l = 50;
420 o.stop = &f;
422 int n = m->solutions();
423 delete m;
424 while (true) {
425 Model* s = lds.next();
426 if (s != NULL) {
427 n--; delete s;
428 }
429 if ((s == NULL) && !lds.stopped())
430 break;
431 f.limit(f.limit()+2);
432 }
433 return n == 0;
434 }
435 };
436
438 template<class Model>
439 class BAB : public Test {
440 private:
442 unsigned int c_d;
444 unsigned int a_d;
446 unsigned int t;
447 public:
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) {}
457 virtual bool run(void) {
458 Model* m = new Model(htb1,htb2,htb3,htc);
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 = NULL;
468 while (true) {
469 Model* s = bab.next();
470 if (s != NULL) {
471 delete b; b=s;
472 }
473 if ((s == NULL) && !bab.stopped())
474 break;
475 f.limit(f.limit()+2);
476 }
477 bool ok = (b == NULL) || b->best();
478 delete b;
479 return ok;
480 }
481 };
482
484 template<class Model, template<class> class Engine>
485 class RBS : public Test {
486 private:
488 unsigned int t;
489 public:
491 RBS(const std::string& e, unsigned int t0)
492 : Test("RBS::"+e+"::"+Model::name()+"::"+str(t0),
495 virtual bool run(void) {
496 Model* m = new Model(htb1,htb2,htb3);
499 o.threads = t;
500 o.stop = &f;
501 o.d_l = 100;
504 int n = m->solutions();
505 delete m;
506 while (true) {
507 Model* s = rbs.next();
508 if (s != NULL) {
509 n--; delete s;
510 }
511 if ((s == NULL) && !rbs.stopped())
512 break;
513 f.limit(f.limit()+2);
514 }
515 return n == 0;
516 }
517 };
518
520 template<class Model, template<class> class Engine>
521 class PBS : public Test {
522 private:
524 bool best;
526 unsigned int a;
528 unsigned int t;
529 public:
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) {}
535 virtual bool run(void) {
536 Model* m = new Model(htb1,htb2,htb3);
539 o.assets = a;
540 o.threads = t;
541 o.d_l = 100;
542 o.stop = &f;
544 if (best) {
545 Model* b = NULL;
546 while (true) {
547 Model* s = pbs.next();
548 if (s != NULL) {
549 delete b; b=s;
550 }
551 if ((s == NULL) && !pbs.stopped())
552 break;
553 f.limit(f.limit()+2);
554 }
555 bool ok = (b == NULL) || 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 != NULL) {
564 n--; delete s;
565 }
566 if ((s == NULL) && !pbs.stopped())
567 break;
568 f.limit(f.limit()+2);
569 }
570 return n >= 0;
571 }
572 }
573 };
574
576 template<class Model>
577 class SEBPBS : public Test {
578 private:
580 bool best;
582 unsigned int mt;
584 unsigned int st;
585 public:
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) {}
591 virtual bool run(void) {
592 using namespace Gecode;
593 Model* m = new Model(htb1,htb2,htb3);
595
597 mo.threads = mt;
598 mo.d_l = 100;
599 mo.stop = &f;
600
602 so.threads = st;
603 so.d_l = 100;
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);
611 delete m;
612
613 Model* b = NULL;
614 while (true) {
615 Model* s = pbs.next();
616 if (s != NULL) {
617 delete b; b=s;
618 }
619 if ((s == NULL) && !pbs.stopped())
620 break;
621 f.limit(f.limit()+2);
622 }
623 bool ok = (b == NULL) || 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);
632
633 int n = 3 * m->solutions();
634 delete m;
635
636 while (true) {
637 Model* s = pbs.next();
638 if (s != NULL) {
639 n--; delete s;
640 }
641 if ((s == NULL) && !pbs.stopped())
642 break;
643 f.limit(f.limit()+2);
644 }
645 return n >= 0;
646 }
647 }
648 };
649
652 private:
654 static const HowToBranch htbs[3];
656 int i;
657 public:
659 BranchTypes(void) : i(0) {}
661 bool operator()(void) const {
662 return i<3;
663 }
665 void operator++(void) {
666 i++;
667 }
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
678 private:
680 static const HowToConstrain htcs[4];
682 int i;
683 public:
685 ConstrainTypes(void) : i(0) {}
687 bool operator()(void) const {
688 return i<4;
689 }
691 void operator++(void) {
692 i++;
693 }
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
705 class Create {
706 public:
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);
719 c_d, a_d, t);
721 c_d, a_d, t);
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);
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>
751 (void) new BAB<SolveImmediate>
753 (void) new BAB<HasSolutions>
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
795 }
796
797}
798
799// STATISTICS: test-search
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Depth-first branch-and-bound search engine.
Definition search.hh:1070
Passing Boolean variables.
Definition int.hh:712
Depth-first search engine.
Definition search.hh:1036
Passing integer variables.
Definition int.hh:656
Integer variable array.
Definition int.hh:763
Integer variables.
Definition int.hh:371
Limited discrepancy search engine.
Definition search.hh:1108
Information passed by meta search engines.
Definition core.hpp:1613
@ PORTFOLIO
Information is provided by a portfolio-based engine.
Definition core.hpp:1620
@ RESTART
Information is provided by a restart-based engine.
Definition core.hpp:1618
const Space * last(void) const
Return last solution found (possibly NULL)
Definition core.hpp:3101
Type type(void) const
Return type of information.
Definition core.hpp:3082
Meta engine using a portfolio of search engines.
Definition search.hh:1236
Meta-engine performing restart-based search.
Definition search.hh:1152
Passing search engine builder arguments.
Definition search.hh:1002
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
Definition cutoff.cpp:160
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition cutoff.cpp:148
Stop-object based on number of failures
Definition search.hh:852
Search engine options
Definition search.hh:746
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition search.hh:753
unsigned int d_l
Discrepancy limit (for LDS)
Definition search.hh:757
Cutoff * cutoff
Cutoff for restart-based search.
Definition search.hh:767
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition search.hh:755
Stop * stop
Stop object for stopping search.
Definition search.hh:765
unsigned int assets
Number of assets (engines) in a portfolio.
Definition search.hh:759
double threads
Number of threads to use.
Definition search.hh:751
Computation spaces.
Definition core.hpp:1742
int size(void) const
Return size of array (number of elements)
Definition array.hpp:926
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1013
Base class for all tests to be run
Definition test.hh:103
BAB(HowToConstrain htc, HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition search.cpp:449
virtual bool run(void)
Run test.
Definition search.cpp:457
Iterator for branching types.
Definition search.cpp:651
HowToBranch htb(void) const
Return current branching type.
Definition search.cpp:669
BranchTypes(void)
Initialize iterator.
Definition search.cpp:659
void operator++(void)
Increment to next branching type.
Definition search.cpp:665
bool operator()(void) const
Test whether iterator is done.
Definition search.cpp:661
Iterator for constrain types.
Definition search.cpp:677
HowToConstrain htc(void) const
Return current constrain type.
Definition search.cpp:695
void operator++(void)
Increment to next constrain type.
Definition search.cpp:691
bool operator()(void) const
Test whether iterator is done.
Definition search.cpp:687
ConstrainTypes(void)
Initialize iterator.
Definition search.cpp:685
Help class to create and register tests.
Definition search.cpp:705
Create(void)
Perform creation and registration.
Definition search.cpp:708
virtual bool run(void)
Run test.
Definition search.cpp:376
DFS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int c_d0, unsigned int a_d0, unsigned int t0)
Initialize test.
Definition search.cpp:369
Space that immediately fails.
Definition search.cpp:95
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:121
IntVarArray x
Variables used.
Definition search.cpp:98
FailImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition search.cpp:100
FailImmediate(FailImmediate &s)
Constructor for cloning s.
Definition search.cpp:106
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:110
static std::string name(void)
Return name.
Definition search.cpp:125
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:117
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition search.cpp:114
Space that requires propagation and has solutions.
Definition search.cpp:166
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:245
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:208
static std::string name(void)
Return name.
Definition search.cpp:285
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:257
virtual void constrain(const Space &_s)
Add constraint for next better solution.
Definition search.cpp:212
virtual bool master(const MetaInfo &mi)
Rule out that solution is found more than once during restarts.
Definition search.cpp:289
HowToConstrain htc
How to constrain.
Definition search.cpp:173
HasSolutions(HasSolutions &s)
Constructor for cloning s.
Definition search.cpp:202
IntVarArray x
Variables used.
Definition search.cpp:169
HowToBranch htb1
How to branch.
Definition search.cpp:171
HasSolutions(HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Constructor for space creation.
Definition search.cpp:191
void branch(const IntVarArgs &x, HowToBranch htb)
Branch on x according to htb.
Definition search.cpp:175
virtual bool run(void)
Run test.
Definition search.cpp:414
LDS(HowToBranch htb1, HowToBranch htb2, HowToBranch htb3, unsigned int t0)
Initialize test.
Definition search.cpp:408
PBS(const std::string &e, bool b, unsigned int a0, unsigned int t0)
Initialize test.
Definition search.cpp:531
virtual bool run(void)
Run test.
Definition search.cpp:535
RBS(const std::string &e, unsigned int t0)
Initialize test.
Definition search.cpp:491
virtual bool run(void)
Run test.
Definition search.cpp:495
Test for portfolio-based search using SEBs
Definition search.cpp:577
SEBPBS(const std::string &e, bool b, unsigned int mt0, unsigned int st0)
Initialize test.
Definition search.cpp:587
virtual bool run(void)
Run test.
Definition search.cpp:591
Space that is immediately solved.
Definition search.cpp:131
virtual int solutions(void) const
Return number of solutions.
Definition search.cpp:152
IntVarArray x
Variables used.
Definition search.cpp:134
virtual bool best(void) const
Verify that this is best solution.
Definition search.cpp:156
virtual Space * copy(void)
Copy during cloning.
Definition search.cpp:144
static std::string name(void)
Return name.
Definition search.cpp:160
SolveImmediate(SolveImmediate &s)
Constructor for cloning s.
Definition search.cpp:140
SolveImmediate(HowToBranch, HowToBranch, HowToBranch, HowToConstrain=HTC_NONE)
Constructor for space creation.
Definition search.cpp:136
virtual void constrain(const Space &)
Add constraint for next better solution.
Definition search.cpp:148
Space with information.
Definition search.cpp:72
virtual int solutions(void) const =0
Return number of solutions.
virtual bool master(const MetaInfo &mi)
Master configuration function that does not restart.
Definition search.cpp:83
TestSpace(void)
Constructor for space creation.
Definition search.cpp:75
TestSpace(TestSpace &s)
Constructor for cloning s.
Definition search.cpp:77
virtual bool best(void) const =0
Verify that this is best solution.
static std::string str(unsigned int i)
Map unsigned integer to string.
Definition search.cpp:319
Test(const std::string &s, HowToBranch _htb1, HowToBranch _htb2, HowToBranch _htb3, HowToConstrain _htc=HTC_NONE)
Initialize test.
Definition search.cpp:350
HowToConstrain htc
How to constrain.
Definition search.cpp:317
static std::string str(HowToBranch htb)
Map branching to string.
Definition search.cpp:325
HowToBranch htb1
How to branch.
Definition search.cpp:315
static std::string str(HowToConstrain htc)
Map constrain to string.
Definition search.cpp:337
void fail(void)
Fail space.
Definition core.hpp:4030
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( )
Definition int.hh:926
@ IRT_LE
Less ( )
Definition int.hh:929
@ IRT_GR
Greater ( )
Definition int.hh:931
@ IRT_LQ
Less or equal ( )
Definition int.hh:928
@ BOT_AND
Conjunction.
Definition int.hh:951
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
T * pbs(T *s, const Search::Options &o=Search::Options::def)
Run a portfolio of search engines.
Definition pbs.hpp:309
T * lds(T *s, const Search::Options &o=Search::Options::def)
Invoke limited-discrepancy search for s as root node and optionso.
Definition lds.hpp:74
T * rbs(T *s, const Search::Options &o)
Perform restart-based search.
Definition rbs.hpp:111
Finite domain integers.
Gecode toplevel namespace
void lex(Home home, const IntVarArgs &x, IntRelType r, const IntVarArgs &y, IntPropLevel ipl=IPL_DEF)
Post lexical order between x and y.
Definition aliases.hpp:132
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
IntValBranch INT_VALUES_MIN(void)
Try all values starting from smallest.
Definition val.hpp:100
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition assign.hpp:55
HowToBranch
Values for selecting branchers.
Definition search.cpp:48
@ HTB_BINARY
Branch with two alternatives.
Definition search.cpp:51
@ HTB_NONE
Do not branch.
Definition search.cpp:49
@ HTB_UNARY
Branch with single alternative.
Definition search.cpp:50
@ HTB_NARY
Branch with many alternatives.
Definition search.cpp:52
HowToConstrain
Values for selecting how to constrain.
Definition search.cpp:56
@ HTC_BAL_GR
Constrain for largest balance.
Definition search.cpp:61
@ HTC_LEX_LE
Constrain for lexically smallest.
Definition search.cpp:58
@ HTC_LEX_GR
Constrain for lexically biggest.
Definition search.cpp:59
@ HTC_BAL_LE
Constrain for smallest balance.
Definition search.cpp:60
@ HTC_NONE
Do not constrain.
Definition search.cpp:57
WhichModel
Values for selecting models.
Definition search.cpp:65
@ WM_FAIL_SEARCH
Model without solutions.
Definition search.cpp:67
@ WM_SOLUTIONS
Model with solutions.
Definition search.cpp:68
@ WM_FAIL_IMMEDIATE
Model that fails immediately.
Definition search.cpp:66
General test support.
Definition afc.cpp:39
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56