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 ![]() | |
ExecStatus | ubc (Space &home, int &nb, HallInfo hall[], Rank rank[], int mu[], int nu[]) |
Upper Bounds constraint (UBC) stating ![]() | |
Bnd (Home home, ViewArray< IntView > &, ViewArray< Card > &, bool, bool) | |
Constructor for posting. | |
![]() | |
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. | |
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
|
inlineprotected |
|
inlineprotected |
|
protected |
|
inlineprotected |
Lower Bounds constraint (LBC) stating
|
inlineprotected |
Upper Bounds constraint (UBC) stating
|
virtual |
|
virtual |
|
virtual |
|
virtual |
|
inlinevirtual |
|
static |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |
|
protected |