Gecode::Int::GCC::Bnd< Card > Class Template Reference
[Integer propagators]
Bounds consistent global cardinality propagator.
More...
#include <gcc.hh>
List of all members.
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 void  reschedule (Space &home) 
 Schedule function.

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 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 Attributes 
ViewArray< IntView >  x 
 Views on which to perform boundspropagation.

ViewArray< IntView >  y 
 Views on which to perform valuepropagation (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: ClaudeGuy Quimper, Peter van Beek, Alejandro LópezOrtiz, Alexander Golynski, and Sayyed Bashir Sadjad. An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint, CP 2003, pages 600614.
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/nonidempotent 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
Definition at line 117 of file gcc.hh.
Constructor & Destructor Documentation
Constructor for cloning p.
Definition at line 60 of file bnd.hpp.
Constructor for posting.
Definition at line 49 of file bnd.hpp.
Member Function Documentation
Prune cardinality variables with 0 maximum occurrence.
Definition at line 566 of file bnd.hpp.
Post propagator for views x and cardinalities k.
Definition at line 812 of file bnd.hpp.
Member Data Documentation
Views on which to perform boundspropagation.
Definition at line 120 of file gcc.hh.
Views on which to perform valuepropagation (subset of x
).
Definition at line 122 of file gcc.hh.
Array containing either fixed cardinalities or CardViews.
Definition at line 124 of file gcc.hh.
Data structure storing the sum of the views lower bounds Necessary for reasoning about the interval capacities in the propagation algorithm.
Definition at line 130 of file gcc.hh.
Data structure storing the sum of the views upper bounds.
Definition at line 132 of file gcc.hh.
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 139 of file gcc.hh.
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 145 of file gcc.hh.
The documentation for this class was generated from the following files: