lex: java.lang.Exception when a single position remains once removed the positions with the same variable in both lists #20

The constraint lex fails when, once removed the positions where the same variable is in both lists, a single position remains.

<instance format="XCSP3" type="CSP">
  <variables>
    <array id="x" size="[3]"> 0..2 </array>
  </variables>
  <constraints>
    <lex>
      <list> x[0] x[1] </list>
      <list> x[0] x[2] </list>
      <operator> le </operator>
    </lex>
  </constraints>
</instance>

Observed: ! ERROR: and no solution, and with -ev:

java.lang.Exception
	at constraints.global.Lexicographic$LexicographicVar.<init>(Lexicographic.java:162)
	at constraints.global.Lexicographic$LexicographicLE.<init>(Lexicographic.java:237)
	at constraints.global.Lexicographic.buildFrom(Lexicographic.java:49)
	at problem.Problem.lexSimple(Problem.java:2462)
	at problem.XCSP3.buildCtrLex(XCSP3.java:509)

Lexicographic.buildFrom() removes (rightly) the positions where the same variable is in both lists (here, x[0]), and then builds a LexicographicLE (or LexicographicLT) on the remaining lists x[1] and x[2], whose constructor controls 1 < half. The same happens with ACE built from the current source (3a6cd59).

Expected: the 18 solutions such that (x[0], x[1]) <=lex (x[0], x[2]), that is to say x[1] <= x[2] (a binary constraint could be posted when a single position remains). With three positions, one of them with the same variable (x[0] x[1] x[2] and x[0] x[2] x[1]), ACE finds the expected solutions.

Results of the three solvers

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

Found by the unit tests of PyCSP3 (branch tests-lexincreasing-lexdecreasing, xcsp3team/pycsp3#141), where test_lex_with_a_shared_variable for the lists [x[0], x[1]], [x[0], x[2]] (4 tests, one for each operator) is marked as an expected failure with ACE, in test_constraints_global_lexincreasing_lexdecreasing.py, whose model is

x = VarArray(size=3, dom=range(3))

satisfy(
    LexIncreasing([x[0], x[1]], [x[0], x[2]])
)

This issue was found by the unit tests of PyCSP3: xcsp3team/pycsp3#141