chocoteam / chocoteam/choco-solver

XCSP3 parser: problems found by the unit tests of PyCSP3 (pow, mod, allDifferent-matrix with except, iff)

Open
#1,248 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.