Generated on for Gecode by doxygen 1.17.0

Guidance for heuristic search engines (experimental). More...

#include <gecode/search.hh>

Public Types

enum  Sense { MINIMIZE , MAXIMIZE }
 Objective direction. More...
typedef std::function< std::int64_t(const Space &)> Evaluate
 Function evaluating a stable space.

Public Member Functions

 HeuristicGuidance (Sense s, Evaluate b, Evaluate r=Evaluate())
 Initialize guidance.

Public Attributes

Sense sense
 Objective direction.
Evaluate bound
 Optimistic objective bound (required).
Evaluate rank
 Node rank (optional, lower first).
std::function< bool(const Space &, const Space &)> dominates
 Whether the first space dominates the second (optional).
std::function< std::size_t(const Space &)> dominance_key
 Dominance key (optional).

Detailed Description

Guidance for heuristic search engines (experimental).

The bound is an optimistic objective value for a stable space: a lower bound when minimizing, an upper bound when maximizing, and the exact objective for a solution. It must agree with the model's constrain function. The optional rank orders nodes (lower first) but is never used for pruning.

The optional dominance predicate returns whether every completion of the second space is matched by a completion of the first that is not worse. It must be transitive. CABS uses it to prune nodes in the same layer. If a dominance key is given, only nodes with equal keys are compared. Without a key, every node offered to the beam is compared with every node already in it.

A* and CABS clone and propagate every child of every node they expand, also close to the root where domains are large. The cost of a node is thus a clone plus propagation at shallow depth, so models should use propagators that stay cheap there.

Callbacks must only read the space passed to them. With several threads they can run concurrently.

Definition at line 1259 of file search.hh.

Member Typedef Documentation

◆ Evaluate

typedef std::function<std::int64_t(const Space&)> Gecode::Search::HeuristicGuidance::Evaluate

Function evaluating a stable space.

Definition at line 1264 of file search.hh.

Member Enumeration Documentation

◆ Sense

Objective direction.

Enumerator
MINIMIZE 
MAXIMIZE 

Definition at line 1262 of file search.hh.

Constructor & Destructor Documentation

◆ HeuristicGuidance()

Gecode::Search::HeuristicGuidance::HeuristicGuidance ( Sense s,
Evaluate b,
Evaluate r = Evaluate() )
inline

Initialize guidance.

Definition at line 1276 of file search.hh.

Member Data Documentation

◆ sense

Sense Gecode::Search::HeuristicGuidance::sense

Objective direction.

Definition at line 1266 of file search.hh.

◆ bound

Evaluate Gecode::Search::HeuristicGuidance::bound

Optimistic objective bound (required).

Definition at line 1268 of file search.hh.

◆ rank

Evaluate Gecode::Search::HeuristicGuidance::rank

Node rank (optional, lower first).

Definition at line 1270 of file search.hh.

◆ dominates

std::function<bool(const Space&,const Space&)> Gecode::Search::HeuristicGuidance::dominates

Whether the first space dominates the second (optional).

Definition at line 1272 of file search.hh.

◆ dominance_key

std::function<std::size_t(const Space&)> Gecode::Search::HeuristicGuidance::dominance_key

Dominance key (optional).

Definition at line 1274 of file search.hh.


The documentation for this class was generated from the following file: