Repository navigation
cardinality: wrong solutions when the number of occurrences of a value is the number of variables #29
Description
When all the variables of a constraint cardinality must be assigned a value v (its number of occurrences is the number of
variables), ACE often gives wrong solutions (never seen when v is the smallest value of the domains):
<instance format="XCSP3" type="CSP">
<variables>
<array id="x" size="[2]"> 0..2 </array>
</variables>
<constraints>
<cardinality>
<list> x[] </list>
<values> 2 </values>
<occurs> 2 </occurs>
</cardinality>
</constraints>
</instance>Observed: 3 solutions, (2, 0), (2, 1) and (2, 2).
Expected: the single solution (2, 2).
| Instance | Expected (brute force) | ACE | CHOCO 4.10.15 and 6.0.2 | cosoco |
|---|---|---|---|---|
x[] (2 variables 0..2), values 2, occurs 2 |
1 solution | wrong: 2 wrong solutions (e.g. (2, 0)) |
correct | correct |
x[] (2 variables 0..4), values 4, occurs 2 |
1 solution | wrong: 4 wrong solutions (e.g. (4, 0)) |
correct | correct |
x[] (3 variables 0..2), values 1, occurs 3 |
1 solution | wrong: 1 wrong solution, (1, 1, 0) |
correct | correct |
x[] (2 variables 0..4), values 4 3, occurs 2 0 |
1 solution | wrong: 3 wrong solutions (e.g. (4, 0)) |
correct | correct |
x[] (2 variables 0..4), values 0, occurs 2 |
1 solution | correct | correct | correct |
x[] (4 variables 0..2), values 2, occurs 4 |
1 solution | correct | correct | correct |
On a grid of instances (2 to 4 variables, domains 0..1 to 0..4, a single value, occurs from 1 to the number of variables), the
wrong solutions only appear when the number of occurrences is the number of variables: for 24 of the 42 such instances (never for
the value 0).
Results obtained with ACE built from the master branch of this repository (83e8b60, embedded in PyCSP3 since xcsp3team/pycsp3#201), CHOCO (choco-parsers-4.10.15-beta, embedded in PyCSP3, and choco-parsers 6.0.2, the latest release, with the same results) and cosoco 2.6.1 (from pip):
- ACE:
java -jar ACE-2.6.jar model.xml -s=all -xe -xc=false - CHOCO:
java -cp choco-parsers-4.10.15-beta.jar org.chocosolver.parser.xcsp.ChocoXCSP model.xml -a -f -flt(6.0.2:-a true) - cosoco:
cosoco model.xml -model=2 -nbsols=0
Cause
The propagator Cardinality (MatcherCardinality, Matcher.java) is concerned: with the decomposition (-g_card=1, a constraint
exactly per value), ACE gives the single expected solution. isSatisfiedBy() is right: the matching does not detect that the
assignment violates the constraint.
Tests
Found while writing the unit tests of PyCSP3: test_cardinality_sizes, test_cardinality_on_expressions and
test_cardinality_on_components in pycsp3/tests/test_constraints_global_cardinality.py: 3 tests.
This issue was found by the unit tests of PyCSP3: xcsp3team/pycsp3#226
Activity
Update the Cardinality tests after the decisions of #226