chocoteam / chocoteam/choco-solver
XCSP3 parser: problems found by the unit tests of PyCSP3 (pow, mod, allDifferent-matrix with except, iff)
- Dominant language
- Java
- Stars
- 779
- Forks
- 159
- Avg merge
- 6d 9h
- Merged PRs (30d)
- 10
Description
This issue gathers the problems found by the unit tests of PyCSP3 with the XCSP3 parser of Choco (`choco-parsers-4.10.15-beta.jar`, the version embedded in PyCSP3). The command is `java -cp choco-parsers-4.10.15-beta.jar org.chocosolver.parser.xcsp.ChocoXCSP model.xml -a -f -flt`.
## 1. pow is unsupported in some intensional constraints
```xml
-3..3
-30..30
eq(pow(x,3),y)
```
**Observed:**
```
java.lang.NullPointerException: Cannot invoke "org.chocosolver.solver.expression.discrete.arithmetic.ArExpression.eq(...)"
Exception in thread "main" java.lang.RuntimeException: UNSUPPORTED
s UNKNOWN
```
The same happens for `eq(y,pow(x,2))` (with `y` in `-3..9`) and for `eq(pow(x,z),y)` (with `z` in `0..2`), whereas `eq(pow(x,2),add(y,3))` is solved.
**Results of the other solvers:**
| Instance | Expected (brute force) | ACE | CHOCO | cosoco |
|---|---|---|---|---|
| `eq(pow(x,3),y)` | 7 solutions | correct: 7 solutions | fails: `java.lang.NullPointerException: Cannot invoke "org.chocosolver.solver.expression.discrete.arithmetic.ArExpression.eq(...` | correct: 7 solutions |
| `eq(y,pow(x,2))` | 7 solutions | correct: 7 solutions | fails: `java.lang.NullPointerException: Cannot invoke "org.chocosolver.solver.expression.discrete.arithmetic.ArExpression.eq(...` | correct: 7 solutions |
| `eq(pow(x,z),y)` | 17 solutions | fails: `java.lang.AssertionError: not implemented` | fails: `java.lang.NullPointerException: Cannot invoke "org.chocosolver.solver.expression.discrete.arithmetic.ArExpression.eq(...` | correct: 17 solutions |
with (ACE 2.6 and CHOCO (choco-parsers-4.10.15-beta), embedded in PyCSP3, and cosoco 2.6.1, from pip: the versions used by PyCSP3):
- 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`
- cosoco: `cosoco model.xml -model=2 -nbsols=0`
**Tests of PyCSP3:** `test_arithmetic_operators[CHOCO-x ** 3 == y]`, `test_arithmetic_operators_with_small_domains[CHOCO-x ** z == y]`, `test_expr[CHOCO-expr("eq", y, expr("pow", x, 2))]` in `pycsp3/tests/test_constraints_intension.py`.
## 2. mod loses the solutions where the dividend is negative and not a multiple of the divisor
```xml
-3..3
-3..3
eq(mod(x,3),y)
```
**Observed:** 5 solutions: `(-3, 0)`, `(0, 0)`, `(1, 1)`, `(2, 2)`, `(3, 0)`.
**Expected:** according to Remark 7 of XCSP3-Core ("rounding towards 0", as in C or Java), 7 solutions: the ones above, and `(-2, -2)` and `(-1, -1)`. No solution is found for `x = -2` and `x = -1` (with the rule "rounding towards negative infinity", `(-2, 1)` and `(-1, 2)` would be expected). Similarly, `eq(y,mod(x,2))` has no solution for `x = -3` and `x = -1`, whereas `eq(div(x,2),y)` is solved as expected.
**Results of the other solvers:**
| Instance | Expected (brute force) | ACE | CHOCO | cosoco |
|---|---|---|---|---|
| `eq(mod(x,3),y)` | 7 solutions | fails: `java.lang.Exception` | wrong: 5 of the 7 expected solutions, and 0 wrong solutions | correct: 7 solutions |
| `eq(y,mod(x,2))` | 7 solutions | fails: `java.lang.Exception` | wrong: 5 of the 7 expected solutions, and 0 wrong solutions | correct: 7 solutions |
| `eq(mod(x,-3),y)` | 7 solutions | fails: `java.lang.Exception` | wrong: 5 of the 7 expected solutions, and 0 wrong solutions | correct: 7 solutions |
with (ACE 2.6 and CHOCO (choco-parsers-4.10.15-beta), embedded in PyCSP3, and cosoco 2.6.1, from pip: the versions used by PyCSP3):
- 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`
- cosoco: `cosoco model.xml -model=2 -nbsols=0`
cosoco finds the expected solutions; ACE fails on these instances (reported in xcsp3team/ACE#12).
**Tests of PyCSP3:** `test_arithmetic_operators[CHOCO-x % 3 == y]`, `test_expr[CHOCO-expr("eq", y, expr("mod", x, 2))]` in `pycsp3/tests/test_constraints_intension.py`.
## 3. allDifferent-matrix with except: solutions are lost
```xml
0..2
x[][]
0
```
**Observed:** some of the expected solutions are not found (see the table below).
**Expected:** the assignments where the values different from 0, on each row and on each column, are all different.
**Results of the three solvers:**
| Instance | Expected (brute force) | ACE | CHOCO | cosoco |
|---|---|---|---|---|
| the instance above | 781 solutions | correct: 781 solutions | wrong: 91 of the 781 expected solutions, and 0 wrong solutions | wrong: 12 of the 781 expected solutions, and 0 wrong solutions |
with `java -jar ACE-2.6.jar model.xml -s=all -xe -xc=false`, `java -cp choco-parsers-4.10.15-beta.jar org.chocosolver.parser.xcsp.ChocoXCSP model.xml -a -f -flt` and `cosoco model.xml -model=2 -nbsols=0` (ACE 2.6 and CHOCO, embedded in PyCSP3, and cosoco 2.6.1, from pip).
ACE finds all the expected solutions; cosoco also loses solutions (reported in xcsp3team/cosoco#78).
**Tests of PyCSP3:** `test_alldifferent_matrix[CHOCO-excepting 0]`, `test_alldifferent_matrix[CHOCO-excepting 0 and 2]` in `pycsp3/tests/test_constraints_global_alldifferent.py`.
---
This issue was found by the unit tests of PyCSP3: https://github.com/xcsp3team/pycsp3/pull/66
Contributor guide
Research direction
Start with the PyCSP3 tests named in the issue: `pycsp3/tests/test_constraints_intension.py` and `pycsp3/tests/test_constraints_global_alldifferent.py`; run the corresponding cases against the Choco XCSP parser command shown in the report. Compare results with the expected solution counts for `pow`, `mod`, and `allDifferent` matrix constraints with exceptions. Done means Choco returns the expected solutions for the reported cases.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- backend
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100