Generated on Sat Feb 7 2015 02:01:47 for Gecode by doxygen 1.8.9.1
Gecode::Int::GCC::Bnd< Card > Class Template Reference

Bounds consistent global cardinality propagator. More...

#include <gcc.hh>

Public Member Functions

virtual Actorcopy (Space &home, bool share)
 Copy propagator during cloning. More...
 
virtual PropCost cost (const Space &home, const ModEventDelta &med) const
 Cost funtion. More...
 
virtual ExecStatus propagate (Space &home, const ModEventDelta &med)
 Perform propagation. More...
 
virtual size_t dispose (Space &home)
 Destructor. More...
 
- Public Member Functions inherited from Gecode::Propagator
ModEventDelta modeventdelta (void) const
 Return the modification event delta. More...
 
virtual ExecStatus advise (Space &home, Advisor &a, const Delta &d)
 Advise function. More...
 
double afc (const Space &home) const
 Return the accumlated failure count. More...
 
- Public Member Functions inherited from Gecode::Actor

Static Public Member Functions

static ExecStatus post (Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
 Post propagator for views x and cardinalities k. More...
 
- Static Public Member Functions inherited from Gecode::Actor
static void * operator new (size_t s, Space &home)
 Allocate memory from space. More...
 
static void operator delete (void *p, Space &home)
 No-op for exceptions. More...
 

Protected Member Functions

 Bnd (Space &home, bool share, Bnd< Card > &p)
 Constructor for cloning p. More...
 
ExecStatus pruneCards (Space &home)
 Prune cardinality variables with 0 maximum occurrence. More...
 
ExecStatus lbc (Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
 Lower Bounds constraint (LBC) stating $ \forall j \in \{0, \dots, |k|-1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \geq min(k_j)$ Hence the lbc constraints the variables such that every value occurs at least as often as specified by its lower cardinality bound. More...
 
ExecStatus ubc (Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[])
 Upper Bounds constraint (UBC) stating $ \forall j \in \{0, \dots, |k|-1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \leq max(k_j)$ Hence the ubc constraints the variables such that no value occurs more often than specified by its upper cardinality bound. More...
 
 Bnd (Home home, ViewArray< IntView > &, ViewArray< Card > &, bool, bool)
 Constructor for posting. More...
 
- Protected Member Functions inherited from Gecode::Propagator
 Propagator (Home home)
 Constructor for posting. More...
 
 Propagator (Space &home, bool share, Propagator &p)
 Constructor for cloning p. More...
 
Propagatorfwd (void) const
 Return forwarding pointer during copying. More...
 

Protected Attributes

ViewArray< IntViewx
 Views on which to perform bounds-propagation. More...
 
ViewArray< IntViewy
 Views on which to perform value-propagation (subset of x) More...
 
ViewArray< Card > k
 Array containing either fixed cardinalities or CardViews. More...
 
PartialSum< Card > lps
 Data structure storing the sum of the views lower bounds Necessary for reasoning about the interval capacities in the propagation algorithm. More...
 
PartialSum< Card > ups
 Data structure storing the sum of the views upper bounds. More...
 
bool card_fixed
 Stores whether cardinalities are all assigned. More...
 
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. More...
 

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>

Definition at line 115 of file gcc.hh.

Constructor & Destructor Documentation

template<class Card >
Gecode::Int::GCC::Bnd< Card >::Bnd ( Space home,
bool  share,
Bnd< Card > &  p 
)
inlineprotected

Constructor for cloning p.

Definition at line 60 of file bnd.hpp.

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

Constructor for posting.

Definition at line 49 of file bnd.hpp.

Member Function Documentation

template<class Card >
ExecStatus Gecode::Int::GCC::Bnd< Card >::pruneCards ( Space home)
protected

Prune cardinality variables with 0 maximum occurrence.

Definition at line 559 of file bnd.hpp.

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

Lower Bounds constraint (LBC) stating $ \forall j \in \{0, \dots, |k|-1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \geq min(k_j)$ Hence the lbc constraints the variables such that every value occurs at least as often as specified by its lower cardinality bound.

Parameters
homecurrent space
nbdenotes number of unique bounds
hallcontains information about the hall structure of the problem (cf. HallInfo)
rankranking information about the variable bounds (cf. Rank)
mupermutation $ \mu $ such that $ \forall i\in \{0, \dots, |x|-2\}: max(x_{\mu(i)}) \leq max(x_{\mu(i+1)})$
nupermutation $ \nu $ such that $ \forall i\in \{0, \dots, |x|-2\}: min(x_{\mu(i)}) \leq min(x_{\mu(i+1)})$

Definition at line 97 of file bnd.hpp.

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

Upper Bounds constraint (UBC) stating $ \forall j \in \{0, \dots, |k|-1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = card(k_j)\} \leq max(k_j)$ Hence the ubc constraints the variables such that no value occurs more often than specified by its upper cardinality bound.

Parameters
homecurrent space
nbdenotes number of unique bounds
hallcontains information about the hall structure of the problem (cf. HallInfo)
rankranking information about the variable bounds (cf. Rank)
mupermutation $ \mu $ such that $ \forall i\in \{0, \dots, |x|-2\}: max(x_{\mu(i)}) \leq max(x_{\mu(i+1)})$
nupermutation $ \nu $ such that $ \forall i\in \{0, \dots, |x|-2\}: min(x_{\mu(i)}) \leq min(x_{\mu(i+1)})$

Definition at line 401 of file bnd.hpp.

template<class Card >
Actor * Gecode::Int::GCC::Bnd< Card >::copy ( Space home,
bool  share 
)
virtual

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 79 of file bnd.hpp.

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 85 of file bnd.hpp.

template<class Card >
ExecStatus Gecode::Int::GCC::Bnd< Card >::propagate ( Space home,
const ModEventDelta med 
)
virtual

Perform propagation.

Implements Gecode::Propagator.

Definition at line 593 of file bnd.hpp.

template<class Card >
size_t Gecode::Int::GCC::Bnd< Card >::dispose ( Space home)
inlinevirtual

Destructor.

Reimplemented from Gecode::Actor.

Definition at line 70 of file bnd.hpp.

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 805 of file bnd.hpp.

Member Data Documentation

template<class Card>
ViewArray<IntView> Gecode::Int::GCC::Bnd< Card >::x
protected

Views on which to perform bounds-propagation.

Definition at line 118 of file gcc.hh.

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 120 of file gcc.hh.

template<class Card>
ViewArray<Card> Gecode::Int::GCC::Bnd< Card >::k
protected

Array containing either fixed cardinalities or CardViews.

Definition at line 122 of file gcc.hh.

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 128 of file gcc.hh.

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 130 of file gcc.hh.

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 137 of file gcc.hh.

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 143 of file gcc.hh.


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