Generated on Wed Nov 1 15:05:01 2006 for Gecode by doxygen 1.4.5

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 $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_r m$.
void Gecode::count (Space *home, const IntVarArgs &x, IntVar y, IntRelType r, int m, IntConLevel icl=ICL_DEF)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_r m$.
void Gecode::count (Space *home, const IntVarArgs &x, int n, IntRelType r, IntVar z, IntConLevel icl=ICL_DEF)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_r z$.
void Gecode::count (Space *home, const IntVarArgs &x, IntVar y, IntRelType r, IntVar z, IntConLevel icl=ICL_DEF)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_r z$.
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

\begin{eqnarray*} \forall t=(v, lb, ub) \in c: & & lb \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq ub \\ \forall t=(v, unspec_{low}, unspec_{up}) \not\in c: & & unspec_{low} \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq unspec_{up} \end{eqnarray*}

.

void Gecode::gcc (Space *home, const IntVarArgs &x, const IntArgs &c, int m, int unspec, int min, int max, IntConLevel icl)
 Post propagator for

\begin{eqnarray*} \forall t=(v, lb, ub) \in c: & & lb \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq ub \\ \forall t=(v, 0, unspec) \not\in c: & & 0 \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq unspec \end{eqnarray*}

.

void Gecode::gcc (Space *home, const IntVarArgs &x, int lb, int ub, IntConLevel icl)
 Post propagator for $ \forall v \in \displaystyle \bigcup_{i\in\{0, \dots, |x|-1\}} dom(x_i): lb \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq ub $.
void Gecode::gcc (Space *home, const IntVarArgs &x, int ub, IntConLevel icl)
 Post propagator for $ \forall v \in \displaystyle \bigcup_{i\in\{0, \dots, |x|-1\}} dom(x_i): lb = \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} = ub $.
void Gecode::gcc (Space *home, const IntVarArgs &x, const IntVarArgs &c, int min, int max, IntConLevel icl)
 Post propagator for

\begin{eqnarray*} v_j \in I=[min;max] & & \\ \forall j \in \{0, \dots, |I| - 1\}: & & \#\{i\in\{0, \dots, |x| - 1\} | x_i = v_j\} = c_j \end{eqnarray*}

.

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 $ \forall j \in \{0, \dots, |v| - 1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = v_j\} = c_j $.
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 $ \forall j \in \{0, \dots, |v| - 1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = v_j\} = c_j $.

Function Documentation

void Gecode::count (  Space *  home,
const IntVarArgs &  x,
int  n,
IntRelType  r,
int  m,
IntConLevel  icl = ICL_DEF
) 
 

Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_r m$.

Supports domain-consistent propagation only.

Definition at line 27 of file count.cc.

void Gecode::count (  Space *  home,
const IntVarArgs &  x,
IntVar  y,
IntRelType  r,
int  m,
IntConLevel  icl = ICL_DEF
) 
 

Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_r m$.

Supports domain-consistent propagation only.

Definition at line 64 of file count.cc.

void Gecode::count (  Space *  home,
const IntVarArgs &  x,
int  n,
IntRelType  r,
IntVar  z,
IntConLevel  icl = ICL_DEF
) 
 

Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_r z$.

Supports domain-consistent propagation only.

Definition at line 100 of file count.cc.

void Gecode::count (  Space *  home,
const IntVarArgs &  x,
IntVar  y,
IntRelType  r,
IntVar  z,
IntConLevel  icl = ICL_DEF
) 
 

Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_r z$.

Supports domain-consistent propagation only.

Definition at line 137 of file count.cc.

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

\begin{eqnarray*} \forall t=(v, lb, ub) \in c: & & lb \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq ub \\ \forall t=(v, unspec_{low}, unspec_{up}) \not\in c: & & unspec_{low} \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq unspec_{up} \end{eqnarray*}

.

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
Let $ D:=\displaystyle \bigcup_{i\in\{0, \dots, |x|-1\}} dom(x_i)$ and $ V $ the set of values represented by c. Then this progator allows sets $ V\subset D$ as well as $ V=D$ .

In this interface values $ v$ and their cardinality bounds have to specified such that c looks as follows (for example): $ c=[ (1,0,1), (2,1,3), \dots, (10,4,5)]$ , 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 $ \forall {i\in\{0, \dots, |x|-1\}}: dom(x_i) \subseteq I=[min;max]$ .

