Generated on Tue May 22 09:40:13 2018 for Gecode by doxygen 1.6.3

rbs.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 
00035 #include <gecode/search/seq/rbs.hh>
00036 
00037 namespace Gecode { namespace Search { namespace Seq {
00038 
00039   bool
00040   RestartStop::stop(const Statistics& s, const Options& o) {
00041     // Stop if the fail limit for the engine says so
00042     if (s.fail > l) {
00043       e_stopped = true;
00044       m_stat.restart++;
00045       return true;
00046     }
00047     // Stop if the stop object for the meta engine says so
00048     if ((m_stop != NULL) && m_stop->stop(m_stat+s,o)) {
00049       e_stopped = false;
00050       return true;
00051     }
00052     return false;
00053   }
00054 
00055   Space*
00056   RBS::next(void) {
00057     if (restart) {
00058       restart = false;
00059       sslr++;
00060       NoGoods& ng = e->nogoods();
00061       // Reset number of no-goods found
00062       ng.ng(0);
00063       MetaInfo mi(stop->m_stat.restart,sslr,e->statistics().fail,last,ng);
00064       bool r = master->master(mi);
00065       stop->m_stat.nogood += ng.ng();
00066       if (master->status(stop->m_stat) == SS_FAILED) {
00067         stop->update(e->statistics());
00068         delete master;
00069         master = NULL;
00070         e->reset(NULL);
00071         return NULL;
00072       } else if (r) {
00073         stop->update(e->statistics());
00074         Space* slave = master;
00075         master = master->clone();
00076         complete = slave->slave(mi);
00077         e->reset(slave);
00078         sslr = 0;
00079         stop->m_stat.restart++;
00080       }
00081     }
00082     while (true) {
00083       Space* n = e->next();
00084       if (n != NULL) {
00085         // The engine found a solution
00086         restart = true;
00087         delete last;
00088         last = n->clone();
00089         return n;
00090       } else if ( (!complete && !e->stopped()) ||
00091                   (e->stopped() && stop->enginestopped()) ) {
00092         // The engine must perform a true restart
00093         // The number of the restart has been incremented in the stop object
00094         sslr = 0;
00095         NoGoods& ng = e->nogoods();
00096         ng.ng(0);
00097         MetaInfo mi(stop->m_stat.restart,sslr,e->statistics().fail,last,ng);
00098         (void) master->master(mi);
00099         stop->m_stat.nogood += ng.ng();
00100         long unsigned int nl = ++(*co);
00101         stop->limit(e->statistics(),nl);
00102         if (master->status(stop->m_stat) == SS_FAILED)
00103           return NULL;
00104         Space* slave = master;
00105         master = master->clone();
00106         complete = slave->slave(mi);
00107         e->reset(slave);
00108       } else {
00109         return NULL;
00110       }
00111     }
00112     GECODE_NEVER;
00113     return NULL;
00114   }
00115 
00116   Search::Statistics
00117   RBS::statistics(void) const {
00118     return stop->metastatistics()+e->statistics();
00119   }
00120 
00121   void
00122   RBS::constrain(const Space& b) {
00123     if (!best)
00124       throw NoBest("RBS::constrain");
00125     if (last != NULL) {
00126       last->constrain(b);
00127       if (last->status() == SS_FAILED) {
00128         delete last;
00129       } else {
00130         return;
00131       }
00132     }
00133     last = b.clone();
00134     master->constrain(b);
00135     e->constrain(b);
00136   }
00137 
00138   bool
00139   RBS::stopped(void) const {
00140     /*
00141      * What might happen during parallel search is that the
00142      * engine has been stopped but the meta engine has not, so
00143      * the meta engine does not perform a restart. However the
00144      * invocation of next will do so and no restart will be
00145      * missed.
00146      */
00147     return e->stopped();
00148   }
00149 
00150   RBS::~RBS(void) {
00151     delete e;
00152     delete master;
00153     delete last;
00154     delete co;
00155     delete stop;
00156   }
00157 
00158 }}}
00159 
00160 // STATISTICS: search-seq