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 * Guido Tack <tack@gecode.org>
6 *
7 * Contributing authors:
8 * Kevin Leo <kevin.leo@monash.edu>
9 * Maxim Shishmarev <maxim.shishmarev@monash.edu>
10 *
11 * Copyright:
12 * Kevin Leo, 2017
13 * Christian Schulte, 2002
14 * Maxim Shishmarev, 2017
15 * Guido Tack, 2004
16 *
17 * This file is part of Gecode, the generic constraint
18 * development environment:
19 * http://www.gecode.org
20 *
21 * Permission is hereby granted, free of charge, to any person obtaining
22 * a copy of this software and associated documentation files (the
23 * "Software"), to deal in the Software without restriction, including
24 * without limitation the rights to use, copy, modify, merge, publish,
25 * distribute, sublicense, and/or sell copies of the Software, and to
26 * permit persons to whom the Software is furnished to do so, subject to
27 * the following conditions:
28 *
29 * The above copyright notice and this permission notice shall be
30 * included in all copies or substantial portions of the Software.
31 *
32 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39 *
40 */
41
42#ifndef GECODE_SEARCH_HH
43#define GECODE_SEARCH_HH
44
45#include <initializer_list>
46
47#include <gecode/kernel.hh>
48
49/*
50 * Configure linking
51 *
52 */
53#if !defined(GECODE_STATIC_LIBS) && \
54 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
55
56#ifdef GECODE_BUILD_SEARCH
57#define GECODE_SEARCH_EXPORT __declspec( dllexport )
58#else
59#define GECODE_SEARCH_EXPORT __declspec( dllimport )
60#endif
61
62#else
63
64#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
65#define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
66#else
67#define GECODE_SEARCH_EXPORT
68#endif
69
70#endif
71
72// Configure auto-linking
73#ifndef GECODE_BUILD_SEARCH
74#define GECODE_LIBRARY_NAME "Search"
75#include <gecode/support/auto-link.hpp>
76#endif
77
78
79namespace Gecode { namespace Search {
80
81 /// %Sequential search engine implementations
82 namespace Sequential {}
83
84 /// %Parallel search engine implementations
85 namespace Parallel {}
86
87 /// %Meta search engine implementations
88 namespace Meta {}
89
90 namespace Meta {
91
92 /// %Sequential meta search engine implementations
93 namespace Sequential {}
94
95 /// %Parallel meta search engine implementations
96 namespace Parallel {}
97
98 }
99
100
101 /**
102 * \brief %Search configuration
103 *
104 * \ingroup TaskModelSearch
105 */
106 namespace Config {
107 /// Whether engines create a clone when being initialized
108 const bool clone = true;
109 /// Number of threads to use
110 const double threads = 1.0;
111
112 /// Create a clone after every \a c_d commits (commit distance)
113 const unsigned int c_d = 8;
114 /// Create a clone during recomputation if distance is greater than \a a_d (adaptive distance)
115 const unsigned int a_d = 2;
116
117 /// Minimal number of open nodes for stealing
118 const unsigned int steal_limit = 3;
119 /// Initial delay in milliseconds for all but first worker thread
120 const unsigned int initial_delay = 5;
121
122 /// Default discrepancy limit for LDS
123 const unsigned int d_l = 5;
124
125 /// Base for geometric restart sequence
126 const double base = 1.5;
127 /// Size of a slice in a portfolio and scale factor for restarts(in number of failures)
128 const unsigned int slice = 250;
129
130 /// Depth limit for no-good generation during search
131 const unsigned int nogoods_limit = 128;
132
133 /// Default port for CPProfiler
134 const unsigned int cpprofiler_port = 6565U;
135 }
136
137}}
138
139#include <gecode/search/exception.hpp>
140
141namespace Gecode { namespace Search {
142
143 /**
144 * \brief %Search engine statistics
145 * \ingroup TaskModelSearch
146 */
147 class Statistics : public StatusStatistics {
148 public:
149 /// Number of failed nodes in search tree
150 unsigned long long int fail;
151 /// Number of nodes expanded
152 unsigned long long int node;
153 /// Maximum depth of search stack
154 unsigned long int depth;
155 /// Number of restarts
156 unsigned long int restart;
157 /// Number of no-goods posted
158 unsigned long int nogood;
159 /// Initialize
160 Statistics(void);
161 /// Reset
162 void reset(void);
163 /// Return sum with \a s
164 Statistics operator +(const Statistics& s);
165 /// Increment by statistics \a s
166 Statistics& operator +=(const Statistics& s);
167 };
168
169}}
170
171#include <gecode/search/statistics.hpp>
172
173namespace Gecode { namespace Search {
174
175 class WrapTraceRecorder;
176 class TraceRecorder;
177 class EdgeTraceRecorder;
178
179}}
180
181#include <string>
182#include <sstream>
183
184namespace Gecode {
185
186 /// Support for tracing search
187 class SearchTracer {
188 friend class Search::WrapTraceRecorder;
189 friend class Search::TraceRecorder;
190 friend class Search::EdgeTraceRecorder;
191 public:
192 /// Which type of engine
193 enum EngineType {
194 DFS = 0, ///< Engine is a DFS engine
195 BAB = 1, ///< Engine is a BAB engine
196 LDS = 2, ///< Engine is a LDS engine
197 RBS = 3, ///< Engine is a RBS engine
198 PBS = 4, ///< Engine is a PBS engine
199 AOE = 5 ///< Unspecified engine (any other engine)
200 };
201 /// Information about an engine
202 class EngineInfo {
203 protected:
204 /// The engine type
205 EngineType _type;
206 /// First worker or engine
207 unsigned int _fst;
208 /// Last worker or engine
209 unsigned int _lst;
210 public:
211 /// Do not initialize
212 EngineInfo(void);
213 /// Initialize
214 EngineInfo(EngineType et, unsigned int fst, unsigned int lst);
215 /// \name Engine type information
216 //@{
217 /// Return engine type
218 EngineType type(void) const;
219 /// Return whether engine is a meta engine
220 bool meta(void) const;
221 //@}
222 /// \name Information for basic (non-meta) engines
223 //@{
224 /// Return id of first worker
225 unsigned int wfst(void) const;
226 /// Return id of last worker plus one
227 unsigned int wlst(void) const;
228 /// Return number of workers
229 unsigned int workers(void) const;
230 //@}
231 /// \name Information for meta engines
232 //@{
233 /// Return id of first engine
234 unsigned int efst(void) const;
235 /// Return id of last engine
236 unsigned int elst(void) const;
237 /// Return number of engines
238 unsigned int engines(void) const;
239 //@}
240 };
241 /// Edge information
242 class EdgeInfo {
243 protected:
244 /// The parent worker id (edge does not exist if UINT_MAX)
245 unsigned int _wid;
246 /// The parent node id
247 unsigned int _nid;
248 /// Number of alternative
249 unsigned int _a;
250 /// String corresponding to alternative
251 std::string _s;
252 public:
253 /// Initialize
254 void init(unsigned int wid, unsigned int nid, unsigned int a);
255 /// Initialize
256 void init(unsigned int wid, unsigned int nid, unsigned int a,
257 const Space& s, const Choice & c);
258 /// Invalidate edge information (for stealing)
259 void invalidate(void);
260 /// Initialize as non existing
261 EdgeInfo(void);
262 /// Initialize
263 EdgeInfo(unsigned int wid, unsigned int nid, unsigned int a);
264 /// Test whether edge actually exists
265 operator bool(void) const;
266 /// Return parent worker id
267 unsigned int wid(void) const;
268 /// Return parent node id
269 unsigned int nid(void) const;
270 /// Return number of alternative
271 unsigned int alternative(void) const;
272 /// Return string for alternative
273 std::string string(void) const;
274 };
275 /// Node type
276 enum NodeType {
277 SOLVED = 0, /// A solution node
278 FAILED = 1, /// A failed node
279 BRANCH = 2 /// A branch node
280 };
281 /// Node information
282 class NodeInfo {
283 protected:
284 /// The node type
285 NodeType _nt;
286 /// The worker id
287 unsigned int _wid;
288 /// The node id
289 unsigned int _nid;
290 /// The corresponding space
291 const Space& _s;
292 /// The corresponding choice (nullptr if type is not BRANCH)
293 const Choice* _c;
294 public:
295 /// Initialize node info
296 NodeInfo(NodeType nt,
297 unsigned int wid, unsigned int nid,
298 const Space& s, const Choice* c = nullptr);
299 /// Return node type
300 NodeType type(void) const;
301 /// Return worker id
302 unsigned int wid(void) const;
303 /// Return node id
304 unsigned int nid(void) const;
305 /// Return corresponding space
306 const Space& space(void) const;
307 /// Return corresponding choice
308 const Choice& choice(void) const;
309 };
310 private:
311 /// Mutex for serialized access
312 Support::Mutex m;
313 /// Number of pending engine and workers calls
314 unsigned int pending;
315 /// Number of engines
316 unsigned int n_e;
317 /// Number of workers
318 unsigned int n_w;
319 /// Number of active workers (for termination)
320 unsigned int n_active;
321 /// The engines
322 Support::DynamicArray<EngineInfo,Heap> es;
323 /// Mapping of workers to engines
324 Support::DynamicArray<unsigned int,Heap> w2e;
325 /// Register new engine
326 void engine(EngineType t, unsigned int n);
327 /// Register new worker
328 void worker(unsigned int& wid, unsigned int& eid);
329 /// Deregister a worker
330 void worker(void);
331 /// \name Unsynchronized internal calls
332 //{@
333 /// The engine with id \a eid goes to a next round (restart or next iteration in LDS)
334 void _round(unsigned int eid);
335 /// The engine skips an edge
336 void _skip(const EdgeInfo& ei);
337 /// The engine creates a new node with information \a ei and \a ni
338 void _node(const EdgeInfo& ei, const NodeInfo& ni);
339 //@}
340 public:
341 /// Initialize
342 SearchTracer(void);
343 /// \name Engine information
344 //@{
345 /// Return number of workers
346 unsigned int workers(void) const;
347 /// Return number of engines
348 unsigned int engines(void) const;
349 /// Provide access to engine with id \a eid
350 const EngineInfo& engine(unsigned int eid) const;
351 /// Return the engine id of a worker with id \a wid
352 unsigned int eid(unsigned int wid) const;
353 //@}
354 /// \name Trace event functions
355 //@{
356 /// The search engine initializes
357 virtual void init(void) = 0;
358 /// The engine with id \a eid goes to a next round (restart or next iteration in LDS)
359 virtual void round(unsigned int eid) = 0;
360 /// The engine skips an edge
361 virtual void skip(const EdgeInfo& ei) = 0;
362 /// The engine creates a new node with information \a ei and \a ni
363 virtual void node(const EdgeInfo& ei, const NodeInfo& ni) = 0;
364 /// All workers are done
365 virtual void done(void) = 0;
366 //@}
367 /// Delete
368 virtual ~SearchTracer(void);
369 };
370
371 class GECODE_SEARCH_EXPORT StdSearchTracer : public SearchTracer {
372 protected:
373 /// Output stream to use
374 std::ostream& os;
375 /// Map engine type to string
376 static const char* t2s[EngineType::AOE + 1];
377 public:
378 /// Initialize with output stream \a os
379 StdSearchTracer(std::ostream& os = std::cerr);
380 /// The search engine initializes
381 virtual void init(void);
382 /// The engine with id \a eid goes to a next round (restart or next iteration in LDS)
383 virtual void round(unsigned int eid);
384 /// The engine skips an edge
385 virtual void skip(const EdgeInfo& ei);
386 /// The engine creates a new node with information \a ei and \a ni
387 virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
388 /// All workers are done
389 virtual void done(void);
390 /// Delete
391 virtual ~StdSearchTracer(void);
392 /// Default tracer (printing to std::cerr)
393 static StdSearchTracer def;
394 };
395
396}
397
398#include <gecode/search/tracer.hpp>
399#include <gecode/search/trace-recorder.hpp>
400
401#ifdef GECODE_HAS_CPPROFILER
402
403namespace Gecode {
404
405 /// Code that is specific to the CPProfiler
406 namespace CPProfiler {}
407
408}
409
410namespace Gecode { namespace CPProfiler {
411
412 /// The actual connector to the CPProfiler
413 class Connector;
414
415}}
416
417namespace Gecode {
418
419 /// Class to record search trace info for CPProfiler
420 class GECODE_SEARCH_EXPORT CPProfilerSearchTracer : public SearchTracer {
421 public:
422 /// Class to send solution information to CPProfiler
423 class GECODE_SEARCH_EXPORT GetInfo : public HeapAllocated {
424 public:
425 /// Initialize
426 GetInfo(void);
427 /// Return info for a space
428 virtual std::string getInfo(const Space& home) const = 0;
429 /// Delete
430 virtual ~GetInfo(void);
431 };
432 private:
433 /// Connector to connect to running instnace of CPProfiler
434 CPProfiler::Connector* connector;
435 /// Execution id to be displayed by CPProfiler
436 int execution_id;
437 /// Name of script being traced
438 std::string name;
439 /// Number of the current restart
440 int restart;
441 /// Send solution information to CPProfiler
442 const GetInfo* pgi;
443 public:
444 /// Initialize
445 CPProfilerSearchTracer(int eid, std::string name,
446 unsigned int port = Search::Config::cpprofiler_port,
447 const GetInfo* pgi = nullptr);
448 /// The search engine initializes
449 virtual void init(void);
450 /// The engine with id \a eid goes to a next round (restart or next iteration in LDS)
451 virtual void round(unsigned int eid);
452 /// The engine skips an edge
453 virtual void skip(const EdgeInfo& ei);
454 /// The engine creates a new node with information \a ei and \a ni
455 virtual void node(const EdgeInfo& ei, const NodeInfo& ni);
456 /// All workers are done
457 virtual void done(void);
458 /// Delete
459 virtual ~CPProfilerSearchTracer(void);
460 };
461
462}
463
464#endif
465
466namespace Gecode { namespace Search {
467
468 /**
469 * \brief Base class for cutoff generators for restart-based meta engine
470 * \ingroup TaskModelSearch
471 */
472 class GECODE_SEARCH_EXPORT Cutoff : public HeapAllocated {
473 public:
474 /// \name Constructors and member functions
475 //@{
476 /// Default constructor
477 Cutoff(void);
478 /// Return the current cutoff value
479 virtual unsigned long long int operator ()(void) const = 0;
480 /// Increment and return the next cutoff value
481 virtual unsigned long long int operator ++(void) = 0;
482 /// Destructor
483 virtual ~Cutoff(void);
484 //@}
485 /// \name Predefined cutoff generators
486 //@{
487 /// Create generator for constant sequence with constant \a s
488 static Cutoff*
489 constant(unsigned long long int scale=Config::slice);
490 /// Create generator for linear sequence scaled by \a scale
491 static Cutoff*
492 linear(unsigned long long int scale=Config::slice);
493 /** Create generator for geometric sequence scaled by
494 * \a scale using base \a base
495 */
496 static Cutoff*
497 geometric(unsigned long long int scale=Config::slice,
498 double base=Config::base);
499 /// Create generator for luby sequence with scale-factor \a scale
500 static Cutoff*
501 luby(unsigned long long int scale=Config::slice);
502 /** Create generator for random sequence with seed \a seed that
503 * generates values between \a min and \a max with \a n steps
504 * between the extreme values.
505 */
506 static Cutoff*
507 rnd(unsigned int seed,
508 unsigned long long int min, unsigned long long int max,
509 unsigned long long int n);
510 /// Append cutoff values from \a c2 after \a n values from \a c1
511 static Cutoff*
512 append(Cutoff* c1, unsigned long long int n, Cutoff* c2);
513 /// Merge cutoff values from \a c1 with values from \a c2
514 static Cutoff*
515 merge(Cutoff* c1, Cutoff* c2);
516 /// Create generator that repeats \a n times each cutoff value from \a c
517 static Cutoff*
518 repeat(Cutoff* c, unsigned long long int n);
519 //@}
520 };
521
522 /**
523 * \brief Cutoff generator for constant sequence
524 * \ingroup TaskModelSearch
525 */
526 class GECODE_SEARCH_EXPORT CutoffConstant : public Cutoff {
527 protected:
528 /// Constant
529 unsigned long long int c;
530 public:
531 /// Constructor
532 CutoffConstant(unsigned long long int c);
533 /// Return the current cutoff value
534 virtual unsigned long long int operator ()(void) const;
535 /// Increment and return the next cutoff value
536 virtual unsigned long long int operator ++(void);
537 };
538
539 /**
540 * \brief Cutoff generator for linear sequence
541 * \ingroup TaskModelSearch
542 */
543 class GECODE_SEARCH_EXPORT CutoffLinear : public Cutoff {
544 protected:
545 /// Scale factor
546 unsigned long long int scale;
547 /// Next number in sequence
548 unsigned long long int n;
549 public:
550 /// Constructor
551 CutoffLinear(unsigned long long int scale);
552 /// Return the current cutoff value
553 virtual unsigned long long int operator ()(void) const;
554 /// Increment and return the next cutoff value
555 virtual unsigned long long int operator ++(void);
556 };
557
558 /**
559 * \brief Cutoff generator for the Luby sequence
560 * \ingroup TaskModelSearch
561 */
562 class GECODE_SEARCH_EXPORT CutoffLuby : public Cutoff {
563 protected:
564 /// Iteration number
565 unsigned long long int i;
566 /// Scale factor
567 unsigned long long int scale;
568 /// Number of pre-computed luby values
569 static const unsigned long long int n_start = 63U;
570 /// Precomputed luby-values
571 static unsigned long int start[n_start];
572 /// Compute binary logarithm of \a i
573 static unsigned long long int log(unsigned long long int i);
574 /// Compute Luby number for step \a i
575 static unsigned long long int luby(unsigned long long int i);
576 public:
577 /// Constructor
578 CutoffLuby(unsigned long long int scale);
579 /// Return the current cutoff value
580 virtual unsigned long long int operator ()(void) const;
581 /// Increment and return the next cutoff value
582 virtual unsigned long long int operator ++(void);
583 };
584
585 /**
586 * \brief Cutoff generator for the geometric sequence
587 * \ingroup TaskModelSearch
588 */
589 class GECODE_SEARCH_EXPORT CutoffGeometric : public Cutoff {
590 protected:
591 /// Current cutoff value
592 double n;
593 /// Scale factor
594 double scale;
595 /// Base
596 double base;
597 public:
598 /// Constructor
599 CutoffGeometric(unsigned long long int scale, double base);
600 /// Return the current cutoff value
601 virtual unsigned long long int operator ()(void) const;
602 /// Increment and return the next cutoff value
603 virtual unsigned long long int operator ++(void);
604 };
605
606 /**
607 * \brief Cutoff generator for the random sequence
608 * \ingroup TaskModelSearch
609 */
610 class GECODE_SEARCH_EXPORT CutoffRandom : public Cutoff {
611 protected:
612 /// Random number generator
613 Support::RandomGenerator rnd;
614 /// Minimum cutoff value
615 unsigned long long int min;
616 /// Random values
617 unsigned long long int n;
618 /// Step size
619 unsigned long long int step;
620 /// Current value
621 unsigned long long int cur;
622 public:
623 /// Constructor
624 CutoffRandom(unsigned int seed,
625 unsigned long long int min, unsigned long long int max,
626 unsigned long long int n);
627 /// Return the current cutoff value
628 virtual unsigned long long int operator ()(void) const;
629 /// Increment and return the next cutoff value
630 virtual unsigned long long int operator ++(void);
631 };
632
633 /**
634 * \brief Cutoff generator appending two cutoff generators
635 * \ingroup TaskModelSearch
636 */
637 class GECODE_SEARCH_EXPORT CutoffAppend : public Cutoff {
638 protected:
639 /// First cutoff generators
640 Cutoff* c1;
641 /// Second cutoff generators
642 Cutoff* c2;
643 /// How many number to take from the first
644 unsigned long long int n;
645 public:
646 /// Constructor
647 CutoffAppend(Cutoff* c1, unsigned long long int n, Cutoff* c2);
648 /// Return the current cutoff value
649 virtual unsigned long long int operator ()(void) const;
650 /// Increment and return the next cutoff value
651 virtual unsigned long long int operator ++(void);
652 /// Destructor
653 virtual ~CutoffAppend(void);
654 };
655
656 /**
657 * \brief Cutoff generator merging two cutoff generators
658 * \ingroup TaskModelSearch
659 */
660 class GECODE_SEARCH_EXPORT CutoffMerge : public Cutoff {
661 protected:
662 /// First cutoff generator
663 Cutoff* c1;
664 /// Second cutoff generator
665 Cutoff* c2;
666 public:
667 /// Constructor
668 CutoffMerge(Cutoff* c1, Cutoff* c2);
669 /// Return the current cutoff value
670 virtual unsigned long long int operator ()(void) const;
671 /// Increment and return the next cutoff value
672 virtual unsigned long long int operator ++(void);
673 /// Destructor
674 virtual ~CutoffMerge(void);
675 };
676
677 /**
678 * \brief Cutoff generator that repeats a cutoff from another cutoff generator
679 * \ingroup TaskModelSearch
680 */
681 class GECODE_SEARCH_EXPORT CutoffRepeat : public Cutoff {
682 protected:
683 /// Actual cutoff generator
684 Cutoff* c;
685 // Current cutoff
686 unsigned long long int cutoff;
687 // Iteration
688 unsigned long long int i;
689 // Number of repetitions
690 unsigned long long int n;
691 public:
692 /// Constructor
693 CutoffRepeat(Cutoff* c, unsigned long long int n);
694 /// Return the current cutoff value
695 virtual unsigned long long int operator ()(void) const;
696 /// Increment and return the next cutoff value
697 virtual unsigned long long int operator ++(void);
698 /// Destructor
699 virtual ~CutoffRepeat(void);
700 };
701
702}}
703
704#include <gecode/search/cutoff.hpp>
705
706namespace Gecode { namespace Search {
707
708 class Stop;
709
710 /**
711 * \brief %Search engine options
712 *
713 * Defines options for search engines. Not all search engines might
714 * honor all option values.
715 *
716 * - \a c_d as minimal recomputation distance: this guarantees that
717 * a path between two nodes in the search tree for which copies are
718 * stored has at least length \a c_d. That is, in order to recompute
719 * a node in the search tree, \a c_d recomputation steps are needed.
720 * The minimal recomputation distance yields a guarantee on saving
721 * memory compared to full copying: it stores \a c_d times less nodes
722 * than full copying.
723 * - \a a_d as adaptive recomputation distance: when a node needs to be
724 * recomputed and the path is longer than \a a_d, an intermediate copy
725 * is created (approximately in the middle of the path) to speed up
726 * future recomputation. Note that small values of \a a_d can increase
727 * the memory consumption considerably.
728 *
729 * Full copying corresponds to a maximal recomputation distance
730 * \a c_d of 1.
731 *
732 * All recomputation performed is based on batch recomputation: batch
733 * recomputation performs propagation only once for an entire path
734 * used in recomputation.
735 *
736 * The number of threads to be used is controlled by a double \f$n\f$
737 * (assume that \f$m\f$ is the number of processing units available). If
738 * \f$1 \leq n\f$, \f$n\f$ threads are chosen (of course with rounding).
739 * If \f$n \leq -1\f$, then \f$m + n\f$ threads are
740 * chosen (all but \f$-n\f$ processing units get a thread). If \f$n\f$
741 * is zero, \f$m\f$ threads are chosen. If \f$0<n<1\f$,
742 * \f$n \times m\f$ threads are chosen. If \f$-1 <n<0\f$,
743 * \f$(1+n)\times m\f$ threads are chosen.
744 *
745 * \ingroup TaskModelSearch
746 */
747 class Options {
748 public:
749 /// Whether engines create a clone when being initialized
750 bool clone;
751 /// Number of threads to use
752 double threads;
753 /// Create a clone after every \a c_d commits (commit distance)
754 unsigned int c_d;
755 /// Create a clone during recomputation if distance is greater than \a a_d (adaptive distance)
756 unsigned int a_d;
757 /// Discrepancy limit (for LDS)
758 unsigned int d_l;
759 /// Number of assets (engines) in a portfolio
760 unsigned int assets;
761 /// Size of a slice in a portfolio (in number of failures)
762 unsigned int slice;
763 /// Depth limit for extraction of no-goods
764 unsigned int nogoods_limit;
765 /// Stop object for stopping search
766 Stop* stop;
767 /// Cutoff for restart-based search
768 Cutoff* cutoff;
769 /// Tracer object for tracing search
770 SearchTracer* tracer;
771 /// Default options
772 GECODE_SEARCH_EXPORT static const Options def;
773 /// Initialize with default values
774 Options(void);
775 /// Expand with real number of threads
776 GECODE_SEARCH_EXPORT Options
777 expand(void) const;
778 };
779
780}}
781
782#include <gecode/search/options.hpp>
783
784namespace Gecode { namespace Search {
785
786 /**
787 * \defgroup TaskModelSearchStop Stop-objects for stopping search
788 * \ingroup TaskModelSearch
789 *
790 * Allows to specify various criteria when a search engine should
791 * stop exploration. Only exploration but neither recomputation
792 * nor propagation will be interrupted.
793 *
794 */
795
796 /**
797 * \brief Base-class for %Stop-object
798 * \ingroup TaskModelSearchStop
799 */
800 class GECODE_SEARCH_EXPORT Stop : public HeapAllocated {
801 public:
802 /// \name Constructors and member functions
803 //@{
804 /// Default constructor
805 Stop(void);
806 /// Stop search, if returns true
807 virtual bool stop(const Statistics& s, const Options& o) = 0;
808 /// Destructor
809 virtual ~Stop(void);
810 //@}
811 /// \name Predefined stop objects
812 //@{
813 /// Stop if node limit \a l has been exceeded
814 static Stop* node(unsigned long long int l);
815 /// Stop if failure limit \a l has been exceeded
816 static Stop* fail(unsigned long long int l);
817 /// Stop if time limit \a l (in milliseconds) has been exceeded
818 static Stop* time(double l);
819 //@}
820 };
821
822 /**
823 * \brief %Stop-object based on number of nodes
824 *
825 * The number of nodes reported (by the statistics) is the
826 * number since the engine started exploration. It is not the
827 * number since the last stop!
828 * \ingroup TaskModelSearchStop
829 */
830 class GECODE_SEARCH_EXPORT NodeStop : public Stop {
831 protected:
832 /// Node limit
833 unsigned long long int l;
834 public:
835 /// Stop if node limit \a l is exceeded
836 NodeStop(unsigned long long int l);
837 /// Return current limit
838 unsigned long long int limit(void) const;
839 /// Set current limit to \a l nodes
840 void limit(unsigned long long int l);
841 /// Return true if node limit is exceeded
842 virtual bool stop(const Statistics& s, const Options& o);
843 };
844
845 /**
846 * \brief %Stop-object based on number of failures
847 *
848 * The number of failures reported (by the statistics) is the
849 * number since the engine started exploration. It is not the
850 * number since the last stop!
851 * \ingroup TaskModelSearchStop
852 */
853 class GECODE_SEARCH_EXPORT FailStop : public Stop {
854 protected:
855 /// Failure limit
856 unsigned long long int l;
857 public:
858 /// Stop if failure limit \a l is exceeded
859 FailStop(unsigned long long int l);
860 /// Return current limit
861 unsigned long long int limit(void) const;
862 /// Set current limit to \a l failures
863 void limit(unsigned long long int l);
864 /// Return true if failure limit is exceeded
865 virtual bool stop(const Statistics& s, const Options& o);
866 };
867
868 /**
869 * \brief %Stop-object based on time
870 * \ingroup TaskModelSearchStop
871 */
872 class GECODE_SEARCH_EXPORT TimeStop : public Stop {
873 protected:
874 /// Time when execution should stop
875 Support::Timer t;
876 /// Current limit in milliseconds
877 double l;
878 public:
879 /// Stop if search exceeds \a l milliseconds (from creation of this object)
880 TimeStop(double l);
881 /// Return current limit in milliseconds
882 double limit(void) const;
883 /// Set current limit to \a l milliseconds
884 void limit(double l);
885 /// Reset time to zero
886 void reset(void);
887 /// Return true if time limit is exceeded
888 virtual bool stop(const Statistics& s, const Options& o);
889 };
890
891}}
892
893#include <gecode/search/stop.hpp>
894
895namespace Gecode { namespace Search {
896
897 /**
898 * \brief %Search engine implementation interface
899 */
900 class GECODE_SEARCH_EXPORT Engine : public HeapAllocated {
901 public:
902 /// Return next solution (nullptr, if none exists or search has been stopped)
903 virtual Space* next(void) = 0;
904 /// Return statistics
905 virtual Statistics statistics(void) const = 0;
906 /// Check whether engine has been stopped
907 virtual bool stopped(void) const = 0;
908 /// Constrain future solutions to be better than \a b (raises exception)
909 virtual void constrain(const Space& b);
910 /// Reset engine to restart at space \a s (does nothing)
911 virtual void reset(Space* s);
912 /// Return no-goods (the no-goods are empty)
913 virtual NoGoods& nogoods(void);
914 /// Destructor
915 virtual ~Engine(void);
916 };
917
918}}
919
920#include <gecode/search/engine.hpp>
921
922namespace Gecode { namespace Search {
923
924 /// Base-class for search engines
925 template<class T>
926 class Base : public HeapAllocated {
927 template<class, class>
928 friend Engine* build(Space*, const Options&);
929 template<class, template<class> class>
930 friend Engine* build(Space*, const Options&);
931 protected:
932 /// The actual search engine
933 Engine* e;
934 /// Constructor
935 Base(Engine* e = nullptr);
936 public:
937 /// Return next solution (nullptr, if none exists or search has been stopped)
938 virtual T* next(void);
939 /// Return statistics
940 virtual Statistics statistics(void) const;
941 /// Check whether engine has been stopped
942 virtual bool stopped(void) const;
943 /// Destructor
944 virtual ~Base(void);
945 private:
946 /// Disallow copy constructor
947 Base(const Base&);
948 /// Disallow assigment operator
949 Base& operator =(const Base&);
950 };
951
952}}
953
954#include <gecode/search/base.hpp>
955
956namespace Gecode { namespace Search {
957
958 /// Build an engine of type \a E for a script \a T
959 template<class T, class E>
960 Engine* build(Space* s, const Options& opt);
961 /// Build a parametric engine of type \a E for a script \a T
962 template<class T, template<class> class E>
963 Engine* build(Space* s, const Options& opt);
964
965 /// A class for building search engines
966 class GECODE_SEARCH_EXPORT Builder : public HeapAllocated {
967 protected:
968 /// Stored and already expanded options
969 Options opt;
970 /// Whether engine to be built is a best solution search engine
971 const bool b;
972 public:
973 /// Initialize with options \a opt and \a best solution search support
974 Builder(const Options& opt, bool best);
975 /// Provide access to options
976 Options& options(void);
977 /// Provide access to options
978 const Options& options(void) const;
979 /// Whether engine is a best solution search engine
980 bool best(void) const;
981 /// Build an engine according to stored options for \a s
982 virtual Engine* operator() (Space* s) const = 0;
983 /// Destructor
984 virtual ~Builder(void);
985 };
986
987}}
988
989#include <gecode/search/build.hpp>
990
991namespace Gecode {
992
993 /// Type for a search engine builder
994 typedef Search::Builder* SEB;
995
996}
997
998#include <gecode/search/traits.hpp>
999
1000namespace Gecode {
1001
1002 /// Passing search engine builder arguments
1003 class SEBs : public ArgArray<SEB> {
1004 public:
1005 /// \name Constructors and initialization
1006 //@{
1007 /// Allocate empty array
1008 SEBs(void);
1009 /// Allocate array with \a n elements
1010 explicit SEBs(int n);
1011 /// Allocate array and copy elements from \a x
1012 SEBs(const std::vector<SEB>& x);
1013 /// Allocate array with and initialize with \a x
1014 SEBs(std::initializer_list<SEB> x);
1015 /// Allocate array and copy elements from \a first to \a last
1016 template<class InputIterator>
1017 SEBs(InputIterator first, InputIterator last);
1018 /// Initialize from primitive argument array \a a (copy elements)
1019 SEBs(const ArgArray<SEB>& a);
1020 //@}
1021 };
1022
1023}
1024
1025#include <gecode/search/sebs.hpp>
1026
1027namespace Gecode {
1028
1029 /**
1030 * \brief Depth-first search engine
1031 *
1032 * This class supports depth-first search for subclasses \a T of
1033 * Space.
1034 * \ingroup TaskModelSearch
1035 */
1036 template<class T>
1037 class DFS : public Search::Base<T> {
1038 public:
1039 /// Initialize search engine for space \a s with options \a o
1040 DFS(T* s, const Search::Options& o=Search::Options::def);
1041 /// Whether engine does best solution search
1042 static const bool best = false;
1043 };
1044
1045 /// Invoke depth-first search engine for subclass \a T of space \a s with options \a o
1046 template<class T>
1047 T* dfs(T* s, const Search::Options& o=Search::Options::def);
1048
1049 /// Return a depth-first search engine builder
1050 template<class T>
1051 SEB dfs(const Search::Options& o=Search::Options::def);
1052
1053}
1054
1055#include <gecode/search/dfs.hpp>
1056
1057namespace Gecode {
1058
1059 /**
1060 * \brief Depth-first branch-and-bound search engine
1061 *
1062 * Additionally, \a s must implement a member function
1063 * \code virtual void constrain(const T& t) \endcode
1064 * Whenever exploration requires to add a constraint
1065 * to the space \a c currently being explored, the engine
1066 * executes \c c.constrain(t) where \a t is the so-far
1067 * best solution.
1068 * \ingroup TaskModelSearch
1069 */
1070 template<class T>
1071 class BAB : public Search::Base<T> {
1072 public:
1073 /// Initialize engine for space \a s and options \a o
1074 BAB(T* s, const Search::Options& o=Search::Options::def);
1075 /// Whether engine does best solution search
1076 static const bool best = true;
1077 };
1078
1079 /**
1080 * \brief Perform depth-first branch-and-bound search for subclass \a T of space \a s and options \a o
1081 *
1082 * Additionally, \a s must implement a member function
1083 * \code virtual void constrain(const T& t) \endcode
1084 * Whenever exploration requires to add a constraint
1085 * to the space \a c currently being explored, the engine
1086 * executes \c c.constrain(t) where \a t is the so-far
1087 * best solution.
1088 *
1089 * \ingroup TaskModelSearch
1090 */
1091 template<class T>
1092 T* bab(T* s, const Search::Options& o=Search::Options::def);
1093
1094 /// Return a depth-first branch-and-bound search engine builder
1095 template<class T>
1096 SEB bab(const Search::Options& o=Search::Options::def);
1097
1098}
1099
1100#include <gecode/search/bab.hpp>
1101
1102namespace Gecode {
1103
1104 /**
1105 * \brief Limited discrepancy search engine
1106 * \ingroup TaskModelSearch
1107 */
1108 template<class T>
1109 class LDS : public Search::Base<T> {
1110 public:
1111 /// Initialize engine for space \a s and options \a o
1112 LDS(T* s, const Search::Options& o=Search::Options::def);
1113 /// Whether engine does best solution search
1114 static const bool best = false;
1115 };
1116
1117 /**
1118 * \brief Invoke limited-discrepancy search for \a s as root node and options\a o
1119 * \ingroup TaskModelSearch
1120 */
1121 template<class T>
1122 T* lds(T* s, const Search::Options& o=Search::Options::def);
1123
1124 /// Return a limited discrepancy search engine builder
1125 template<class T>
1126 SEB lds(const Search::Options& o=Search::Options::def);
1127
1128}
1129
1130#include <gecode/search/lds.hpp>
1131
1132namespace Gecode {
1133
1134 /**
1135 * \brief Meta-engine performing restart-based search
1136 *
1137 * The engine uses the Cutoff sequence supplied in the options \a o to
1138 * periodically restart the search of engine \a E.
1139 *
1140 * The class \a T can implement member functions
1141 * \code virtual bool master(const MetaInfo& mi) \endcode
1142 * and
1143 * \code virtual bool slave(const MetaInfo& mi) \endcode
1144 *
1145 * Whenever exploration restarts or a solution is found, the
1146 * engine executes the functions on the master and slave
1147 * space. For more details, consult "Modeling and Programming
1148 * with Gecode".
1149 *
1150 * \ingroup TaskModelSearch
1151 */
1152 template<class T, template<class> class E = DFS>
1153 class RBS : public Search::Base<T> {
1154 using Search::Base<T>::e;
1155 public:
1156 /// Initialize engine for space \a s and options \a o
1157 RBS(T* s, const Search::Options& o);
1158 /// Whether engine does best solution search
1159 static const bool best = E<T>::best;
1160 };
1161
1162 /**
1163 * \brief Perform restart-based search
1164 *
1165 * The engine uses the Cutoff sequence supplied in the options \a o to
1166 * periodically restart the search of engine \a E.
1167 *
1168 * The class \a T can implement member functions
1169 * \code virtual bool master(const MetaInfo& mi) \endcode
1170 * and
1171 * \code virtual bool slave(const MetaInfo& mi) \endcode
1172 *
1173 * Whenever exploration restarts or a solution is found, the
1174 * engine executes the functions on the master and slave
1175 * space. For more details, consult "Modeling and Programming
1176 * with Gecode".
1177 *
1178 * \ingroup TaskModelSearch
1179 */
1180 template<class T, template<class> class E>
1181 T* rbs(T* s, const Search::Options& o);
1182
1183 /// Return a restart search engine builder
1184 template<class T, template<class> class E>
1185 SEB rbs(const Search::Options& o);
1186
1187}
1188
1189#include <gecode/search/rbs.hpp>
1190
1191namespace Gecode { namespace Search { namespace Meta {
1192
1193 /// Build a sequential engine
1194 template<class T, template<class> class E>
1195 Engine* sequential(T* master, const Search::Statistics& stat, Options& opt);
1196
1197 /// Build a sequential engine
1198 template<class T, template<class> class E>
1199 Engine* sequential(T* master, SEBs& sebs,
1200 const Search::Statistics& stat, Options& opt, bool best);
1201
1202#ifdef GECODE_HAS_THREADS
1203
1204 /// Build a parallel engine
1205 template<class T, template<class> class E>
1206 Engine* parallel(T* master, const Search::Statistics& stat, Options& opt);
1207
1208 /// Build a parallel engine
1209 template<class T, template<class> class E>
1210 Engine* parallel(T* master, SEBs& sebs,
1211 const Search::Statistics& stat, Options& opt, bool best);
1212
1213#endif
1214
1215}}}
1216
1217namespace Gecode {
1218
1219 /**
1220 * \brief Meta engine using a portfolio of search engines
1221 *
1222 * The engine will run a portfolio with a number of assets as defined
1223 * by the options \a o. The engine supports parallel execution of
1224 * assets by using the number of threads as defined by the options.
1225 *
1226 * The class \a T can implement member functions
1227 * \code virtual bool master(const MetaInfo& mi) \endcode
1228 * and
1229 * \code virtual bool slave(const MetaInfo& mi) \endcode
1230 *
1231 * When the assets are created, these functions are executed.
1232 * For more details, consult "Modeling and Programming with Gecode".
1233 *
1234 * \ingroup TaskModelSearch
1235 */
1236 template<class T, template<class> class E = DFS>
1237 class PBS : public Search::Base<T> {
1238 using Search::Base<T>::e;
1239 protected:
1240 /// The actual build function
1241 void build(T* s, SEBs& sebs, const Search::Options& o);
1242 public:
1243 /// Initialize with engines running copies of \a s with options \a o
1244 PBS(T* s, const Search::Options& o=Search::Options::def);
1245 /// Initialize with engine builders \a sebs
1246 PBS(T* s, SEBs& sebs, const Search::Options& o=Search::Options::def);
1247 /// Whether engine does best solution search
1248 static const bool best = E<T>::best;
1249 };
1250
1251 /**
1252 * \brief Run a portfolio of search engines
1253 *
1254 * The engine will run a portfolio with a number of assets as defined
1255 * by the options \a o. The engine supports parallel execution of
1256 * assets by using the number of threads as defined by the options.
1257 *
1258 * The class \a T can implement member functions
1259 * \code virtual bool master(const MetaInfo& mi) \endcode
1260 * and
1261 * \code virtual bool slave(const MetaInfo& mi) \endcode
1262 *
1263 * When the assets are created, these functions are executed.
1264 * For more details, consult "Modeling and Programming with Gecode".
1265 *
1266 * \ingroup TaskModelSearch
1267 */
1268 template<class T, template<class> class E>
1269 T* pbs(T* s, const Search::Options& o=Search::Options::def);
1270
1271 /// Return a portfolio search engine builder
1272 template<class T>
1273 SEB pbs(const Search::Options& o=Search::Options::def);
1274
1275}
1276
1277#include <gecode/search/pbs.hpp>
1278
1279#endif
1280
1281// STATISTICS: search-other