Gecode::Int::GCC::Bnd< Card > Class Template Reference
[Integer propagators]

Bounds consistent global cardinality propagator. More...

#include <gcc.hh>

Public Member Functions
virtual Actor *	copy (Space &home, bool share)
	Copy propagator during cloning.
virtual PropCost	cost (const Space &home, const ModEventDelta &med) const
	Cost funtion.
virtual ExecStatus	propagate (Space &home, const ModEventDelta &med)
	Perform propagation.
virtual size_t	dispose (Space &home)
	Destructor.
Static Public Member Functions
static ExecStatus	post (Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
	Post propagator for views x and cardinalities k.
Protected Member Functions
	Bnd (Space &home, bool share, 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 $\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.
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.
	Bnd (Home home, ViewArray< IntView > &, ViewArray< Card > &, bool, bool)
	Constructor for posting.
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>

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
	)			`[inline, protected]`

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
	)			`[inline, protected]`

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 ) [inline, 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[]
	)			`[inline, protected]`

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:

	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 $\mu$ such that $\forall i\in \{0, \dots, \|x\|-2\}: max(x_{\mu(i)}) \leq max(x_{\mu(i+1)})$
	nu	permutation $\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[]
	)			`[inline, protected]`

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:

	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 $\mu$ such that $\forall i\in \{0, \dots, \|x\|-2\}: max(x_{\mu(i)}) \leq max(x_{\mu(i+1)})$
	nu	permutation $\nu$ such that $\forall i\in \{0, \dots, \|x\|-2\}: min(x_{\mu(i)}) \leq min(x_{\mu(i+1)})$