pbs.hh
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2015
*
* 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.
*
*/
#ifndef __GECODE_SEARCH_PAR_PBS_HH__
#define __GECODE_SEARCH_PAR_PBS_HH__
#include <gecode/search.hh>
namespace Gecode { namespace Search { namespace Par {
class GECODE_SEARCH_EXPORT PortfolioStop : public Stop {
private:
Stop* so;
volatile bool* tostop;
public:
PortfolioStop(Stop* so);
void share(volatile bool* ts);
virtual bool stop(const Statistics& s, const Options& o);
void stop(bool s);
bool stop(void) const;
};
// Forward declaration
template<class Collect>
class PBS;
template<class Collect>
class GECODE_SEARCH_EXPORT Slave : public Support::Runnable {
protected:
PBS<Collect>* master;
Engine* slave;
Stop* stop;
public:
Slave(PBS<Collect>* m, Engine* s, Stop* so);
Statistics statistics(void) const;
bool stopped(void) const;
void constrain(const Space& b);
virtual void run(void);
virtual ~Slave(void);
};
class CollectAll {
protected:
Support::DynamicQueue<Space*,Heap> solutions;
public:
static const bool best = false;
CollectAll(void);
bool add(Space* s, Slave<CollectAll>* r);
bool constrain(const Space& b);
bool empty(void) const;
Space* get(Slave<CollectAll>*& r);
~CollectAll(void);
};
class CollectBest {
protected:
Space* b;
Slave<CollectBest>* reporter;
public:
static const bool best = true;
CollectBest(void);
bool add(Space* s, Slave<CollectBest>* r);
bool constrain(const Space& b);
bool empty(void) const;
Space* get(Slave<CollectBest>*& r);
~CollectBest(void);
};
template<class Collect>
class GECODE_SEARCH_EXPORT PBS : public Engine {
friend class Slave<Collect>;
protected:
Statistics stat;
Slave<Collect>** slaves;
unsigned int n_slaves;
unsigned int n_active;
bool slave_stop;
volatile bool tostop;
Collect solutions;
Support::Mutex m;
unsigned int n_busy;
Support::Event idle;
bool report(Slave<Collect>* slave, Space* s);
public:
PBS(Engine** s, Stop** so, unsigned int n, const Statistics& stat);
virtual Space* next(void);
virtual Statistics statistics(void) const;
virtual bool stopped(void) const;
virtual void constrain(const Space& b);
virtual ~PBS(void);
};
}}}
#include <gecode/search/par/pbs.hpp>
#endif
// STATISTICS: search-par
Gecode::Search::Options
Search engine options
Definition search.hh:746
Gecode::Search::Par::CollectAll::get
Space * get(Slave< CollectAll > *&r)
Return solution reported by r.
Definition pbs.hpp:57
Gecode::Search::Par::CollectAll::empty
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:53
Gecode::Search::Par::CollectAll::solutions
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition pbs.hh:94
Gecode::Search::Par::CollectAll::add
bool add(Space *s, Slave< CollectAll > *r)
Add a solution a reported by r and always return true.
Definition pbs.hpp:43
Gecode::Search::Par::CollectAll::CollectAll
CollectAll(void)
Initialize.
Definition pbs.hpp:40
Gecode::Search::Par::CollectAll::~CollectAll
~CollectAll(void)
Destructor.
Definition pbs.hpp:61
Gecode::Search::Par::CollectAll::best
static const bool best
Whether it collects best solutions.
Definition pbs.hh:97
Gecode::Search::Par::CollectAll::constrain
bool constrain(const Space &b)
Dummy function.
Definition pbs.hpp:48
Gecode::Search::Par::CollectBest::CollectBest
CollectBest(void)
Initialize.
Definition pbs.hpp:68
Gecode::Search::Par::CollectBest::best
static const bool best
Whether it collects best solutions.
Definition pbs.hh:121
Gecode::Search::Par::CollectBest::constrain
bool constrain(const Space &b)
Check whether b better and update accordingly.
Definition pbs.hpp:86
Gecode::Search::Par::CollectBest::empty
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:100
Gecode::Search::Par::CollectBest::add
bool add(Space *s, Slave< CollectBest > *r)
Add a solution s by r and return whether is was better.
Definition pbs.hpp:71
Gecode::Search::Par::CollectBest::get
Space * get(Slave< CollectBest > *&r)
Return solution reported by r (only if a better one was found).
Definition pbs.hpp:104
Gecode::Search::Par::CollectBest::reporter
Slave< CollectBest > * reporter
Who has reported the best solution (NULL if solution has already been reported).
Definition pbs.hh:118
Gecode::Search::Par::CollectBest::~CollectBest
~CollectBest(void)
Destructor.
Definition pbs.hpp:111
Gecode::Search::Par::CollectBest::b
Space * b
Currently best solution.
Definition pbs.hh:116
Gecode::Search::Par::Engine
Parallel depth-first search engine
Definition engine.hh:46
Gecode::Search::Par::Engine::Engine
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:116
Gecode::Search::Par::PBS
Parallel portfolio engine implementation.
Definition pbs.hh:138
Gecode::Search::Par::PBS::stopped
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition pbs.hpp:256
Gecode::Search::Par::PBS::slave_stop
bool slave_stop
Whether a slave has been stopped.
Definition pbs.hh:150
Gecode::Search::Par::PBS::idle
Support::Event idle
Signal that number of busy slaves becomes zero.
Definition pbs.hh:160
Gecode::Search::Par::PBS::report
bool report(Slave< Collect > *slave, Space *s)
Process report from slave, return false if solution was ignored.
Definition pbs.hpp:170
Gecode::Search::Par::PBS::solutions
Collect solutions
Collect solutions in this.
Definition pbs.hh:154
Gecode::Search::Par::PBS::m
Support::Mutex m
Mutex for synchronization.
Definition pbs.hh:156
Gecode::Search::Par::PBS::slaves
Slave< Collect > ** slaves
Slave engines.
Definition pbs.hh:144
Gecode::Search::Par::PBS::n_active
unsigned int n_active
Number of active slave engines.
Definition pbs.hh:148
Gecode::Search::Par::PBS::tostop
volatile bool tostop
Shared stop flag.
Definition pbs.hh:152
Gecode::Search::Par::PBS::n_slaves
unsigned int n_slaves
Number of slave engines.
Definition pbs.hh:146
Gecode::Search::Par::PBS::stat
Statistics stat
Master statistics.
Definition pbs.hh:142
Gecode::Search::Par::PBS::PBS
PBS(Engine **s, Stop **so, unsigned int n, const Statistics &stat)
Initialize.
Definition pbs.hpp:155
Gecode::Search::Par::PBS::constrain
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition pbs.hpp:272
Gecode::Search::Par::PBS::next
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped).
Definition pbs.hpp:210
Gecode::Search::Par::PBS::statistics
virtual Statistics statistics(void) const
Return statistics.
Definition pbs.hpp:262
Gecode::Search::Par::PBS::n_busy
unsigned int n_busy
Number of busy slaves.
Definition pbs.hh:158
Gecode::Search::Par::PortfolioStop::share
void share(volatile bool *ts)
Set pointer to shared tostop variable.
Definition pbs.hpp:121
Gecode::Search::Par::PortfolioStop::stop
virtual bool stop(const Statistics &s, const Options &o)
Return true if portfolio engine must be stopped.
Definition pbs.cpp:39
Gecode::Search::Par::PortfolioStop::stop
void stop(bool s)
Signal whether search must be stopped.
Gecode::Search::Par::PortfolioStop::PortfolioStop
PortfolioStop(Stop *so)
Initialize.
Definition pbs.hpp:117
Gecode::Search::Par::PortfolioStop::stop
bool stop(void) const
Whether search must be stopped.
Gecode::Search::Par::Slave
Runnable slave of a portfolio master.
Definition pbs.hh:67
Gecode::Search::Par::Slave::slave
Engine * slave
The slave engine.
Definition pbs.hh:72
Gecode::Search::Par::Slave::master
PBS< Collect > * master
The master engine.
Definition pbs.hh:70
Gecode::Search::Par::Slave::run
virtual void run(void)
Perform one run.
Definition pbs.hpp:201
Gecode::Search::Par::Slave::stopped
bool stopped(void) const
Check whether slave has been stopped.
Definition pbs.hpp:137
Gecode::Search::Par::Slave::statistics
Statistics statistics(void) const
Return statistics of slave.
Definition pbs.hpp:132
Gecode::Search::Par::Slave::Slave
Slave(PBS< Collect > *m, Engine *s, Stop *so)
Initialize with master m, slave s, and its stop object so.
Definition pbs.hpp:128
Gecode::Search::Par::Slave::constrain
void constrain(const Space &b)
Constrain with better solution b.
Definition pbs.hpp:142
Gecode::Search::Par::Slave::stop
Stop * stop
Stop object.
Definition pbs.hh:74
Gecode::Search::Statistics
Search engine statistics
Definition search.hh:147
Gecode::Search::Stop
Base-class for Stop-object.
Definition search.hh:799
Gecode::Search::Stop::Stop
Stop(void)
Default constructor.
Definition stop.hpp:41
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::DynamicQueue
Queue with arbitrary number of elements.
Definition dynamic-queue.hpp:42
Gecode::Support::Event
An event for synchronization.
Definition thread.hpp:215
Gecode::Support::Mutex
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
Gecode::Support::Runnable
An interface for objects that can be run by a thread.
Definition thread.hpp:264
Gecode::Search::Par
Definition bab.hh:39
Gecode::Search
Search engines
Gecode
Gecode toplevel namespace
pbs.hpp
search.hh
GECODE_SEARCH_EXPORT
#define GECODE_SEARCH_EXPORT
Definition search.hh:67