Generated on Sat Sep 5 2015 20:51:05 for Gecode by doxygen 1.8.9.1
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: 2015-03-17 16:09:10 +0100 (Tue, 17 Mar 2015) $ by $Author: schulte $
11  * $Revision: 14446 $
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[], int n);
147 
151  GECODE_DRIVER_EXPORT double
152  dev(double t[], 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<BAB<S> > {
200  public:
201  static void explore(S* root, const Gist::Options& opt) {
202  (void) Gist::bab(root, opt);
203  }
204  };
205 
206 #endif
207 
208 
209  template<class BaseSpace>
212  : BaseSpace(opt) {}
213 
214  template<class BaseSpace>
217  : BaseSpace(share,e) {}
218 
219  template<class BaseSpace>
220  void
221  ScriptBase<BaseSpace>::print(std::ostream&) const {}
222 
223  template<class BaseSpace>
224  void
225  ScriptBase<BaseSpace>::compare(const Space&, std::ostream&) const {}
226 
227  template<class BaseSpace>
228  std::ostream&
229  ScriptBase<BaseSpace>::select_ostream(const char* name, std::ofstream& ofs) {
230  if (strcmp(name, "stdout") == 0) {
231  return std::cout;
232  } else if (strcmp(name, "stdlog") == 0) {
233  return std::clog;
234  } else if (strcmp(name, "stderr") == 0) {
235  return std::cerr;
236  } else {
237  ofs.open(name);
238  return ofs;
239  }
240  }
241 
242 
246  template<template<class> class E, class T>
247  class EngineToMeta : public E<T> {
248  public:
249  EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
250  };
251 
252  template<class BaseSpace>
253  template<class Script, template<class> class Engine, class Options>
254  void
256  if (o.restart()==RM_NONE) {
257  runMeta<Script,Engine,Options,EngineToMeta>(o,s);
258  } else {
259  runMeta<Script,Engine,Options,RBS>(o,s);
260  }
261  }
262 
263  template<class BaseSpace>
264  template<class Script, template<class> class Engine, class Options,
265  template<template<class> class,class> class Meta>
266  void
267  ScriptBase<BaseSpace>::runMeta(const Options& o, Script* s) {
268  using namespace std;
269 
270  ofstream sol_file, log_file;
271 
272  ostream& s_out = select_ostream(o.out_file(), sol_file);
273  ostream& l_out = select_ostream(o.log_file(), log_file);
274 
275  try {
276  switch (o.mode()) {
277  case SM_GIST:
278 #ifdef GECODE_HAS_GIST
279  {
280  Gist::Print<Script> pi(o.name());
281  Gist::VarComparator<Script> vc(o.name());
283  opt.inspect.click(&pi);
284  opt.inspect.compare(&vc);
285  opt.clone = false;
286  opt.c_d = o.c_d();
287  opt.a_d = o.a_d();
288  for (int i=0; o.inspect.click(i) != NULL; i++)
289  opt.inspect.click(o.inspect.click(i));
290  for (int i=0; o.inspect.solution(i) != NULL; i++)
291  opt.inspect.solution(o.inspect.solution(i));
292  for (int i=0; o.inspect.move(i) != NULL; i++)
293  opt.inspect.move(o.inspect.move(i));
294  for (int i=0; o.inspect.compare(i) != NULL; i++)
295  opt.inspect.compare(o.inspect.compare(i));
296  if (s == NULL)
297  s = new Script(o);
298  (void) GistEngine<Engine<Script> >::explore(s, opt);
299  }
300  break;
301  // If Gist is not available, fall through
302 #endif
303  case SM_SOLUTION:
304  {
305  l_out << o.name() << endl;
307  int i = o.solutions();
308  t.start();
309  if (s == NULL)
310  s = new Script(o);
311  unsigned int n_p = s->propagators();
312  unsigned int n_b = s->branchers();
313  Search::Options so;
314  so.threads = o.threads();
315  so.c_d = o.c_d();
316  so.a_d = o.a_d();
317  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
318  o.interrupt());
319  so.cutoff = createCutoff(o);
320  so.clone = false;
321  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
322  if (o.interrupt())
324  {
325  Meta<Engine,Script> e(s,so);
326  if (o.print_last()) {
327  Script* px = NULL;
328  do {
329  Script* ex = e.next();
330  if (ex == NULL) {
331  if (px != NULL) {
332  px->print(s_out);
333  delete px;
334  }
335  break;
336  } else {
337  delete px;
338  px = ex;
339  }
340  } while (--i != 0);
341  } else {
342  do {
343  Script* ex = e.next();
344  if (ex == NULL)
345  break;
346  ex->print(s_out);
347  delete ex;
348  } while (--i != 0);
349  }
350  if (o.interrupt())
352  Search::Statistics stat = e.statistics();
353  s_out << endl;
354  if (e.stopped()) {
355  l_out << "Search engine stopped..." << endl
356  << "\treason: ";
357  int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
358  if (r & CombinedStop::SR_INT)
359  l_out << "user interrupt " << endl;
360  else {
361  if (r & CombinedStop::SR_NODE)
362  l_out << "node ";
363  if (r & CombinedStop::SR_FAIL)
364  l_out << "fail ";
365  if (r & CombinedStop::SR_TIME)
366  l_out << "time ";
367  l_out << "limit reached" << endl << endl;
368  }
369  }
370  l_out << "Initial" << endl
371  << "\tpropagators: " << n_p << endl
372  << "\tbranchers: " << n_b << endl
373  << endl
374  << "Summary" << endl
375  << "\truntime: ";
376  stop(t, l_out);
377  l_out << endl
378  << "\tsolutions: "
379  << ::abs(static_cast<int>(o.solutions()) - i) << endl
380  << "\tpropagations: " << stat.propagate << endl
381  << "\tnodes: " << stat.node << endl
382  << "\tfailures: " << stat.fail << endl
383  << "\trestarts: " << stat.restart << endl
384  << "\tno-goods: " << stat.nogood << endl
385  << "\tpeak depth: " << stat.depth << endl
386 #ifdef GECODE_PEAKHEAP
387  << "\tpeak memory: "
388  << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
389  << endl
390 #endif
391  << endl;
392  }
393  delete so.stop;
394  }
395  break;
396  case SM_STAT:
397  {
398  l_out << o.name() << endl;
399  Support::Timer t;
400  int i = o.solutions();
401  t.start();
402  if (s == NULL)
403  s = new Script(o);
404  unsigned int n_p = s->propagators();
405  unsigned int n_b = s->branchers();
406  Search::Options so;
407  so.clone = false;
408  so.threads = o.threads();
409  so.c_d = o.c_d();
410  so.a_d = o.a_d();
411  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
412  o.interrupt());
413  so.cutoff = createCutoff(o);
414  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
415  if (o.interrupt())
417  {
418  Meta<Engine,Script> e(s,so);
419  do {
420  Script* ex = e.next();
421  if (ex == NULL)
422  break;
423  delete ex;
424  } while (--i != 0);
425  if (o.interrupt())
427  Search::Statistics stat = e.statistics();
428  l_out << endl
429  << "\tpropagators: " << n_p << endl
430  << "\tbranchers: " << n_b << endl
431  << "\truntime: ";
432  stop(t, l_out);
433  l_out << endl
434  << "\tsolutions: "
435  << ::abs(static_cast<int>(o.solutions()) - i) << endl
436  << "\tpropagations: " << stat.propagate << endl
437  << "\tnodes: " << stat.node << endl
438  << "\tfailures: " << stat.fail << endl
439  << "\trestarts: " << stat.restart << endl
440  << "\tno-goods: " << stat.nogood << endl
441  << "\tpeak depth: " << stat.depth << endl
442 #ifdef GECODE_PEAKHEAP
443  << "\tpeak memory: "
444  << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
445  << endl
446 #endif
447  << endl;
448  }
449  delete so.stop;
450  }
451  break;
452  case SM_TIME:
453  {
454  l_out << o.name() << endl;
455  Support::Timer t;
456  double* ts = new double[o.samples()];
457  bool stopped = false;
458  for (unsigned int s = o.samples(); !stopped && s--; ) {
459  t.start();
460  for (unsigned int k = o.iterations(); !stopped && k--; ) {
461  unsigned int i = o.solutions();
462  Script* s = new Script(o);
463  Search::Options so;
464  so.clone = false;
465  so.threads = o.threads();
466  so.c_d = o.c_d();
467  so.a_d = o.a_d();
468  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
469  false);
470  so.cutoff = createCutoff(o);
471  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
472  {
473  Meta<Engine,Script> e(s,so);
474  do {
475  Script* ex = e.next();
476  if (ex == NULL)
477  break;
478  delete ex;
479  } while (--i != 0);
480  if (e.stopped())
481  stopped = true;
482  }
483  delete so.stop;
484  }
485  ts[s] = t.stop() / o.iterations();
486  }
487  if (stopped) {
488  l_out << "\tSTOPPED" << endl;
489  } else {
490  double m = am(ts,o.samples());
491  double d = dev(ts,o.samples()) * 100.0;
492  l_out << "\truntime: "
493  << setw(20) << right
494  << showpoint << fixed
495  << setprecision(6) << m << "ms"
496  << setprecision(2) << " (" << d << "% deviation)"
497  << endl;
498  }
499  delete [] ts;
500  }
501  break;
502  }
503  } catch (Exception& e) {
504  cerr << "Exception: " << e.what() << "." << endl
505  << "Stopping..." << endl;
506  if (sol_file.is_open())
507  sol_file.close();
508  if (log_file.is_open())
509  log_file.close();
510  exit(EXIT_FAILURE);
511  }
512  if (sol_file.is_open())
513  sol_file.close();
514  if (log_file.is_open())
515  log_file.close();
516  }
517 
518 }}
519 
520 // STATISTICS: driver-any
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:458
Restart with linear sequence.
Definition: driver.hh:112
double am(double t[], int n)
Compute arithmetic mean of n elements in t.
Definition: script.cpp:78
NodeType t
Type of node.
Definition: bool-expr.cpp:234
unsigned int nogoods_limit
Depth limit for extraction of no-goods.
Definition: search.hh:460
Search engine statistics
Definition: search.hh:136
static std::ostream & select_ostream(const char *name, std::ofstream &ofs)
Choose output stream according to name.
Definition: script.hpp:229
Stop-object based on number of nodes
Definition: search.hh:531
static Cutoff * geometric(unsigned long int scale=1U, double base=1.5)
Definition: cutoff.cpp:164
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:456
Search engine options
Definition: search.hh:449
void abs(Home home, FloatVar x0, FloatVar x1)
Post propagator for .
Definition: arithmetic.cpp:49
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
static void interrupt(int)
Handler for catching Ctrl-C.
Definition: script.hpp:114
Interrupted by user.
Definition: script.hpp:74
virtual void inspect(const Space &node)
Use the print method of the template class S to print a space.
Definition: gist.hpp:145
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:168
static Stop * fail(unsigned long int l)
Stop if failure limit l has been exceeded.
Definition: stop.cpp:51
virtual void compare(const Space &home, std::ostream &os) const
Compare with s.
Definition: script.hpp:225
Search::Cutoff * createCutoff(const Options &o)
Create cutoff object from options.
Definition: script.hpp:157
Computation spaces.
Definition: core.hpp:1362
Parametric base-class for scripts.
Definition: driver.hh:633
Heap heap
The single global heap.
Definition: heap.cpp:49
static Stop * node(unsigned long int l)
Stop if node limit l has been exceeded.
Definition: stop.cpp:47
Gecode::IntSet d(v, 7)
EngineToMeta(T *s, const Search::Options &o)
Definition: script.hpp:249
void start(void)
Start timer.
Definition: timer.hpp:70
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:464
double threads
Number of threads to use.
Definition: search.hh:454
double dev(double t[], int n)
Compute deviation of n elements in t.
Definition: script.cpp:88
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
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
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
static Cutoff * linear(unsigned long int scale=1U)
Create generator for linear sequence scaled by scale.
Definition: cutoff.cpp:156
Stop object based on nodes, failures, and time.
Definition: script.hpp:54
virtual void print(std::ostream &os) const
Print a solution to os.
Definition: script.hpp:221
Measure average runtime.
Definition: driver.hh:100
Wrapper class to add engine template argument.
Definition: script.hpp:247
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:342
static Cutoff * constant(unsigned long int scale=1U)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:152
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:452
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
Definition: stop.cpp:75
#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
~CombinedStop(void)
Destructor.
Definition: script.hpp:130
Print statistics for script.
Definition: driver.hh:101
Restart with geometric sequence.
Definition: driver.hh:114
#define forceinline
Definition: config.hpp:170
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:255
static Cutoff * luby(unsigned long int scale=1U)
Create generator for luby sequence with scale-factor scale.
Definition: cutoff.cpp:160
void restart_base(double base)
Set default restart base.
Definition: options.hpp:333
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:211
Stop * stop
Stop object for stopping search.
Definition: search.hh:462
int explore(Space *root, bool bab, const Options &opt)
Create a new stand-alone Gist for root using bab.
Definition: gist.cpp:105
Gecode toplevel namespace
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:494
Options for Gist
Definition: gist.hh:238
void restart(RestartMode r)
Set default restart mode.
Definition: options.hpp:324
#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:326
Restart with constant sequence.
Definition: driver.hh:111
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition: driver.hh:708
Stop-object based on number of failures
Definition: search.hh:554
virtual bool stop(const Search::Statistics &s, const Search::Options &o)
Test whether search must be stopped.
Definition: script.hpp:77