00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #include <iostream>
00040 #include <iomanip>
00041 #include <fstream>
00042 #include <cstring>
00043
00044 #ifndef GECODE_THREADS_WINDOWS
00045 #include <csignal>
00046 #endif
00047
00048 namespace Gecode { namespace Driver {
00049
00054 class CombinedStop : public Search::Stop {
00055 private:
00056 Search::NodeStop* ns;
00057 Search::FailStop* fs;
00058 Search::TimeStop* ts;
00059 GECODE_DRIVER_EXPORT
00060 static bool sigint;
00061
00062 CombinedStop(unsigned int node, unsigned int fail, unsigned int time)
00063 : ns((node > 0) ? new Search::NodeStop(node) : NULL),
00064 fs((fail > 0) ? new Search::FailStop(fail) : NULL),
00065 ts((time > 0) ? new Search::TimeStop(time) : NULL) {
00066 sigint = false;
00067 }
00068 public:
00070 enum {
00071 SR_NODE = 1 << 0,
00072 SR_FAIL = 1 << 1,
00073 SR_TIME = 1 << 2,
00074 SR_INT = 1 << 3
00075 };
00077 virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
00078 return
00079 sigint ||
00080 ((ns != NULL) && ns->stop(s,o)) ||
00081 ((fs != NULL) && fs->stop(s,o)) ||
00082 ((ts != NULL) && ts->stop(s,o));
00083 }
00085 int reason(const Search::Statistics& s, const Search::Options& o) {
00086 return
00087 (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
00088 (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
00089 (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0) |
00090 (sigint ? SR_INT : 0);
00091 }
00093 static Search::Stop*
00094 create(unsigned int node, unsigned int fail, unsigned int time,
00095 bool intr) {
00096 if ( (!intr) && (node == 0) && (fail == 0) && (time == 0))
00097 return NULL;
00098 else
00099 return new CombinedStop(node,fail,time);
00100 }
00101 #ifdef GECODE_THREADS_WINDOWS
00102
00103 static BOOL interrupt(DWORD t) {
00104 if (t == CTRL_C_EVENT) {
00105 sigint = true;
00106 installCtrlHandler(false,true);
00107 return true;
00108 }
00109 return false;
00110 }
00111 #else
00112
00113 static void
00114 interrupt(int) {
00115 sigint = true;
00116 installCtrlHandler(false,true);
00117 }
00118 #endif
00119
00120 static void installCtrlHandler(bool install, bool force=false) {
00121 if (force || !sigint) {
00122 #ifdef GECODE_THREADS_WINDOWS
00123 SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
00124 #else
00125 std::signal(SIGINT, install ? interrupt : SIG_DFL);
00126 #endif
00127 }
00128 }
00130 ~CombinedStop(void) {
00131 delete ns; delete fs; delete ts;
00132 }
00133 };
00134
00139 GECODE_DRIVER_EXPORT void
00140 stop(Support::Timer& t, std::ostream& os);
00141
00145 GECODE_DRIVER_EXPORT double
00146 am(double t[], unsigned int n);
00147
00151 GECODE_DRIVER_EXPORT double
00152 dev(double t[], unsigned int n);
00153
00155 template<class Options>
00156 inline Search::Cutoff*
00157 createCutoff(const Options& o) {
00158 switch (o.restart()) {
00159 case RM_NONE:
00160 return NULL;
00161 case RM_CONSTANT:
00162 return Search::Cutoff::constant(o.restart_scale());
00163 case RM_LINEAR:
00164 return Search::Cutoff::linear(o.restart_scale());
00165 case RM_LUBY:
00166 return Search::Cutoff::luby(o.restart_scale());
00167 case RM_GEOMETRIC:
00168 return Search::Cutoff::geometric(o.restart_scale(),o.restart_base());
00169 default: GECODE_NEVER;
00170 }
00171 return NULL;
00172 }
00173
00174
00175 #ifdef GECODE_HAS_GIST
00176
00180 template<class Engine>
00181 class GistEngine {
00182 public:
00183 static void explore(Space* root, const Gist::Options& opt) {
00184 (void) Gist::dfs(root, opt);
00185 }
00186 };
00187
00189 template<typename S>
00190 class GistEngine<DFS<S> > {
00191 public:
00192 static void explore(S* root, const Gist::Options& opt) {
00193 (void) Gist::dfs(root, opt);
00194 }
00195 };
00196
00198 template<typename S>
00199 class GistEngine<LDS<S> > {
00200 public:
00201 static void explore(S* root, const Gist::Options& opt) {
00202 (void) Gist::dfs(root, opt);
00203 }
00204 };
00205
00207 template<typename S>
00208 class GistEngine<BAB<S> > {
00209 public:
00210 static void explore(S* root, const Gist::Options& opt) {
00211 (void) Gist::bab(root, opt);
00212 }
00213 };
00214
00215 #endif
00216
00217
00218 template<class BaseSpace>
00219 forceinline
00220 ScriptBase<BaseSpace>::ScriptBase(const Options& opt)
00221 : BaseSpace(opt) {}
00222
00223 template<class BaseSpace>
00224 forceinline
00225 ScriptBase<BaseSpace>::ScriptBase(bool share, ScriptBase& e)
00226 : BaseSpace(share,e) {}
00227
00228 template<class BaseSpace>
00229 void
00230 ScriptBase<BaseSpace>::print(std::ostream&) const {}
00231
00232 template<class BaseSpace>
00233 void
00234 ScriptBase<BaseSpace>::compare(const Space&, std::ostream&) const {}
00235
00236 template<class BaseSpace>
00237 std::ostream&
00238 ScriptBase<BaseSpace>::select_ostream(const char* sn, std::ofstream& ofs) {
00239 if (strcmp(sn, "stdout") == 0) {
00240 return std::cout;
00241 } else if (strcmp(sn, "stdlog") == 0) {
00242 return std::clog;
00243 } else if (strcmp(sn, "stderr") == 0) {
00244 return std::cerr;
00245 } else {
00246 ofs.open(sn);
00247 return ofs;
00248 }
00249 }
00250
00251
00255 template<class T, template<class> class E>
00256 class EngineToMeta : public E<T> {
00257 public:
00258 EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
00259 };
00260
00261 template<class BaseSpace>
00262 template<class Script, template<class> class Engine, class Options>
00263 void
00264 ScriptBase<BaseSpace>::run(const Options& o, Script* s) {
00265 if ((o.restart() != RM_NONE) && (o.assets() > 0)) {
00266 std::cerr << "Cannot use restarts and portfolio..." << std::endl;
00267 exit(EXIT_FAILURE);
00268 }
00269 if (o.restart() != RM_NONE) {
00270 runMeta<Script,Engine,Options,RBS>(o,s);
00271 } else if (o.assets() > 0) {
00272 runMeta<Script,Engine,Options,PBS>(o,s);
00273 } else {
00274 runMeta<Script,Engine,Options,EngineToMeta>(o,s);
00275 }
00276 }
00277
00278 template<class BaseSpace>
00279 template<class Script, template<class> class Engine, class Options,
00280 template<class, template<class> class> class Meta>
00281 void
00282 ScriptBase<BaseSpace>::runMeta(const Options& o, Script* s) {
00283 using namespace std;
00284
00285 ofstream sol_file, log_file;
00286
00287 ostream& s_out = select_ostream(o.out_file(), sol_file);
00288 ostream& l_out = select_ostream(o.log_file(), log_file);
00289
00290 try {
00291 switch (o.mode()) {
00292 case SM_GIST:
00293 #ifdef GECODE_HAS_GIST
00294 {
00295 Gist::Print<Script> pi(o.name());
00296 Gist::VarComparator<Script> vc(o.name());
00297 Gist::Options opt;
00298 opt.inspect.click(&pi);
00299 opt.inspect.compare(&vc);
00300 opt.clone = false;
00301 opt.c_d = o.c_d();
00302 opt.a_d = o.a_d();
00303 for (unsigned int i=0; o.inspect.click(i) != NULL; i++)
00304 opt.inspect.click(o.inspect.click(i));
00305 for (unsigned int i=0; o.inspect.solution(i) != NULL; i++)
00306 opt.inspect.solution(o.inspect.solution(i));
00307 for (unsigned int i=0; o.inspect.move(i) != NULL; i++)
00308 opt.inspect.move(o.inspect.move(i));
00309 for (unsigned int i=0; o.inspect.compare(i) != NULL; i++)
00310 opt.inspect.compare(o.inspect.compare(i));
00311 if (s == NULL)
00312 s = new Script(o);
00313 (void) GistEngine<Engine<Script> >::explore(s, opt);
00314 }
00315 break;
00316
00317 #endif
00318 case SM_SOLUTION:
00319 {
00320 l_out << o.name() << endl;
00321 Support::Timer t;
00322 int i = static_cast<int>(o.solutions());
00323 t.start();
00324 if (s == NULL)
00325 s = new Script(o);
00326 unsigned int n_p = PropagatorGroup::all.size(*s);
00327 unsigned int n_b = BrancherGroup::all.size(*s);
00328 Search::Options so;
00329 so.threads = o.threads();
00330 so.c_d = o.c_d();
00331 so.a_d = o.a_d();
00332 so.d_l = o.d_l();
00333 so.assets = o.assets();
00334 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00335 o.interrupt());
00336 so.cutoff = createCutoff(o);
00337 so.clone = false;
00338 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00339 if (o.interrupt())
00340 CombinedStop::installCtrlHandler(true);
00341 {
00342 Meta<Script,Engine> e(s,so);
00343 if (o.print_last()) {
00344 Script* px = NULL;
00345 do {
00346 Script* ex = e.next();
00347 if (ex == NULL) {
00348 if (px != NULL) {
00349 px->print(s_out);
00350 delete px;
00351 }
00352 break;
00353 } else {
00354 delete px;
00355 px = ex;
00356 }
00357 } while (--i != 0);
00358 } else {
00359 do {
00360 Script* ex = e.next();
00361 if (ex == NULL)
00362 break;
00363 ex->print(s_out);
00364 delete ex;
00365 } while (--i != 0);
00366 }
00367 if (o.interrupt())
00368 CombinedStop::installCtrlHandler(false);
00369 Search::Statistics stat = e.statistics();
00370 s_out << endl;
00371 if (e.stopped()) {
00372 l_out << "Search engine stopped..." << endl
00373 << "\treason: ";
00374 int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
00375 if (r & CombinedStop::SR_INT)
00376 l_out << "user interrupt " << endl;
00377 else {
00378 if (r & CombinedStop::SR_NODE)
00379 l_out << "node ";
00380 if (r & CombinedStop::SR_FAIL)
00381 l_out << "fail ";
00382 if (r & CombinedStop::SR_TIME)
00383 l_out << "time ";
00384 l_out << "limit reached" << endl << endl;
00385 }
00386 }
00387 l_out << "Initial" << endl
00388 << "\tpropagators: " << n_p << endl
00389 << "\tbranchers: " << n_b << endl
00390 << endl
00391 << "Summary" << endl
00392 << "\truntime: ";
00393 stop(t, l_out);
00394 l_out << endl
00395 << "\tsolutions: "
00396 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00397 << "\tpropagations: " << stat.propagate << endl
00398 << "\tnodes: " << stat.node << endl
00399 << "\tfailures: " << stat.fail << endl
00400 << "\trestarts: " << stat.restart << endl
00401 << "\tno-goods: " << stat.nogood << endl
00402 << "\tpeak depth: " << stat.depth << endl
00403 #ifdef GECODE_PEAKHEAP
00404 << "\tpeak memory: "
00405 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00406 << endl
00407 #endif
00408 << endl;
00409 }
00410 delete so.stop;
00411 }
00412 break;
00413 case SM_STAT:
00414 {
00415 l_out << o.name() << endl;
00416 Support::Timer t;
00417 int i = static_cast<int>(o.solutions());
00418 t.start();
00419 if (s == NULL)
00420 s = new Script(o);
00421 unsigned int n_p = PropagatorGroup::all.size(*s);
00422 unsigned int n_b = BrancherGroup::all.size(*s);
00423 Search::Options so;
00424 so.clone = false;
00425 so.threads = o.threads();
00426 so.assets = o.assets();
00427 so.c_d = o.c_d();
00428 so.a_d = o.a_d();
00429 so.d_l = o.d_l();
00430 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00431 o.interrupt());
00432 so.cutoff = createCutoff(o);
00433 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00434 if (o.interrupt())
00435 CombinedStop::installCtrlHandler(true);
00436 {
00437 Meta<Script,Engine> e(s,so);
00438 do {
00439 Script* ex = e.next();
00440 if (ex == NULL)
00441 break;
00442 delete ex;
00443 } while (--i != 0);
00444 if (o.interrupt())
00445 CombinedStop::installCtrlHandler(false);
00446 Search::Statistics stat = e.statistics();
00447 l_out << endl
00448 << "\tpropagators: " << n_p << endl
00449 << "\tbranchers: " << n_b << endl
00450 << "\truntime: ";
00451 stop(t, l_out);
00452 l_out << endl
00453 << "\tsolutions: "
00454 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00455 << "\tpropagations: " << stat.propagate << endl
00456 << "\tnodes: " << stat.node << endl
00457 << "\tfailures: " << stat.fail << endl
00458 << "\trestarts: " << stat.restart << endl
00459 << "\tno-goods: " << stat.nogood << endl
00460 << "\tpeak depth: " << stat.depth << endl
00461 #ifdef GECODE_PEAKHEAP
00462 << "\tpeak memory: "
00463 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00464 << endl
00465 #endif
00466 << endl;
00467 }
00468 delete so.stop;
00469 }
00470 break;
00471 case SM_TIME:
00472 {
00473 l_out << o.name() << endl;
00474 Support::Timer t;
00475 double* ts = new double[o.samples()];
00476 bool stopped = false;
00477 for (unsigned int ns = o.samples(); !stopped && ns--; ) {
00478 t.start();
00479 for (unsigned int k = o.iterations(); !stopped && k--; ) {
00480 unsigned int i = o.solutions();
00481 Script* s1 = new Script(o);
00482 Search::Options so;
00483 so.clone = false;
00484 so.threads = o.threads();
00485 so.assets = o.assets();
00486 so.c_d = o.c_d();
00487 so.a_d = o.a_d();
00488 so.d_l = o.d_l();
00489 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00490 false);
00491 so.cutoff = createCutoff(o);
00492 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00493 {
00494 Meta<Script,Engine> e(s1,so);
00495 do {
00496 Script* ex = e.next();
00497 if (ex == NULL)
00498 break;
00499 delete ex;
00500 } while (--i != 0);
00501 if (e.stopped())
00502 stopped = true;
00503 }
00504 delete so.stop;
00505 }
00506 ts[ns] = t.stop() / o.iterations();
00507 }
00508 if (stopped) {
00509 l_out << "\tSTOPPED" << endl;
00510 } else {
00511 double m = am(ts,o.samples());
00512 double d = dev(ts,o.samples()) * 100.0;
00513 l_out << "\truntime: "
00514 << setw(20) << right
00515 << showpoint << fixed
00516 << setprecision(6) << m << "ms"
00517 << setprecision(2) << " (" << d << "% deviation)"
00518 << endl;
00519 }
00520 delete [] ts;
00521 }
00522 break;
00523 }
00524 } catch (Exception& e) {
00525 cerr << "Exception: " << e.what() << "." << endl
00526 << "Stopping..." << endl;
00527 if (sol_file.is_open())
00528 sol_file.close();
00529 if (log_file.is_open())
00530 log_file.close();
00531 exit(EXIT_FAILURE);
00532 }
00533 if (sol_file.is_open())
00534 sol_file.close();
00535 if (log_file.is_open())
00536 log_file.close();
00537 }
00538
00539 }}
00540
00541