Search engines
Functionality by programming task » Programming models

## 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::Options
| Search engine options More...
class | Gecode::DFS< T >
| Depth-first search engine. 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

#include <gecode/search.hh>
search.hh

## 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.

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)
Gecode::MetaInfo
Information passed by meta search engines.
Definition core.hpp:1613

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 111 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.

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 309 of file pbs.hpp.