Cardinality constraints
[Using finite domain integers]
Collaboration diagram for Cardinality constraints:
![]() |
Detailed Description
- Note:
- Domain consistency on the extended cardinality variables of the Global Cardinality Propagator is only obtained if they are bounds consistent, otherwise the problem of enforcing domain consistency on the cardinality variables is NP-complete as proved by Qumiper et. al. in Improved Algorithms for the Global Cardinality Constraint"
Functions | |
void | Gecode::count (Space *home, const IntVarArgs &x, int n, IntRelType r, int m, IntConLevel icl=ICL_DEF) |
Post propagator for ![]() | |
void | Gecode::count (Space *home, const IntVarArgs &x, IntVar y, IntRelType r, int m, IntConLevel icl=ICL_DEF) |
Post propagator for ![]() | |
void | Gecode::count (Space *home, const IntVarArgs &x, int n, IntRelType r, IntVar z, IntConLevel icl=ICL_DEF) |
Post propagator for ![]() | |
void | Gecode::count (Space *home, const IntVarArgs &x, IntVar y, IntRelType r, IntVar z, IntConLevel icl=ICL_DEF) |
Post propagator for ![]() | |
void | Gecode::gcc (Space *home, const IntVarArgs &x, const IntArgs &c, int m, int unspec_low, int unspec_up, int min, int max, IntConLevel icl) |
Post propagator for
| |
void | Gecode::gcc (Space *home, const IntVarArgs &x, const IntArgs &c, int m, int unspec, int min, int max, IntConLevel icl) |
Post propagator for
| |
void | Gecode::gcc (Space *home, const IntVarArgs &x, int lb, int ub, IntConLevel icl) |
Post propagator for ![]() | |
void | Gecode::gcc (Space *home, const IntVarArgs &x, int ub, IntConLevel icl) |
Post propagator for ![]() | |
void | Gecode::gcc (Space *home, const IntVarArgs &x, const IntVarArgs &c, int min, int max, IntConLevel icl) |
Post propagator for
| |
void | Gecode::gcc (Space *home, const IntVarArgs &x, const IntArgs &v, const IntVarArgs &c, int m, int unspec_low, int unspec_up, bool all, int min, int max, IntConLevel icl) |
Post propagator for ![]() | |
void | Gecode::gcc (Space *home, const IntVarArgs &x, const IntArgs &v, const IntVarArgs &c, int m, int unspec, bool all, int min, int max, IntConLevel icl) |
Post propagator for ![]() |
Function Documentation
void Gecode::count | ( | Space * | home, | |
const IntVarArgs & | x, | |||
int | n, | |||
IntRelType | r, | |||
int | m, | |||
IntConLevel | icl = ICL_DEF | |||
) |
void Gecode::count | ( | Space * | home, | |
const IntVarArgs & | x, | |||
IntVar | y, | |||
IntRelType | r, | |||
int | m, | |||
IntConLevel | icl = ICL_DEF | |||
) |
void Gecode::count | ( | Space * | home, | |
const IntVarArgs & | x, | |||
int | n, | |||
IntRelType | r, | |||
IntVar | z, | |||
IntConLevel | icl = ICL_DEF | |||
) |
void Gecode::count | ( | Space * | home, | |
const IntVarArgs & | x, | |||
IntVar | y, | |||
IntRelType | r, | |||
IntVar | z, | |||
IntConLevel | icl = ICL_DEF | |||
) |
void Gecode::gcc | ( | Space * | home, | |
const IntVarArgs & | x, | |||
const IntArgs & | c, | |||
int | m, | |||
int | unspec_low, | |||
int | unspec_up, | |||
int | min, | |||
int | max, | |||
IntConLevel | icl | |||
) |
Post propagator for
.
Supports value (icl = ICL_VAL, default), bounds (icl = ICL_BND), and domain-consistency (icl = ICL_DOM).
- Exceptions:
-
Int::ArgumentSame thrown if x contains shared variables.
- Parameters:
-
x variables on which to perform propagation c specifying cardinality information as shown below m denotes the size of c unspec_low denotes the lower bound for those values not specified in c unspec_up denotes the upper bound for those values not specified in c min smallest domain value of x max largest domain value of x icl consistency level




