Generated on Fri Jul 13 2018 06:08:22 for Gecode by doxygen 1.8.14
script.hpp
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, 2004
8  *
9  * Last modified:
10  * $Date: 2016-10-25 12:52:26 +0200 (Tue, 25 Oct 2016) $ by $Author: schulte $
11  * $Revision: 15233 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  *
18  * Permission is hereby granted, free of charge, to any person obtaining
19  * a copy of this software and associated documentation files (the
20  * "Software"), to deal in the Software without restriction, including
21  * without limitation the rights to use, copy, modify, merge, publish,
22  * distribute, sublicense, and/or sell copies of the Software, and to
23  * permit persons to whom the Software is furnished to do so, subject to
24  * the following conditions:
25  *
26  * The above copyright notice and this permission notice shall be
27  * included in all copies or substantial portions of the Software.
28  *
29  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36  *
37  */
38 
39 #include <iostream>
40 #include <iomanip>
41 #include <fstream>
42 #include <cstring>
43 
44 #ifndef GECODE_THREADS_WINDOWS
45 #include <csignal>
46 #endif
47 
48 namespace Gecode { namespace Driver {
49 
54  class CombinedStop : public Search::Stop {
55  private:
56  Search::NodeStop* ns;
57  Search::FailStop* fs;
58  Search::TimeStop* ts;
60  static bool sigint;
61  CombinedStop(unsigned int node, unsigned int fail, unsigned int time)
63  : ns((node > 0) ? new Search::NodeStop(node) : NULL),
64  fs((fail > 0) ? new Search::FailStop(fail) : NULL),
65  ts((time > 0) ? new Search::TimeStop(time) : NULL) {
66  sigint = false;
67  }
68  public:
70  enum {
71  SR_NODE = 1 << 0,
72  SR_FAIL = 1 << 1,
73  SR_TIME = 1 << 2,
74  SR_INT = 1 << 3
75  };
77  virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
78  return
79  sigint ||
80  ((ns != NULL) && ns->stop(s,o)) ||
81  ((fs != NULL) && fs->stop(s,o)) ||
82  ((ts != NULL) && ts->stop(s,o));
83  }
85  int reason(const Search::Statistics& s, const Search::Options& o) {
86  return
87  (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
88  (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
89  (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0) |
90  (sigint ? SR_INT : 0);
91  }
93  static Search::Stop*
94  create(unsigned int node, unsigned int fail, unsigned int time,
95  bool intr) {
96  if ( (!intr) && (node == 0) && (fail == 0) && (time == 0))
97  return NULL;
98  else
99  return new CombinedStop(node,fail,time);
100  }
101 #ifdef GECODE_THREADS_WINDOWS
102  static BOOL interrupt(DWORD t) {
104  if (t == CTRL_C_EVENT) {
105  sigint = true;
106  installCtrlHandler(false,true);
107  return true;
108  }
109  return false;
110  }
111 #else
112  static void
114  interrupt(int) {
115  sigint = true;
116  installCtrlHandler(false,true);
117  }
118 #endif
119  static void installCtrlHandler(bool install, bool force=false) {
121  if (force || !sigint) {
122 #ifdef GECODE_THREADS_WINDOWS
123  SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
124 #else
125  std::signal(SIGINT, install ? interrupt : SIG_DFL);
126 #endif
127  }
128  }
131  delete ns; delete fs; delete ts;
132  }
133  };
134 
140  stop(Support::Timer& t, std::ostream& os);
141 
145  GECODE_DRIVER_EXPORT double
146  am(double t[], unsigned int n);
147 
151  GECODE_DRIVER_EXPORT double
152  dev(double t[], unsigned int n);
153 
155  template<class Options>
156  inline Search::Cutoff*
157  createCutoff(const Options& o) {
158  switch (o.restart()) {
159  case RM_NONE:
160  return NULL;
161  case RM_CONSTANT:
163  case RM_LINEAR:
165  case RM_LUBY:
167  case RM_GEOMETRIC:
169  default: GECODE_NEVER;
170  }
171  return NULL;
172  }
173 
174 
175 #ifdef GECODE_HAS_GIST
176 
180  template<class Engine>
181  class GistEngine {
182  public:
183  static void explore(Space* root, const Gist::Options& opt) {
184  (void) Gist::dfs(root, opt);
185  }
186  };
187 
189  template<typename S>
190  class GistEngine<DFS<S> > {
191  public:
192  static void explore(S* root, const Gist::Options& opt) {
193  (void) Gist::dfs(root, opt);
194  }
195  };
196 
198  template<typename S>
199  class GistEngine<LDS<S> > {
200  public:
201  static void explore(S* root, const Gist::Options& opt) {
202  (void) Gist::dfs(root, opt);
203  }
204  };
205 
207  template<typename S>
208  class GistEngine<BAB<S> > {
209  public:
210  static void explore(S* root, const Gist::Options& opt) {
211  (void) Gist::bab(root, opt);
212  }
213  };
214 
215 #endif
216 
217 
218  template<class BaseSpace>
221  : BaseSpace(opt) {}
222 
223  template<class BaseSpace>
226  : BaseSpace(share,e) {}
227 
228  template<class BaseSpace>
229  void
230  ScriptBase<BaseSpace>::print(std::ostream&) const {}
231 
232  template<class BaseSpace>
233  void
234  ScriptBase<BaseSpace>::compare(const Space&, std::ostream&) const {}
235 
236  template<class BaseSpace>
237  std::ostream&
238  ScriptBase<BaseSpace>::select_ostream(const char* sn, std::ofstream& ofs) {
239  if (strcmp(sn, "stdout") == 0) {
240  return std::cout;
241  } else if (strcmp(sn, "stdlog") == 0) {
242  return std::clog;
243  } else if (strcmp(sn, "stderr") == 0) {
244  return std::cerr;
245  } else {
246  ofs.open(sn);
247  return ofs;
248  }
249  }
250 
251 
255  template<class T, template<class> class E>
256  class EngineToMeta : public E<T> {
257  public:
258  EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
259  };
260 
261  template<class BaseSpace>
262  template<class Script, template<class> class Engine, class Options>
263  void
265  if ((o.restart() != RM_NONE) && (o.assets() > 0)) {
266  std::cerr << "Cannot use restarts and portfolio..." << std::endl;
267  exit(EXIT_FAILURE);
268  }
269  if (o.restart() != RM_NONE) {
270  runMeta<Script,Engine,Options,RBS>(o,s);
271  } else if (o.assets() > 0) {
272  runMeta<Script,Engine,Options,PBS>(o,s);
273  } else {
274  runMeta<Script,Engine,Options,EngineToMeta>(o,s);
275  }
276  }
277 
278  template<class BaseSpace>
279  template<class Script, template<class> class Engine, class Options,
280  template<class, template<class> class> class Meta>
281  void
282  ScriptBase<BaseSpace>::runMeta(const Options& o, Script* s) {
283  using namespace std;
284 
285  ofstream sol_file, log_file;
286 
287  ostream& s_out = select_ostream(o.out_file(), sol_file);
288  ostream& l_out = select_ostream(o.log_file(), log_file);
289 
290  try {
291  switch (o.mode()) {
292  case SM_GIST:
293 #ifdef GECODE_HAS_GIST
294  {
295  Gist::Print<Script> pi(o.name());
296  Gist::VarComparator<Script> vc(o.name());
298  opt.inspect.click(&pi);
299  opt.inspect.compare(&vc);
300  opt.clone = false;
301  opt.c_d = o.c_d();
302  opt.a_d = o.a_d();
303  for (unsigned int i=0; o.inspect.click(i) != NULL; i++)
304  opt.inspect.click(o.inspect.click(i));
305  for (unsigned int i=0; o.inspect.solution(i) != NULL; i++)
306  opt.inspect.solution(o.inspect.solution(i));
307  for (unsigned int i=0; o.inspect.move(i) != NULL; i++)
308  opt.inspect.move(o.inspect.move(i));
309  for (unsigned int i=0; o.inspect.compare(i) != NULL; i++)
310  opt.inspect.compare(o.inspect.compare(i));
311  if (s == NULL)
312  s = new Script(o);
313  (void) GistEngine<Engine<Script> >::explore(s, opt);
314  }
315  break;
316  // If Gist is not available, fall through
317 #endif
318  case SM_SOLUTION:
319  {
320  l_out << o.name() << endl;
322  int i = static_cast<int>(o.solutions());
323  t.start();
324  if (s == NULL)
325  s = new Script(o);
326  unsigned int n_p = PropagatorGroup::all.size(*s);
327  unsigned int n_b = BrancherGroup::all.size(*s);
328  Search::Options so;
329  so.threads = o.threads();
330  so.c_d = o.c_d();
331  so.a_d = o.a_d();
332  so.d_l = o.d_l();
333  so.assets = o.assets();
334  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
335  o.interrupt());
336  so.cutoff = createCutoff(o);
337  so.clone = false;
338  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
339  if (o.interrupt())
341  {
342  Meta<Script,Engine> e(s,so);
343  if (o.print_last()) {
344  Script* px = NULL;
345  do {
346  Script* ex = e.next();
347  if (ex == NULL) {
348  if (px != NULL) {
349  px->print(s_out);
350  delete px;
351  }
352  break;
353  } else {
354  delete px;
355  px = ex;
356  }
357  } while (--i != 0);
358  } else {
359  do {
360  Script* ex = e.next();
361  if (ex == NULL)
362  break;
363  ex->print(s_out);
364  delete ex;
365  } while (--i != 0);
366  }
367  if (o.interrupt())
369  Search::Statistics stat = e.statistics();
370  s_out << endl;
371  if (e.stopped()) {
372  l_out << "Search engine stopped..." << endl
373  << "\treason: ";
374  int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
375  if (r & CombinedStop::SR_INT)
376  l_out << "user interrupt " << endl;
377  else {
378  if (r & CombinedStop::SR_NODE)
379  l_out << "node ";
380  if (r & CombinedStop::SR_FAIL)
381  l_out << "fail ";
382  if (r & CombinedStop::SR_TIME)
383  l_out << "time ";
384  l_out << "limit reached" << endl << endl;
385  }
386  }
387  l_out << "Initial" << endl
388  << "\tpropagators: " << n_p << endl
389  << "\tbranchers: " << n_b << endl
390  << endl
391  << "Summary" << endl
392  << "\truntime: ";
393  stop(t, l_out);
394  l_out << endl
395  << "\tsolutions: "
396  << ::abs(static_cast<int>(o.solutions()) - i) << endl
397  << "\tpropagations: " << stat.propagate << endl
398  << "\tnodes: " << stat.node << endl
399  << "\tfailures: " << stat.fail << endl
400  << "\trestarts: " << stat.restart << endl
401  << "\tno-goods: " << stat.nogood << endl
402  << "\tpeak depth: " << stat.depth << endl
403 #ifdef GECODE_PEAKHEAP
404  << "\tpeak memory: "
405  << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
406  << endl
407 #endif
408  << endl;
409  }
410  delete so.stop;
411  }
412  break;
413  case SM_STAT:
414  {
415  l_out << o.name() << endl;
416  Support::Timer t;
417  int i = static_cast<int>(o.solutions());
418  t.start();
419  if (s == NULL)
420  s = new Script(o);
421  unsigned int n_p = PropagatorGroup::all.size(*s);
422  unsigned int n_b = BrancherGroup::all.size(*s);
423  Search::Options so;
424  so.clone = false;
425  so.threads = o.threads();
426  so.assets = o.assets();
427  so.c_d = o.c_d();
428  so.a_d = o.a_d();
429  so.d_l = o.d_l();
430  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
431  o.interrupt());
432  so.cutoff = createCutoff(o);
433  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
434  if (o.interrupt())
436  {
437  Meta<Script,Engine> e(s,so);
438  do {
439  Script* ex = e.next();
440  if (ex == NULL)
441  break;
442  delete ex;
443  } while (--i != 0);
444  if (o.interrupt())
446  Search::Statistics stat = e.statistics();
447  l_out << endl
448  << "\tpropagators: " << n_p << endl
449  << "\tbranchers: " << n_b << endl
450  << "\truntime: ";
451  stop(t, l_out);
452  l_out << endl
453  << "\tsolutions: "
454  << ::abs(static_cast<int>(o.solutions()) - i) << endl
455  << "\tpropagations: " << stat.propagate << endl
456  << "\tnodes: " << stat.node << endl
457  << "\tfailures: " << stat.fail << endl
458  << "\trestarts: " << stat.restart << endl
459  << "\tno-goods: " << stat.nogood << endl
460  << "\tpeak depth: " << stat.depth << endl
461 #ifdef GECODE_PEAKHEAP
462  << "\tpeak memory: "
463  << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
464  << endl
465 #endif
466  << endl;
467  }
468  delete so.stop;
469  }
470  break;
471  case SM_TIME:
472  {
473  l_out << o.name() << endl;
474  Support::Timer t;
475  double* ts = new double[o.samples()];
476  bool stopped = false;
477  for (unsigned int ns = o.samples(); !stopped && ns--; ) {
478  t.start();
479  for (unsigned int k = o.iterations(); !stopped && k--; ) {
480  unsigned int i = o.solutions();
481  Script* s1 = new Script(o);
482  Search::Options so;
483  so.clone = false;
484  so.threads = o.threads();
485  so.assets = o.assets();
486  so.c_d = o.c_d();
487  so.a_d = o.a_d();
488  so.d_l = o.d_l();
489  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
490  false);
491  so.cutoff = createCutoff(o);
492  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
493  {
494  Meta<Script,Engine> e(s1,so);
495  do {
496  Script* ex = e.next();
497  if (ex == NULL)
498  break;
499  delete ex;
500  } while (--i != 0);
501  if (e.stopped())
502  stopped = true;
503  }
504  delete so.stop;
505  }
506  ts[ns] = t.stop() / o.iterations();
507  }
508  if (stopped) {
509  l_out << "\tSTOPPED" << endl;
510  } else {
511  double m = am(ts,o.samples());
512  double d = dev(ts,o.samples()) * 100.0;
513  l_out << "\truntime: "
514  << setw(20) << right
515  << showpoint << fixed
516  << setprecision(6) << m << "ms"
517  << setprecision(2) << " (" << d << "% deviation)"
518  << endl;
519  }
520  delete [] ts;
521  }
522  break;
523  }
524  } catch (Exception& e) {
525  cerr << "Exception: " << e.what() << "." << endl
526  << "Stopping..." << endl;
527  if (sol_file.is_open())
528  sol_file.close();
529  if (log_file.is_open())
530  log_file.close();
531  exit(EXIT_FAILURE);
532  }
533  if (sol_file.is_open())
534  sol_file.close();
535  if (log_file.is_open())
536  log_file.close();
537  }
538 
539 }}
540 
541 // STATISTICS: driver-any
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:455
Restart with linear sequence.
Definition: driver.hh:112
NodeType t
Type of node.
Definition: bool-expr.cpp:234
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:467
Limited discrepancy search engine.
Definition: search.hh:811
static BrancherGroup all
Group of all branchers.
Definition: core.hpp:913
Search engine statistics
Definition: search.hh:140
Stop-object based on number of nodes
Definition: search.hh:531
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:453
Search engine options
Definition: search.hh:446
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:45
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:855
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
Traits class for search engines.
Definition: script.hpp:181
virtual void print(std::ostream &os) const
Print a solution to os.
Definition: script.hpp:230
static void interrupt(int)
Handler for catching Ctrl-C.
Definition: script.hpp:114
Restart with Luby sequence.
Definition: driver.hh:113
No restarts.
Definition: driver.hh:110
Base class for cutoff generators for restart-based meta engine.
Definition: search.hh:172
static Stop * fail(unsigned long int l)
Stop if failure limit l has been exceeded.
Definition: stop.cpp:51
Search::Cutoff * createCutoff(const Options &o)
Create cutoff object from options.
Definition: script.hpp:157
Computation spaces.
Definition: core.hpp:1748
unsigned int d_l
Discrepancy limit (for LDS)
Definition: search.hh:457
Parametric base-class for scripts.
Definition: driver.hh:703
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition: core.cpp:917
virtual void compare(const Space &home, std::ostream &os) const
Compare with s.
Definition: script.hpp:234
static Stop * node(unsigned long int l)
Stop if node limit l has been exceeded.
Definition: stop.cpp:47
Gecode::IntSet d(v, 7)
static void explore(S *root, const Gist::Options &opt)
Definition: script.hpp:201
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:471
double threads
Number of threads to use.
Definition: search.hh:451
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Options opt
The options.
Definition: test.cpp:101
int dfs(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for root.
Definition: gist.hpp:207
Print solution and some statistics.
Definition: driver.hh:99
Depth-first branch-and-bound search engine.
Definition: search.hh:773
static void installCtrlHandler(bool install, bool force=false)
Install handler for catching Ctrl-C.
Definition: script.hpp:120
static Search::Stop * create(unsigned int node, unsigned int fail, unsigned int time, bool intr)
Create appropriate stop-object.
Definition: script.hpp:94
Stop object based on nodes, failures, and time.
Definition: script.hpp:54
static void explore(S *root, const Gist::Options &opt)
Definition: script.hpp:192
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition: core.cpp:995
double am(double t[], unsigned int n)
Compute arithmetic mean of n elements in t.
Definition: script.cpp:78
Measure average runtime.
Definition: driver.hh:100
Wrapper class to add engine template argument.
Definition: script.hpp:256
EngineToMeta(T *s, const Search::Options &o)
Definition: script.hpp:258
int reason(const Search::Statistics &s, const Search::Options &o)
Report reason why search has been stopped.
Definition: script.hpp:85
void restart_scale(unsigned int scale)
Set default restart scale factor.
Definition: options.hpp:395
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:449
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
Definition: stop.cpp:75
const int * pi[]
Definition: photo.cpp:14266
#define GECODE_DRIVER_EXPORT
Definition: driver.hh:65
static Stop * time(unsigned long int l)
Stop if time limit l (in milliseconds) has been exceeded.
Definition: stop.cpp:55
A simple comparator.
Definition: gist.hh:215
static Cutoff * geometric(unsigned long int scale=Config::slice, double base=Config::base)
Definition: cutoff.cpp:164
unsigned int assets
Number of assets (engines) in a portfolio.
Definition: search.hh:463
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
double dev(double t[], unsigned int n)
Compute deviation of n elements in t.
Definition: script.cpp:88
~CombinedStop(void)
Destructor.
Definition: script.hpp:130
void assets(unsigned int n)
Set default number of assets in a portfolio.
Definition: options.hpp:359
Interrupted by user.
Definition: script.hpp:74
Print statistics for script.
Definition: driver.hh:101
Restart with geometric sequence.
Definition: driver.hh:114
static Cutoff * linear(unsigned long int scale=Config::slice)
Create generator for linear sequence scaled by scale.
Definition: cutoff.cpp:156
static Cutoff * luby(unsigned long int scale=Config::slice)
Create generator for luby sequence with scale-factor scale.
Definition: cutoff.cpp:160
Heap heap
The single global heap.
Definition: heap.cpp:48
#define forceinline
Definition: config.hpp:173
virtual bool stop(const Statistics &s, const Options &o)
Return true if node limit is exceeded.
Definition: stop.cpp:65
static void run(const Options &opt, Script *s=NULL)
Definition: script.hpp:264
void restart_base(double base)
Set default restart base.
Definition: options.hpp:386
int bab(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for branch-and-bound search of root.
Definition: gist.hpp:212
Run script in Gist.
Definition: driver.hh:102
ScriptBase(const Options &opt)
Constructor.
Definition: script.hpp:220
static Cutoff * constant(unsigned long int scale=Config::slice)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:152
Stop * stop
Stop object for stopping search.
Definition: search.hh:469
int explore(Space *root, bool bab, const Options &opt)
Create a new stand-alone Gist for root using bab.
Definition: gist.cpp:106
Gecode toplevel namespace
static std::ostream & select_ostream(const char *sn, std::ofstream &ofs)
Choose output stream according to sn.
Definition: script.hpp:238
An inspector for printing simple text output.
Definition: gist.hh:192
Stop-object based on time
Definition: search.hh:573
Base-class for Stop-object.
Definition: search.hh:501
Options for Gist
Definition: gist.hh:238
void restart(RestartMode r)
Set default restart mode.
Definition: options.hpp:377
static void explore(S *root, const Gist::Options &opt)
Definition: script.hpp:210
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
virtual bool stop(const Statistics &s, const Options &o)
Return true if time limit is exceeded.
Definition: stop.cpp:85
Options for scripts
Definition: driver.hh:366
Restart with constant sequence.
Definition: driver.hh:111
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition: driver.hh:778
Depth-first search engine.
Definition: search.hh:739
Stop-object based on number of failures
Definition: search.hh:554
static void explore(Space *root, const Gist::Options &opt)
Definition: script.hpp:183
virtual bool stop(const Search::Statistics &s, const Search::Options &o)
Test whether search must be stopped.
Definition: script.hpp:77