rbs.cpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Guido Tack, 2012
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <gecode/search/seq/rbs.hh>
namespace Gecode { namespace Search { namespace Seq {
bool
RestartStop::stop(const Statistics& s, const Options& o) {
// Stop if the fail limit for the engine says so
if (s.fail > l) {
e_stopped = true;
m_stat.restart++;
return true;
}
// Stop if the stop object for the meta engine says so
if ((m_stop != NULL) && m_stop->stop(m_stat+s,o)) {
e_stopped = false;
return true;
}
return false;
}
Space*
RBS::next(void) {
if (restart) {
restart = false;
sslr++;
NoGoods& ng = e->nogoods();
// Reset number of no-goods found
ng.ng(0);
MetaInfo mi(stop->m_stat.restart,sslr,e->statistics().fail,last,ng);
bool r = master->master(mi);
stop->m_stat.nogood += ng.ng();
if (master->status(stop->m_stat) == SS_FAILED) {
stop->update(e->statistics());
delete master;
master = NULL;
e->reset(NULL);
return NULL;
} else if (r) {
stop->update(e->statistics());
Space* slave = master;
master = master->clone();
complete = slave->slave(mi);
e->reset(slave);
sslr = 0;
stop->m_stat.restart++;
}
}
while (true) {
Space* n = e->next();
if (n != NULL) {
// The engine found a solution
restart = true;
delete last;
last = n->clone();
return n;
} else if ( (!complete && !e->stopped()) ||
(e->stopped() && stop->enginestopped()) ) {
// The engine must perform a true restart
// The number of the restart has been incremented in the stop object
sslr = 0;
NoGoods& ng = e->nogoods();
ng.ng(0);
MetaInfo mi(stop->m_stat.restart,sslr,e->statistics().fail,last,ng);
(void) master->master(mi);
stop->m_stat.nogood += ng.ng();
long unsigned int nl = ++(*co);
stop->limit(e->statistics(),nl);
if (master->status(stop->m_stat) == SS_FAILED)
return NULL;
Space* slave = master;
master = master->clone();
complete = slave->slave(mi);
e->reset(slave);
} else {
return NULL;
}
}
GECODE_NEVER;
return NULL;
}
Search::Statistics
RBS::statistics(void) const {
return stop->metastatistics()+e->statistics();
}
void
RBS::constrain(const Space& b) {
if (!best)
throw NoBest("RBS::constrain");
if (last != NULL) {
last->constrain(b);
if (last->status() == SS_FAILED) {
delete last;
} else {
return;
}
}
last = b.clone();
master->constrain(b);
e->constrain(b);
}
bool
RBS::stopped(void) const {
/*
* What might happen during parallel search is that the
* engine has been stopped but the meta engine has not, so
* the meta engine does not perform a restart. However the
* invocation of next will do so and no restart will be
* missed.
*/
return e->stopped();
}
RBS::~RBS(void) {
delete e;
delete master;
delete last;
delete co;
delete stop;
}
}}}
// STATISTICS: search-seq
Gecode::MetaInfo
Information passed by meta search engines.
Definition core.hpp:1613
Gecode::NoGoods
No-goods recorded from restarts.
Definition core.hpp:1588
Gecode::NoGoods::ng
unsigned long int ng(void) const
Return number of no-goods posted.
Definition core.hpp:3055
Gecode::Search::NoBest
Exception: Best solution search is not supported
Definition exception.hpp:60
Gecode::Search::Options
Search engine options
Definition search.hh:746
Gecode::Search::Seq::RBS::stop
RestartStop * stop
The stop control object.
Definition rbs.hh:83
Gecode::Search::Seq::RBS::next
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped).
Definition rbs.cpp:56
Gecode::Search::Seq::RBS::best
bool best
Whether the engine performs best solution search.
Definition rbs.hh:93
Gecode::Search::Seq::RBS::master
Space * master
The master space to restart from.
Definition rbs.hh:77
Gecode::Search::Seq::RBS::restart
bool restart
Whether a restart must be performed when next is called.
Definition rbs.hh:91
Gecode::Search::Seq::RBS::complete
bool complete
Whether search for the next solution will be complete.
Definition rbs.hh:89
Gecode::Search::Seq::RBS::e
Engine * e
The actual engine.
Definition rbs.hh:75
Gecode::Search::Seq::RBS::stopped
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition rbs.cpp:139
Gecode::Search::Seq::RBS::constrain
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition rbs.cpp:122
Gecode::Search::Seq::RBS::last
Space * last
The last solution space (possibly NULL).
Definition rbs.hh:79
Gecode::Search::Seq::RBS::sslr
unsigned long int sslr
How many solutions since the last restart.
Definition rbs.hh:85
Gecode::Search::Seq::RBS::co
Cutoff * co
The cutoff object.
Definition rbs.hh:81
Gecode::Search::Seq::RBS::~RBS
virtual ~RBS(void)
Destructor.
Definition rbs.cpp:150
Gecode::Search::Seq::RBS::statistics
virtual Statistics statistics(void) const
Return statistics.
Definition rbs.cpp:117
Gecode::Search::Seq::RestartStop::stop
virtual bool stop(const Statistics &s, const Options &o)
Return true if meta engine must be stopped.
Definition rbs.cpp:40
Gecode::Search::Statistics
Search engine statistics
Definition search.hh:147
Gecode::Search::Statistics::fail
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::slave
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition core.cpp:863
Gecode::Space::clone
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode::Search::Seq
Definition pbs.cpp:36
Gecode::Search
Search engines
Gecode
Gecode toplevel namespace
rbs.hh
GECODE_NEVER
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56