In this interface values and their cardinality bounds have to specified such that c looks as follows (for example):
, where the value 1 may occur zero times or once, the value 2 must occur at least once at most three times and the value 10 must occur at least 4 times and at most 5 times.
Furthermore, this interface requires that .
void Gecode::gcc | ( | Space * | home, | |
const IntVarArgs & | x, | |||
const IntArgs & | c, | |||
int | m, | |||
int | unspec, | |||
int | min, | |||
int | max, | |||
IntConLevel | icl | |||
) |
Post propagator for
.
Supports value (icl = ICL_VAL, default), bounds (icl = ICL_BND), and domain-consistency (icl = ICL_DOM).
- Exceptions:
-
Int::ArgumentSame thrown if x contains shared variables.
- Parameters:
-
x variables on which to perform propagation c specifying cardinality information as shown below m denotes the size of c unspec denotes the upper bound for those values not specified in c min smallest domain value of x max largest domain value of x icl consistency level




In this interface values and their cardinality bounds have to be specified such that c looks as follows (for example):
, where the value 1 may occur zero times or once, the value 2 must occur at least once at most three times and the value 10 must occur at least 4 times and at most 5 times.
void Gecode::gcc | ( | Space * | home, | |
const IntVarArgs & | x, | |||
int | lb, | |||
int | ub, | |||
IntConLevel | icl | |||
) |
Post propagator for .
Supports value (icl = ICL_VAL, default), bounds (icl = ICL_BND), and domain-consistency (icl = ICL_DOM).
- Exceptions:
-
Int::ArgumentSame thrown if x contains shared variables.
- Parameters:
-
x variables on which to perform propagation lb denotes the lower bound for all values specified in the array c, ub denotes the upper bound for all values specified in the array c, where this interface allows only value sets icl consistency level
void Gecode::gcc | ( | Space * | home, | |
const IntVarArgs & | x, | |||
int | ub, | |||
IntConLevel | icl | |||
) |
Post propagator for .
Supports value (icl = ICL_VAL, default), bounds (icl = ICL_BND), and domain-consistency (icl = ICL_DOM).
- Exceptions:
-
Int::ArgumentSame thrown if x contains shared variables.
- Parameters:
-
x variables on which to perform propagation ub denotes the upper bound for all values specified in the array c, where this interface allows only value sets icl consistency level
void Gecode::gcc | ( | Space * | home, | |
const IntVarArgs & | x, | |||
const IntVarArgs & | c, | |||
int | min, | |||
int | max, | |||
IntConLevel | icl | |||
) |
Post propagator for
.
- Parameters:
-
x variables on which to perform propagation c cardinality variables min smallest domain value of x max largest domain value of x icl consistency level
This interface requires that .
void Gecode::gcc | ( | Space * | home, | |
const IntVarArgs & | x, | |||
const IntArgs & | v, | |||
const IntVarArgs & | c, | |||
int | m, | |||
int | unspec_low, | |||
int | unspec_up, | |||
bool | all, | |||
int | min, | |||
int | max, | |||
IntConLevel | icl | |||
) |
Post propagator for .
- Parameters:
-
x variables on which to perform propagation v containing the values connected to the cardinality variables as specified below c cardinality variables m denotes the size of v and c unspec_low denotes the lower bound for those values not specified in v and c unspec_up denotes the upper bound for those values not specified in v and c all specifies whether the propagator uses all values in the interval min smallest domain value of x max largest domain value of x icl consistency level
This interface requires that . If all is set to true, every value from the interval
is specified with cardinalities. Otherwise, only specified values in v are used and unspecified values may occur between unspec_low and unspec_up times.
void Gecode::gcc | ( | Space * | home, | |
const IntVarArgs & | x, | |||
const IntArgs & | v, | |||
const IntVarArgs & | c, | |||
int | m, | |||
int | unspec, | |||
bool | all, | |||
int | min, | |||
int | max, | |||
IntConLevel | icl | |||
) |
Post propagator for .
- Parameters:
-
x variables on which to perform propagation v containing the values connected to the cardinality variables as specified below c cardinality variables m denotes the size of v and c unspec denotes the upper bound for those values not specified in v and c all specifies whether the propagator uses all values in the interval min smallest domain value of x max largest domain value of x icl consistency level
This interface requires that . If all is set to true, every value from the interval
is specified with cardinalities. Otherwise, only specified values in v are used and unspecified values may occur between 0 and unspec times.