Gecode::Int::GCC::Bnd< Card > Class Template Reference
Other available functionality » Integer propagators

Bounds consistent global cardinality propagator. More...

`#include <gcc.hh>`

## Public Member Functions

virtual Actor * | copy (Space &home)
| Copy propagator during cloning.
virtual PropCost | cost (const Space &home, const ModEventDelta &med) const
| Cost funtion.
virtual void | reschedule (Space &home)
| Schedule function.
virtual ExecStatus | propagate (Space &home, const ModEventDelta &med)
| Perform propagation.
virtual size_t | dispose (Space &home)
| Destructor.
ModEventDelta | modeventdelta (void) const
| Return the modification event delta.
virtual ExecStatus | advise (Space &home, Advisor &a, const Delta &d)
| Advise function.
virtual void | advise (Space &home, Advisor &a)
| Run advisor a to be run on failure in failed space.
double | afc (void) const
| Return the accumlated failure count.
unsigned int | id (void) const
| Return propagator id.
PropagatorGroup | group (void) const
| Return group propagator belongs to.
void | group (PropagatorGroup g)
| Add propagator to group g.
bool | disabled (void) const
| Whether propagator is currently disabled.
virtual | ~Actor (void)
| To avoid warnings.

## Static Public Member Functions

static ExecStatus | post (Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
| Post propagator for views x and cardinalities k.
static void * | operator new (size_t s, Space &home)
| Allocate memory from space.
static void | operator delete (void *p, Space &home)
| No-op for exceptions.
static void * | operator new (size_t s)
| Not used.
static void | operator delete (void *p)
| Not used.

## Protected Member Functions

| Bnd (Space &home, Bnd< Card > &p)
| Constructor for cloning p.
ExecStatus | pruneCards (Space &home)
| Prune cardinality variables with 0 maximum occurrence.
ExecStatus | lbc (Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
| Lower Bounds constraint (LBC) stating Hence the lbc constraints the variables such that every value occurs at least as often as specified by its lower cardinality bound.
ExecStatus | ubc (Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
| Upper Bounds constraint (UBC) stating Hence the ubc constraints the variables such that no value occurs more often than specified by its upper cardinality bound.
| Bnd (Home home, ViewArray< IntView > &, ViewArray< Card > &, bool, bool)
| Constructor for posting.
Protected Member Functions inherited from Gecode::Propagator
| Propagator (Home home)
| Constructor for posting.
| Propagator (Space &home, Propagator &p)
| Constructor for cloning p.
Propagator * | fwd (void) const
| Return forwarding pointer during copying.
Kernel::GPI::Info & | gpi (void)
| Provide access to global propagator information.

## Protected Attributes

ViewArray< IntView > | x
| Views on which to perform bounds-propagation.
ViewArray< IntView > | y
| Views on which to perform value-propagation (subset of `x`).
ViewArray< Card > | k
| Array containing either fixed cardinalities or CardViews.
PartialSum< Card > | lps
| Data structure storing the sum of the views lower bounds Necessary for reasoning about the interval capacities in the propagation algorithm.
PartialSum< Card > | ups
| Data structure storing the sum of the views upper bounds.
bool | card_fixed
| Stores whether cardinalities are all assigned.
bool | skip_lbc
| Stores whether the minium required occurences of the cardinalities are all zero. If so, we do not need to perform lower bounds propagation.

## Detailed Description

template<class Card>
class Gecode::Int::GCC::Bnd< Card >

Bounds consistent global cardinality propagator.

The algorithm is taken from: Claude-Guy Quimper, Peter van Beek, Alejandro López-Ortiz, Alexander Golynski, and Sayyed Bashir Sadjad. An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint, CP 2003, pages 600-614.

This implementation uses the code that is provided by Peter Van Beek: http://ai.uwaterloo.ca/~vanbeek/software/software.html The code 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).

The Bnd class is used to post the propagator and BndImp is the actual implementation taking shared variables into account.

Requires

#include <gecode/int/gcc.hh>
gcc.hh

Definition at line 113 of file gcc.hh.

## Constructor & Destructor Documentation

## Bnd() [1/2]

template<class Card>

Gecode::Int::GCC::Bnd< Card >::Bnd | ( | Space & | home,
|  | Bnd< Card > & | p )

inline protected

Constructor for cloning p.

Definition at line 55 of file bnd.hpp.

## Bnd() [2/2]

template<class Card>

Gecode::Int::GCC::Bnd< Card >::Bnd | ( | Home | home,
|  | ViewArray< IntView > & | x0,
|  | ViewArray< Card > & | k0,
|  | bool | cf,
|  | bool | nolbc )

inline protected

Constructor for posting.

Definition at line 44 of file bnd.hpp.

## Member Function Documentation

## pruneCards()

template<class Card>

ExecStatus Gecode::Int::GCC::Bnd< Card >::pruneCards | ( | Space & | home | ) |

protected

Prune cardinality variables with 0 maximum occurrence.

Definition at line 562 of file bnd.hpp.

## lbc()

template<class Card>

ExecStatus Gecode::Int::GCC::Bnd< Card >::lbc | ( | Space & | home,
|  | int & | nb,
|  | HallInfo | hall[],
|  | Rank | rank[],
|  | int | mu[],
|  | int | nu[] )

inline protected

Lower Bounds constraint (LBC) stating Hence the lbc constraints the variables such that every value occurs at least as often as specified by its lower cardinality bound.

Parameters

  home | current space
  nb | denotes number of unique bounds
  hall | contains information about the hall structure of the problem (cf. HallInfo)
  rank | ranking information about the variable bounds (cf. Rank)
  mu | permutation such that
  nu | permutation such that

Definition at line 100 of file bnd.hpp.

## ubc()

template<class Card>

ExecStatus Gecode::Int::GCC::Bnd< Card >::ubc | ( | Space & | home,
|  | int & | nb,
|  | HallInfo | hall[],
|  | Rank | rank[],
|  | int | mu[],
|  | int | nu[] )

inline protected

Upper Bounds constraint (UBC) stating Hence the ubc constraints the variables such that no value occurs more often than specified by its upper cardinality bound.

Parameters

  home | current space
  nb | denotes number of unique bounds
  hall | contains information about the hall structure of the problem (cf. HallInfo)
  rank | ranking information about the variable bounds (cf. Rank)
  mu | permutation such that
  nu | permutation such that

Definition at line 404 of file bnd.hpp.

## copy()

template<class Card>

Actor * Gecode::Int::GCC::Bnd< Card >::copy | ( | Space & | home | ) |

virtual

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 75 of file bnd.hpp.

## cost()

template<class Card>

PropCost Gecode::Int::GCC::Bnd< Card >::cost | ( | const Space & | home,
|  | const ModEventDelta & | med ) const

virtual

Cost funtion.

Implements Gecode::Propagator.

Definition at line 81 of file bnd.hpp.

## reschedule()

template<class Card>

void Gecode::Int::GCC::Bnd< Card >::reschedule | ( | Space & | home | ) |

virtual

Schedule function.

Implements Gecode::Propagator.

Definition at line 93 of file bnd.hpp.

## propagate()

template<class Card>

ExecStatus Gecode::Int::GCC::Bnd< Card >::propagate | ( | Space & | home,
|  | const ModEventDelta & | med )

virtual

Perform propagation.

Implements Gecode::Propagator.

Definition at line 596 of file bnd.hpp.

## dispose()

template<class Card>

size_t Gecode::Int::GCC::Bnd< Card >::dispose | ( | Space & | home | ) |

inline virtual

Destructor.

Reimplemented from Gecode::Actor.

Definition at line 66 of file bnd.hpp.

## post()

template<class Card>

ExecStatus Gecode::Int::GCC::Bnd< Card >::post | ( | Home | home,
|  | ViewArray< IntView > & | x,
|  | ViewArray< Card > & | k )

static

Post propagator for views x and cardinalities k.

Definition at line 808 of file bnd.hpp.

## Member Data Documentation

## x

template<class Card>

ViewArray<IntView> Gecode::Int::GCC::Bnd< Card >::x

protected

Views on which to perform bounds-propagation.

Definition at line 116 of file gcc.hh.

## y

template<class Card>

ViewArray<IntView> Gecode::Int::GCC::Bnd< Card >::y

protected

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

Definition at line 118 of file gcc.hh.

## k

template<class Card>

ViewArray<Card> Gecode::Int::GCC::Bnd< Card >::k

protected

Array containing either fixed cardinalities or CardViews.

Definition at line 120 of file gcc.hh.

## lps

template<class Card>

PartialSum<Card> Gecode::Int::GCC::Bnd< Card >::lps

protected

Data structure storing the sum of the views lower bounds Necessary for reasoning about the interval capacities in the propagation algorithm.

Definition at line 126 of file gcc.hh.

## ups

template<class Card>

PartialSum<Card> Gecode::Int::GCC::Bnd< Card >::ups

protected

Data structure storing the sum of the views upper bounds.

Definition at line 128 of file gcc.hh.

## card_fixed

template<class Card>

bool Gecode::Int::GCC::Bnd< Card >::card_fixed

protected

Stores whether cardinalities are all assigned.

If all cardinalities are assigned the propagation algorithm only has to perform propagation for the upper bounds.

Definition at line 135 of file gcc.hh.

## skip_lbc

template<class Card>

bool Gecode::Int::GCC::Bnd< Card >::skip_lbc

protected

Stores whether the minium required occurences of the cardinalities are all zero. If so, we do not need to perform lower bounds propagation.

Definition at line 141 of file gcc.hh.

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

- gecode/int/gcc.hh
- gecode/int/gcc/bnd.hpp