Generated on Sat Feb 7 2015 02:01:13 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: 2013-07-15 02:49:56 +0200 (Mon, 15 Jul 2013) $ by $Author: tack $
11  * $Revision: 13879 $
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 Space>
210  std::ostream&
211  ScriptBase<Space>::select_ostream(const char* name, std::ofstream& ofs) {
212  if (strcmp(name, "stdout") == 0) {
213  return std::cout;
214  } else if (strcmp(name, "stdlog") == 0) {
215  return std::clog;
216  } else if (strcmp(name, "stderr") == 0) {
217  return std::cerr;
218  } else {
219  ofs.open(name);
220  return ofs;
221  }
222  }
223 
227  template<template<class> class E, class T>
228  class EngineToMeta : public E<T> {
229  public:
230  EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
231  };
232 
233  template<class Space>
234  template<class Script, template<class> class Engine, class Options>
235  void
237  if (o.restart()==RM_NONE) {
238  runMeta<Script,Engine,Options,EngineToMeta>(o,s);
239  } else {
240  runMeta<Script,Engine,Options,RBS>(o,s);
241  }
242  }
243 
244  template<class Space>
245  template<class Script, template<class> class Engine, class Options,
246  template<template<class> class,class> class Meta>
247  void
248  ScriptBase<Space>::runMeta(const Options& o, Script* s) {
249  using namespace std;
250 
251  ofstream sol_file, log_file;
252 
253  ostream& s_out = select_ostream(o.out_file(), sol_file);
254  ostream& l_out = select_ostream(o.log_file(), log_file);
255 
256  try {
257  switch (o.mode()) {
258  case SM_GIST:
259 #ifdef GECODE_HAS_GIST
260  {
261  Gist::Print<Script> pi(o.name());
262  Gist::VarComparator<Script> vc(o.name());
264  opt.inspect.click(&pi);
265  opt.inspect.compare(&vc);
266  opt.clone = false;
267  opt.c_d = o.c_d();
268  opt.a_d = o.a_d();
269  for (int i=0; o.inspect.click(i) != NULL; i++)
270  opt.inspect.click(o.inspect.click(i));
271  for (int i=0; o.inspect.solution(i) != NULL; i++)
272  opt.inspect.solution(o.inspect.solution(i));
273  for (int i=0; o.inspect.move(i) != NULL; i++)
274  opt.inspect.move(o.inspect.move(i));
275  for (int i=0; o.inspect.compare(i) != NULL; i++)
276  opt.inspect.compare(o.inspect.compare(i));
277  if (s == NULL)
278  s = new Script(o);
279  (void) GistEngine<Engine<Script> >::explore(s, opt);
280  }
281  break;
282  // If Gist is not available, fall through
283 #endif
284  case SM_SOLUTION:
285  {
286  l_out << o.name() << endl;
288  int i = o.solutions();
289  t.start();
290  if (s == NULL)
291  s = new Script(o);
292  unsigned int n_p = s->propagators();
293  unsigned int n_b = s->branchers();
294  Search::Options so;
295  so.threads = o.threads();
296  so.c_d = o.c_d();
297  so.a_d = o.a_d();
298  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
299  o.interrupt());
300  so.cutoff = createCutoff(o);
301  so.clone = false;
302  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
303  if (o.interrupt())
305  {
306  Meta<Engine,Script> e(s,so);
307  if (o.print_last()) {
308  Script* px = NULL;
309  do {
310  Script* ex = e.next();
311  if (ex == NULL) {
312  if (px != NULL) {
313  px->print(s_out);
314  delete px;
315  }
316  break;
317  } else {
318  delete px;
319  px = ex;
320  }
321  } while (--i != 0);
322  } else {
323  do {
324  Script* ex = e.next();
325  if (ex == NULL)
326  break;
327  ex->print(s_out);
328  delete ex;
329  } while (--i != 0);
330  }
331  if (o.interrupt())
333  Search::Statistics stat = e.statistics();
334  s_out << endl;
335  if (e.stopped()) {
336  l_out << "Search engine stopped..." << endl
337  << "\treason: ";
338  int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
339  if (r & CombinedStop::SR_INT)
340  l_out << "user interrupt " << endl;
341  else {
342  if (r & CombinedStop::SR_NODE)
343  l_out << "node ";
344  if (r & CombinedStop::SR_FAIL)
345  l_out << "fail ";
346  if (r & CombinedStop::SR_TIME)
347  l_out << "time ";
348  l_out << "limit reached" << endl << endl;
349  }
350  }
351  l_out << "Initial" << endl
352  << "\tpropagators: " << n_p << endl
353  << "\tbranchers: " << n_b << endl
354  << endl
355  << "Summary" << endl
356  << "\truntime: ";
357  stop(t, l_out);
358  l_out << endl
359  << "\tsolutions: "
360  << ::abs(static_cast<int>(o.solutions()) - i) << endl
361  << "\tpropagations: " << stat.propagate << endl
362  << "\tnodes: " << stat.node << endl
363  << "\tfailures: " << stat.fail << endl
364  << "\trestarts: " << stat.restart << endl
365  << "\tno-goods: " << stat.nogood << endl
366  << "\tpeak depth: " << stat.depth << endl
367 #ifdef GECODE_PEAKHEAP
368  << "\tpeak memory: "
369  << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
370  << endl
371 #endif
372  << endl;
373  }
374  delete so.stop;
375  }
376  break;
377  case SM_STAT:
378  {
379  l_out << o.name() << endl;
380  Support::Timer t;
381  int i = o.solutions();
382  t.start();
383  if (s == NULL)
384  s = new Script(o);
385  unsigned int n_p = s->propagators();
386  unsigned int n_b = s->branchers();
387  Search::Options so;
388  so.clone = false;
389  so.threads = o.threads();
390  so.c_d = o.c_d();
391  so.a_d = o.a_d();
392  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
393  o.interrupt());
394  so.cutoff = createCutoff(o);
395  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
396  if (o.interrupt())
398  {
399  Meta<Engine,Script> e(s,so);
400  do {
401  Script* ex = e.next();
402  if (ex == NULL)
403  break;
404  delete ex;
405  } while (--i != 0);
406  if (o.interrupt())
408  Search::Statistics stat = e.statistics();
409  l_out << endl
410  << "\tpropagators: " << n_p << endl
411  << "\tbranchers: " << n_b << endl
412  << "\truntime: ";
413  stop(t, l_out);
414  l_out << endl
415  << "\tsolutions: "
416  << ::abs(static_cast<int>(o.solutions()) - i) << endl
417  << "\tpropagations: " << stat.propagate << endl
418  << "\tnodes: " << stat.node << endl
419  << "\tfailures: " << stat.fail << endl
420  << "\trestarts: " << stat.restart << endl
421  << "\tno-goods: " << stat.nogood << endl
422  << "\tpeak depth: " << stat.depth << endl
423 #ifdef GECODE_PEAKHEAP
424  << "\tpeak memory: "
425  << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
426  << endl
427 #endif
428  << endl;
429  }
430  delete so.stop;
431  }
432  break;
433  case SM_TIME:
434  {
435  l_out << o.name() << endl;
436  Support::Timer t;
437  double* ts = new double[o.samples()];
438  bool stopped = false;
439  for (unsigned int s = o.samples(); !stopped && s--; ) {
440  t.start();
441  for (unsigned int k = o.iterations(); !stopped && k--; ) {
442  unsigned int i = o.solutions();
443  Script* s = new Script(o);
444  Search::Options so;
445  so.clone = false;
446  so.threads = o.threads();
447  so.c_d = o.c_d();
448  so.a_d = o.a_d();
449  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
450  false);
451  so.cutoff = createCutoff(o);
452  so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
453  {
454  Meta<Engine,Script> e(s,so);
455  do {
456  Script* ex = e.next();
457  if (ex == NULL)
458  break;
459  delete ex;
460  } while (--i != 0);
461  if (e.stopped())
462  stopped = true;
463  }
464  delete so.stop;
465  }
466  ts[s] = t.stop() / o.iterations();
467  }
468  if (stopped) {
469  l_out << "\tSTOPPED" << endl;
470  } else {
471  double m = am(ts,o.samples());
472  double d = dev(ts,o.samples()) * 100.0;
473  l_out << "\truntime: "
474  << setw(20) << right
475  << showpoint << fixed
476  << setprecision(6) << m << "ms"
477  << setprecision(2) << " (" << d << "% deviation)"
478  << endl;
479  }
480  delete [] ts;
481  }
482  break;
483  }
484  } catch (Exception& e) {
485  cerr << "Exception: " << e.what() << "." << endl
486  << "Stopping..." << endl;
487  if (sol_file.is_open())
488  sol_file.close();
489  if (log_file.is_open())
490  log_file.close();
491  exit(EXIT_FAILURE);
492  }
493  if (sol_file.is_open())
494  sol_file.close();
495  if (log_file.is_open())
496  log_file.close();
497  }
498 
499 }}
500 
501 // STATISTICS: driver-any
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:213
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:215
Search engine statistics
Definition: search.hh:136
Stop-object based on number of nodes
Definition: search.hh:284
static Cutoff * geometric(unsigned long int scale=1U, double base=1.5)
Definition: cutoff.cpp:230
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:211
Search engine options
Definition: search.hh:204
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
Driver::ScriptBase< Space > Script
Base-class for scripts.
Definition: driver.hh:666
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:389
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:622
Heap heap
The single global heap.
Definition: heap.cpp:49
static std::ostream & select_ostream(const char *name, std::ofstream &ofs)
Choose output stream according to name.
Definition: script.hpp:211
Gecode::IntSet d(v, 7)
EngineToMeta(T *s, const Search::Options &o)
Definition: script.hpp:230
void start(void)
Start timer.
Definition: timer.hpp:70
Cutoff * cutoff
Cutoff for restart-based search.
Definition: search.hh:219
double threads
Number of threads to use.
Definition: search.hh:209
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:222
Stop object based on nodes, failures, and time.
Definition: script.hpp:54
Measure average runtime.
Definition: driver.hh:100
Wrapper class to add engine template argument.
Definition: script.hpp:228
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:324
static Cutoff * constant(unsigned long int scale=1U)
Create generator for constant sequence with constant s.
Definition: cutoff.cpp:218
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:207
virtual bool stop(const Statistics &s, const Options &o)
Return true if failure limit is exceeded.
Definition: stop.cpp:57
#define GECODE_DRIVER_EXPORT
Definition: driver.hh:65
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
virtual void print(std::ostream &os) const
Print a solution to os.
Definition: driver.hh:630
virtual bool stop(const Statistics &s, const Options &o)
Return true if node limit is exceeded.
Definition: stop.cpp:47
static Cutoff * luby(unsigned long int scale=1U)
Create generator for luby sequence with scale-factor scale.
Definition: cutoff.cpp:226
void restart_base(double base)
Set default restart base.
Definition: options.hpp:315
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
static void run(const Options &opt, Script *s=NULL)
Definition: script.hpp:236
Stop * stop
Stop object for stopping search.
Definition: search.hh:217
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:326
Base-class for Stop-object.
Definition: search.hh:262
Options for Gist
Definition: gist.hh:238
void restart(RestartMode r)
Set default restart mode.
Definition: options.hpp:306
#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:67
Options for scripts
Definition: driver.hh:326
Restart with constant sequence.
Definition: driver.hh:111
Stop-object based on number of failures
Definition: search.hh:307
virtual bool stop(const Search::Statistics &s, const Search::Options &o)
Test whether search must be stopped.
Definition: script.hpp:77