[BUG] PropUnionVar has index errors

[jgFages]

Issues

• PropUnionVar may encounter ArrayIndexOutOfBoundsException

• The documentation of
  default Constraint union(SetVar unionSet, int vOffset, SetVar indices, int iOffset, SetVar[] sets)
  does not explain how the offsets are taken into account in the formula. My expectation would be the following :
  sets[i-iOffset]-vOffset, where i in indices, is equal to unionSet.
  but I do not know if this is was indeed the intended implementation.

• Finally, even though I am not 100% sure about the vOffset exact definition, I think that it should somehow intervene in filter1 and filter2, whereas it is not the case.

To Reproduce

@Test(groups = "1s", timeOut = 60000)
public void testUnionBounds() {
    Model model = new Model();
    SetVar[] sets = model.setVarArray("S", 3, new int[]{}, new int[]{2, 3, 5, 6});
    SetVar indices = model.setVar("I", new int[]{}, new int[]{-1, 0, 2, 6});
    SetVar union = model.setVar("U", new int[]{}, new int[]{1, 2, 3, 6, 7});
    model.union(union, indices, sets).post();
    model.getSolver().solve();
}

java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5
	at org.chocosolver.solver/org.chocosolver.solver.constraints.set.PropUnionVar.filter2(PropUnionVar.java:127)

This time with the following code : (array of 2 sets but index set = {0, 1, 2}, I would expect to have no solution as you cannot have 3 indexes for an array of size 2. Instead, the test outputs a solution.

    @Test(groups = "1s", timeOut = 60000)
    public void testUnionWrongBoundsResult() {
        Model model = new Model();
        SetVar[] sets = model.setVarArray("S", 2, new int[]{}, new int[]{0,1,2});
        SetVar indices = model.setVar("I", new int[]{}, new int[]{0,1,2});
        SetVar union = model.setVar("U", new int[]{}, new int[]{0,1});
        model.union(union, indices, sets).post();
        model.getSolver().solve();
        model.getSolver().printStatistics();
    }

gives a solution (whereas it should not). Here vars[2] is actually returning the union variable

    @Test(groups = "1s", timeOut = 60000)
    public void testUnionWrongBoundsResult() {
        Model model = new Model();
        SetVar[] sets = model.setVarArray("S", 2, new int[]{}, new int[]{0,1,2});
        SetVar indices = model.setVar("I", new int[]{0,1,2,3,4,5}, new int[]{0,1,2,3,4,5});
        SetVar union = model.setVar("U", new int[]{}, new int[]{0,1});
        model.union(union, indices, sets).post();
        model.getSolver().solve();
        model.getSolver().printStatistics();
    }

gives a solution (whereas it should not). Here the index set is somehow ignored as it is instantiated.

    @Test(groups = "1s", timeOut = 60000)
    public void testUnionWrongBoundsResult() {
        Model model = new Model();
        SetVar[] sets = model.setVarArray("S", 2, new int[]{}, new int[]{0,1,2});
        SetVar indices = model.setVar("I", new int[]{}, new int[]{0,1,2,3,4});
        SetVar union = model.setVar("U", new int[]{}, new int[]{0,1});
        model.union(union, indices, sets).post();
        model.getSolver().solve();
        model.getSolver().printStatistics();
    }

runs with error... but it would be better to have no solution than a runtime exception.

Possible solution

It will not solve everything but I suggest to remove vOffset to make the code clearer. I think this argument is not necessary as we already have an offset constraint if we really want to shift a set variable (so this can be done outside of this constraint).

The domain of the index set should be filtered according to sets.length and iOffset.

Environment (please complete the following information):

• Choco-solver version: 4.10.12-SNAPSHOT
• JRE : 11

[cprudhom]

Bounds

@Test(groups = "1s", timeOut = 60000)
public void testUnionBounds() {
    Model model = new Model();
    SetVar[] sets = model.setVarArray("S", 3, new int[]{}, new int[]{2, 3, 5, 6});
    SetVar indices = model.setVar("I", new int[]{}, new int[]{-1, 0, 2, 6});
    SetVar union = model.setVar("U", new int[]{}, new int[]{1, 2, 3, 6, 7});
    model.union(union, indices, sets).post();
    model.getSolver().solve();
}

The filtering algorithm is not complete and should remove -1 (assuming iOffset = 0) from indices but also 6 since there are at most 3 sets considered in the union. This will be fixed.

WrongBoundsResult 1

@Test(groups = "1s", timeOut = 60000)
    public void testUnionWrongBoundsResult() {
        Model model = new Model();
        SetVar[] sets = model.setVarArray("S", 2, new int[]{}, new int[]{0,1,2});
        SetVar indices = model.setVar("I", new int[]{}, new int[]{0,1,2});
        SetVar union = model.setVar("U", new int[]{}, new int[]{0,1});
        model.union(union, indices, sets).post();
        model.getSolver().solve();
        model.getSolver().printStatistics();
    }

This time with the following code : (array of 2 sets but index set = {0, 1, 2}, I would expect to have no solution as you cannot have 3 indexes for an array of size 2. Instead, the test outputs a solution.

I believe your test is not complete, because this is a solution:

sets = [({0,1}, {0,1}),({2},{2})]
indices = ({0},{0})
union = ({0,1}, {0,1})

Here, 2 should be removed from indices too, but this should be fixed (see previous point).

WrongBoundsResult 2

@Test(groups = "1s", timeOut = 60000)
    public void testUnionWrongBoundsResult() {
        Model model = new Model();
        SetVar[] sets = model.setVarArray("S", 2, new int[]{}, new int[]{0,1,2});
        SetVar indices = model.setVar("I", new int[]{0,1,2,3,4,5}, new int[]{0,1,2,3,4,5});
        SetVar union = model.setVar("U", new int[]{}, new int[]{0,1});
        model.union(union, indices, sets).post();
        model.getSolver().solve();
        model.getSolver().printStatistics();
    }

gives a solution (whereas it should not).

It doesn't give solution in the current branch.

WrongBoundsResult 3

@Test(groups = "1s", timeOut = 60000)
    public void testUnionWrongBoundsResult() {
        Model model = new Model();
        SetVar[] sets = model.setVarArray("S", 2, new int[]{}, new int[]{0,1,2});
        SetVar indices = model.setVar("I", new int[]{}, new int[]{0,1,2,3,4});
        SetVar union = model.setVar("U", new int[]{}, new int[]{0,1});
        model.union(union, indices, sets).post();
        model.getSolver().solve();
        model.getSolver().printStatistics();
    }

runs with error... but it would be better to have no solution than a runtime exception.

It shouldn't throw any error, a solution to this exists too.

[jgFages]

Thank you Charles ! It seems I was a bit tired indeed.

WrongBoundsResult 1 : you are right it is a wrong example (I wanted to illustrate the fact that at some point in the code (filter2 - vars[i - iOffset]) we may consider the wrong variable. But anyway it was a wrong example.
WrongBoundsResult 2 : my mistake after running it again on master I also have "no solution" which is the expected behavior.