Generated on Thu Nov 2 14:49:37 2006 for Gecode/J by doxygen 1.5.0

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 CardVarNPCompl Qumiper et.

al. in Improved Algorithms for the Global Cardinality Constraint


Functions

static synchronized void org::gecode::Gecode.count (JavaSpace home, VarArray<?extends IntVar > x, int n, IntRelType r, int m, IntConLevel icl)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_r m$.
static synchronized void org::gecode::Gecode.count (JavaSpace home, VarArray<?extends IntVar > x, int n, IntRelType r, int m)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_r m$.
static synchronized void org::gecode::Gecode.count (JavaSpace home, VarArray<?extends IntVar > x, IntVar y, IntRelType r, int m, IntConLevel icl)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_r m$.
static synchronized void org::gecode::Gecode.count (JavaSpace home, VarArray<?extends IntVar > x, IntVar y, IntRelType r, int m)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_r m$.
static synchronized void org::gecode::Gecode.count (JavaSpace home, VarArray<?extends IntVar > x, int n, IntRelType r, IntVar z, IntConLevel icl)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_r z$.
static synchronized void org::gecode::Gecode.count (JavaSpace home, VarArray<?extends IntVar > x, int n, IntRelType r, IntVar z)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=n\}\sim_r z$.
static synchronized void org::gecode::Gecode.count (JavaSpace home, VarArray<?extends IntVar > x, IntVar y, IntRelType r, IntVar z, IntConLevel icl)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_r z$.
static synchronized void org::gecode::Gecode.count (JavaSpace home, VarArray<?extends IntVar > x, IntVar y, IntRelType r, IntVar z)
 Post propagator for $\#\{i\in\{0,\ldots,|x|-1\}\;|\;x_i=y\}\sim_r z$.
static synchronized void org::gecode::Gecode.gcc (JavaSpace home, VarArray<?extends IntVar > x, int[] 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*}

.

static synchronized void org::gecode::Gecode.gcc (JavaSpace home, VarArray<?extends IntVar > x, int[] 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*}

.

static synchronized void org::gecode::Gecode.gcc (JavaSpace home, VarArray<?extends IntVar > 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 $.
static synchronized void org::gecode::Gecode.gcc (JavaSpace home, VarArray<?extends IntVar > 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 $.
static synchronized void org::gecode::Gecode.gcc (JavaSpace home, VarArray<?extends IntVar > x, VarArray<?extends IntVar > 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*}

.

static synchronized void org::gecode::Gecode.gcc (JavaSpace home, VarArray<?extends IntVar > x, int[] v, VarArray<?extends IntVar > c, int m, int unspec_low, int unspec_up, boolean 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 $.
static synchronized void org::gecode::Gecode.gcc (JavaSpace home, VarArray<?extends IntVar > x, int[] v, VarArray<?extends IntVar > c, int m, int unspec, boolean 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

static synchronized void org.gecode.Gecode.count ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int  n,
IntRelType  r,
int  m,
IntConLevel  icl 
) [static, inherited]

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

Supports domain-consistent propagation only.

Definition at line 1261 of file Gecode.java.

static synchronized void org.gecode.Gecode.count ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int  n,
IntRelType  r,
int  m 
) [static, inherited]

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

Supports domain-consistent propagation only.

Definition at line 1271 of file Gecode.java.

static synchronized void org.gecode.Gecode.count ( JavaSpace  home,
VarArray<?extends IntVar >  x,
IntVar  y,
IntRelType  r,
int  m,
IntConLevel  icl 
) [static, inherited]

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

Supports domain-consistent propagation only.

Definition at line 1280 of file Gecode.java.

static synchronized void org.gecode.Gecode.count ( JavaSpace  home,
VarArray<?extends IntVar >  x,
IntVar  y,
IntRelType  r,
int  m 
) [static, inherited]

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

Supports domain-consistent propagation only.

Definition at line 1289 of file Gecode.java.

static synchronized void org.gecode.Gecode.count ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int  n,
IntRelType  r,
IntVar  z,
IntConLevel  icl 
) [static, inherited]

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

Supports domain-consistent propagation only.

Definition at line 1298 of file Gecode.java.

static synchronized void org.gecode.Gecode.count ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int  n,
IntRelType  r,
IntVar  z 
) [static, inherited]

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

Supports domain-consistent propagation only.

Definition at line 1307 of file Gecode.java.

static synchronized void org.gecode.Gecode.count ( JavaSpace  home,
VarArray<?extends IntVar >  x,
IntVar  y,
IntRelType  r,
IntVar  z,
IntConLevel  icl 
) [static, inherited]

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

Supports domain-consistent propagation only.

Definition at line 1316 of file Gecode.java.

static synchronized void org.gecode.Gecode.count ( JavaSpace  home,
VarArray<?extends IntVar >  x,
IntVar  y,
IntRelType  r,
IntVar  z 
) [static, inherited]

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

Supports domain-consistent propagation only.

Definition at line 1325 of file Gecode.java.

static synchronized void org.gecode.Gecode.gcc ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int[]  c,
int  m,
int  unspec_low,
int  unspec_up,
int  min,
int  max,
IntConLevel  icl 
) [static, inherited]

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 1371 of file Gecode.java.

static synchronized void org.gecode.Gecode.gcc ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int[]  c,
int  m,
int  unspec,
int  min,
int  max,
IntConLevel  icl 
) [static, inherited]

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 1410 of file Gecode.java.

static synchronized void org.gecode.Gecode.gcc ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int  lb,
int  ub,
IntConLevel  icl 
) [static, inherited]

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 1436 of file Gecode.java.

static synchronized void org.gecode.Gecode.gcc ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int  ub,
IntConLevel  icl 
) [static, inherited]

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 1461 of file Gecode.java.

static synchronized void org.gecode.Gecode.gcc ( JavaSpace  home,
VarArray<?extends IntVar >  x,
VarArray<?extends IntVar >  c,
int  min,
int  max,
IntConLevel  icl 
) [static, inherited]

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 1488 of file Gecode.java.

static synchronized void org.gecode.Gecode.gcc ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int[]  v,
VarArray<?extends IntVar >  c,
int  m,
int  unspec_low,
int  unspec_up,
boolean  all,
int  min,
int  max,
IntConLevel  icl 
) [static, inherited]

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 1524 of file Gecode.java.

static synchronized void org.gecode.Gecode.gcc ( JavaSpace  home,
VarArray<?extends IntVar >  x,
int[]  v,
VarArray<?extends IntVar >  c,
int  m,
int  unspec,
boolean  all,
int  min,
int  max,
IntConLevel  icl 
) [static, inherited]

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 1557 of file Gecode.java.