Adding a hybrid table constraint

[cprudhom]

See also discussion #1004. Add new table constraint that manages hybrid (aka smart) tuples.

A tuple is a set of ints which denotes a possible (or impossible) combination for a set of variables. A table constraint is based on a set of tuples, and at least one of them hold in a solution (DNF-like).

A hybrid tuple is an extension of tuples to set of expressions like eq(2), gt(col(0)) or ne(col(2).add(2)). This makes possible to define intension relationships between variables/columns of a table constraints. For example, this is how a allEqual(x,y,z) constraint can be formulated:

HybridTuples tuples = new HybridTuples();
tuples.add(any(), col(0), col(0));
model.table(new IntVar[]{x, y, z}, tuples).post();

Here is a way to define a reified equality (x = y) <=> b:

HybridTuples tuples = new HybridTuples();
tuples.add(any(), eq(col(0)), eq(1));
tuples.add(any(), ne(col(0)), eq(0));
model.table(new IntVar[]{x, y, b}, tuples).post();

This implementation is based on STR2.

[cprudhom]

@martins-avots

[cprudhom]

There is space for improvement, because some expressions, like col(i), are not bijective. For instance:

IntVar x = model.intVar("x", 1, 10);
IntVar y = model.intVar("y", 2 3);
HybridTuples tuples = new HybridTuples();
tuples.add(any(), col(0));

at propagation, the domain of x will not be reduced to [2,3].

I suppose this question the design choice.

[gadavidd]

@cprudhom the hybrid table with ReExpression suits the majority of applications supported by Smart Table, but do you think it's possible to add another operation like Logical expressions, ∈𝑆 and ∉𝑆? I think that it is a great option to include more than one value for the same variable/column. Somethings like this:

       HybridTuples tuples = new HybridTuples();
       tuples.add(eq(1), in(1,3), none(1,3,5));
       model.table(new IntVar[]{x, y, z}, tuples).post();

       int[] s = {1,2,3};

       HybridTuples tuples = new HybridTuples();
       tuples.add(xor(1,2), in(s), none(4,5,6));
       model.table(new IntVar[]{x, y, z}, tuples).post();

[cprudhom]

I change the way tuples provide support for variables, and now it reaches the right level of filtering. It makes possible to connect two variables: one variable refers to another one.

From now on, the following expressions are enabled (c is a constant, i is an index):

• unary expressions: any(), eq(c), ne(c), ge(c), gt(c), le(c), lt(c), in(c1, c2, c3), nin(c1, c2, c3), col(i)
• binary expressions: eq(col(i), c), ne(col(i)), ne(col(i), c), ge(col(i)), ge(col(i), c), gt(col(i)), gt(col(i), c), le(col(i)), le(col(i), c), lt(col(i)), lt(col(i), c)

Now, the expressions can certainly be extended to more complex expressions, involving three or more variables, or other operators.