Definition at line 426 of file gcc.cc.

void Gecode::gcc (  Space *  home,
const IntVarArgs &  x,
const IntArgs &  c,
int  m,
int  unspec,
int  min,
int  max,
IntConLevel  icl
) 
 

Post propagator for

\begin{eqnarray*} \forall t=(v, lb, ub) \in c: & & lb \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq ub \\ \forall t=(v, 0, unspec) \not\in c: & & 0 \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq unspec \end{eqnarray*}

.

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
Let $ D:=\displaystyle \bigcup_{i\in\{0, \dots, |x|-1\}} dom(x_i)$ and $ V $ the set of values represented by c. Then this interface allows to specify sets $ V\subset D$ as well as $ V=D$ .

In this interface values $ v$ and their cardinality bounds have to be specified such that c looks as follows (for example): $ c=[ (1,0,1), (2,1,3), \dots, (10,4,5)]$ , 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.

Definition at line 494 of file gcc.cc.

void Gecode::gcc (  Space *  home,
const IntVarArgs &  x,
int  lb,
int  ub,
IntConLevel  icl
) 
 

Post propagator for $ \forall v \in \displaystyle \bigcup_{i\in\{0, \dots, |x|-1\}} dom(x_i): lb \leq \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} \leq ub $.

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 $ V=D \displaystyle \bigcup_{i\in\{0, \dots, |x|-1\}} dom(x_i)$
icl consistency level

Definition at line 500 of file gcc.cc.

void Gecode::gcc (  Space *  home,
const IntVarArgs &  x,
int  ub,
IntConLevel  icl
) 
 

Post propagator for $ \forall v \in \displaystyle \bigcup_{i\in\{0, \dots, |x|-1\}} dom(x_i): lb = \#\{i\in\{0, \dots, |x| - 1\} | x_i = v\} = ub $.

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 $ V=D \displaystyle \bigcup_{i\in\{0, \dots, |x|-1\}} dom(x_i)$
icl consistency level

Definition at line 522 of file gcc.cc.

void Gecode::gcc (  Space *  home,
const IntVarArgs &  x,
const IntVarArgs &  c,
int  min,
int  max,
IntConLevel  icl
) 
 

Post propagator for

\begin{eqnarray*} v_j \in I=[min;max] & & \\ \forall j \in \{0, \dots, |I| - 1\}: & & \#\{i\in\{0, \dots, |x| - 1\} | x_i = v_j\} = c_j \end{eqnarray*}

.

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
Supports value (icl = ICL_VAL, default), bounds (icl = ICL_BND), and domain-consistency (icl = ICL_DOM).

This interface requires that $ \forall {i\in\{0, \dots, |x|-1\}}: dom(x_i) \subseteq I=[min;max]$ .

Definition at line 528 of file gcc.cc.

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 $ \forall j \in \{0, \dots, |v| - 1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = v_j\} = c_j $.

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 $ I=[min;max]$
min smallest domain value of x
max largest domain value of x
icl consistency level
Supports value (icl = ICL_VAL, default), bounds (icl = ICL_BND), and domain-consistency (icl = ICL_DOM).

This interface requires that $ \forall {i\in\{0, \dots, |x|-1\}}: dom(x_i) \subseteq I=[min;max]$ . If all is set to true, every value from the interval $ I=[min;max]$ is specified with cardinalities. Otherwise, only specified values in v are used and unspecified values may occur between unspec_low and unspec_up times.

Definition at line 594 of file gcc.cc.

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 $ \forall j \in \{0, \dots, |v| - 1\}: \#\{i\in\{0, \dots, |x| - 1\} | x_i = v_j\} = c_j $.

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 $ I=[min;max]$
min smallest domain value of x
max largest domain value of x
icl consistency level
Supports value (icl = ICL_VAL, default), bounds (icl = ICL_BND), and domain-consistency (icl = ICL_DOM).

This interface requires that $ \forall {i\in\{0, \dots, |x|-1\}}: dom(x_i) \subseteq [min, \dots, max]$ . If all is set to true, every value from the interval $ I=[min;max]$ is specified with cardinalities. Otherwise, only specified values in v are used and unspecified values may occur between 0 and unspec times.

Definition at line 587 of file gcc.cc.