Generated on for Gecode by doxygen 1.17.0

Topics

 Stop-objects for stopping search

Namespaces

namespace  Gecode::Search::Config
 Search configuration

Classes

class  Gecode::Search::Statistics
 Search engine statistics More...
class  Gecode::Search::Cutoff
 Base class for cutoff generators for restart-based meta engine. More...
class  Gecode::Search::CutoffConstant
 Cutoff generator for constant sequence. More...
class  Gecode::Search::CutoffLinear
 Cutoff generator for linear sequence. More...
class  Gecode::Search::CutoffLuby
 Cutoff generator for the Luby sequence. More...
class  Gecode::Search::CutoffGeometric
 Cutoff generator for the geometric sequence. More...
class  Gecode::Search::CutoffRandom
 Cutoff generator for the random sequence. More...
class  Gecode::Search::CutoffAppend
 Cutoff generator appending two cutoff generators. More...
class  Gecode::Search::CutoffMerge
 Cutoff generator merging two cutoff generators. More...
class  Gecode::Search::CutoffRepeat
 Cutoff generator that repeats a cutoff from another cutoff generator. More...
class  Gecode::Search::WorkerControl
 External control for the requested number of search workers. More...
class  Gecode::Search::Options
 Search engine options More...
class  Gecode::DFS< T >
 Depth-first search engine. More...
class  Gecode::Search::HeuristicGuidance
 Guidance for heuristic search engines (experimental). More...
class  Gecode::AStar< T >
 A* search engine (experimental). More...
class  Gecode::CABS< T >
 Complete anytime beam search engine (experimental). More...
class  Gecode::BAB< T >
 Depth-first branch-and-bound search engine. More...
class  Gecode::LDS< T >
 Limited discrepancy search engine. More...
class  Gecode::RBS< T, E >
 Meta-engine performing restart-based search. More...
class  Gecode::PBS< T, E >
 Meta engine using a portfolio of search engines. More...

Functions

template<class T>
T * Gecode::bab (T *s, const Search::Options &o=Search::Options::def)
 Perform depth-first branch-and-bound search for subclass T of space s and options o.
template<class T>
T * Gecode::lds (T *s, const Search::Options &o=Search::Options::def)
 Invoke limited-discrepancy search for s as root node and optionso.
template<class T, template< class > class E>
T * Gecode::rbs (T *s, const Search::Options &o)
 Perform restart-based search.
template<class T, template< class > class E>
T * Gecode::pbs (T *s, const Search::Options &o=Search::Options::def)
 Run a portfolio of search engines.

Detailed Description

Defines search engines. All search engines (but Gecode::LDS, where it is not needed) support recomputation. The behaviour of recomputation is controlled by a passing a search option object (see the class Gecode::Search::Options).

Requires

Function Documentation

◆ bab()

template<class T>
T * Gecode::bab ( T * s,
const Search::Options & o = Search::Options::def )
inline

Perform depth-first branch-and-bound search for subclass T of space s and options o.

Additionally, s must implement a member function

virtual void constrain(const T& t)

Whenever exploration requires to add a constraint to the space c currently being explored, the engine executes c.constrain(t) where t is the so-far best solution.

Definition at line 77 of file bab.hpp.

◆ lds()

template<class T>
T * Gecode::lds ( T * s,
const Search::Options & o = Search::Options::def )

Invoke limited-discrepancy search for s as root node and optionso.

Returning nullptr does not prove that there is no solution when the discrepancy limit has been reached, see LDS.

Definition at line 74 of file lds.hpp.

◆ rbs()

template<class T, template< class > class E>
T * Gecode::rbs ( T * s,
const Search::Options & o )
inline

Perform restart-based search.

The engine uses the Cutoff sequence supplied in the options o to periodically restart the search of engine E.

The class T can implement member functions

virtual bool master(const MetaInfo& mi)
Information passed by meta search engines.
Definition core.hpp:1635

and

virtual bool slave(const MetaInfo& mi)

Whenever exploration restarts or a solution is found, the engine executes the functions on the master and slave space. For more details, consult "Modeling and Programming with Gecode".

Definition at line 132 of file rbs.hpp.

◆ pbs()

template<class T, template< class > class E>
T * Gecode::pbs ( T * s,
const Search::Options & o = Search::Options::def )
inline

Run a portfolio of search engines.

The engine will run a portfolio with a number of assets as defined by the options o. The engine supports parallel execution of assets by using the number of threads as defined by the options. An external worker control is supported only when o selects one asset. PBS does not implement worker-allocation policy.

The class T can implement member functions

virtual bool master(const MetaInfo& mi)

and

virtual bool slave(const MetaInfo& mi)

When the assets are created, these functions are executed. For more details, consult "Modeling and Programming with Gecode".

Definition at line 618 of file pbs.hpp.