Generated on Sat Aug 25 2012 15:53:12 for Gecode by doxygen 1.7.5
Gecode::Int::Distinct::Bnd Class Reference

Bounds consistent distinct propagator. More...

#include <distinct.hh>

List of all members.

Public Member Functions

virtual ExecStatus propagate (Space &home, const ModEventDelta &med)
 Perform propagation.
virtual PropCost cost (const Space &home, const ModEventDelta &med) const
 Cost function.
virtual Actorcopy (Space &home, bool share)
 Copy propagator during cloning.
virtual size_t dispose (Space &home)
 Destructor.

Static Public Member Functions

static ExecStatus post (Home home, ViewArray< View > &x)
 Post propagator for view array x.

Protected Member Functions

 Bnd (Home home, ViewArray< View > &x)
 Constructor for posting.
 Bnd (Space &home, bool share, Bnd< View > &p)
 Constructor for cloning p.

Protected Attributes

ViewArray< View > x
 Views on which to perform bounds-propagation.
ViewArray< View > y
 Views on which to perform value-propagation (subset of x)
int min_x
 Minimum (approximation) of view in x.
int max_x
 Maximum (approximation) of view in x.

Detailed Description

Bounds consistent distinct propagator.

The propagator uses staging: first it uses naive value-based propagation and only then uses bounds consistent propagation. Due to using naive value-based propagation, the propagator might actually achieve stronger consistency than just bounds consistency.

The algorithm is taken from: A. Lopez-Ortiz, C.-G. Quimper, J. Tromp, and P. van Beek. A fast and simple algorithm for bounds consistency of the alldifferent constraint. IJCAI-2003.

This implementation uses the code that is provided by Peter Van Beek: http://ai.uwaterloo.ca/~vanbeek/software/software.html The code (originally by John Tromp) here has only been slightly modified to fit Gecode (taking idempotent/non-idempotent propagation into account) and uses a more efficient layout of datastructures (keeping the number of different arrays small).

Requires


Constructor & Destructor Documentation

Gecode::Int::Distinct::Bnd::Bnd ( Home  home,
ViewArray< View > &  x 
) [inline, protected]

Constructor for posting.

Definition at line 42 of file bnd.hpp.

Gecode::Int::Distinct::Bnd::Bnd ( Space home,
bool  share,
Bnd< View > &  p 
) [inline, protected]

Constructor for cloning p.

Definition at line 68 of file bnd.hpp.


Member Function Documentation

ExecStatus Gecode::Int::Distinct::Bnd::post ( Home  home,
ViewArray< View > &  x 
) [static]

Post propagator for view array x.

Definition at line 433 of file bnd.hpp.

ExecStatus Gecode::Int::Distinct::Bnd::propagate ( Space home,
const ModEventDelta med 
) [virtual]

Perform propagation.

Implements Gecode::Propagator.

Definition at line 355 of file bnd.hpp.

PropCost Gecode::Int::Distinct::Bnd::cost ( const Space home,
const ModEventDelta med 
) const [virtual]

Cost function.

If in stage for naive value propagation, the cost is low linear. Otherwise it is low quadratic.

Implements Gecode::Propagator.

Definition at line 82 of file bnd.hpp.

Actor * Gecode::Int::Distinct::Bnd::copy ( Space home,
bool  share 
) [virtual]

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 76 of file bnd.hpp.

size_t Gecode::Int::Distinct::Bnd::dispose ( Space home) [inline, virtual]

Destructor.

Reimplemented from Gecode::Actor.

Definition at line 60 of file bnd.hpp.


Member Data Documentation

Views on which to perform bounds-propagation.

Definition at line 132 of file distinct.hh.

Views on which to perform value-propagation (subset of x)

Definition at line 134 of file distinct.hh.

Minimum (approximation) of view in x.

Definition at line 136 of file distinct.hh.

Maximum (approximation) of view in x.

Definition at line 138 of file distinct.hh.


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