Table constraints and Smart Tables

[gadavidd]

Hi, I was reading about the Table constraints in choco-solver and have a question. Does Choco-solver have any plan to implement Smart Table Constraints related to the paper "Extending Compact-Table to Basic Smart Tables"?

https://link.springer.com/chapter/10.1007/978-3-319-66158-2_19

[cprudhom]

Hi
This is one of the things I'd like to do, only I get stuck on the tuple declaration part practically in Java/Choco.
As I don't spend much energy on it either (it is not a hot topic to me), I have to admit, it's not going very well...

[martins-avots]

Hi, also I have not worked on table constraints myself yet and
therefore, my offer may not make any sense:

I'm currently working on an optimization framework based on Java,
that uses tables for nearly everything.

Maybe I can help on an architecture/interface level?
Do you have any concrete problems?

[cprudhom]

To me, the main difficulty comes from the modelling aspect.
Indeed, the filtering algorithm is known, and it just needs to be implemented.
So the question is : how to handle ≤ v ≥ v, ∈𝑆 and ∉𝑆 (and probably more complex ones in the future like ≥ x where x is a variable) together with any integer and * in tuples.

In the current version, there is no such question, because tuples can only deal with integers and * (which is an integer value decided by the user).

Model model = new Model();                              
IntVar x = model.intVar(1, 3);                          
IntVar y = model.intVar(1, 3);                          
IntVar z = model.intVar(1, 3);                          
Tuples ts = new Tuples(true);                           
int ST = 99;                                            
ts.setUniversalValue(ST);                               
ts.add(3, ST, 1);                                       
ts.add(1, 2, 3);                                        
ts.add(2, 2, 3);                                        
model.table(new IntVar[]{x, y, z}, ts, "CT+").post();

So I think the first thing to do is to design a smart tuple data structure, presumably only dedicated to smart table (to avoid changing the entire table API), which makes possible to declare smart tuples. May be relying on ReExpression interface can help.
For instance:

Model model = new Model();                              
IntVar x = model.intVar(1, 3);                          
IntVar y = model.intVar(1, 3);                          
IntVar z = model.intVar(1, 3);                          
SmartTuples ts = new SmartTuples();                               
ts.add(eq(3), gt(0), 1);                                       
ts.add(lt(3), 2, 3);                                                                                
model.table(new IntVar[]{x, y, z}, ts, "CTsmart").post();

?

[martins-avots]

So I think the first thing to do is to design a smart tuple data structure, presumably only dedicated to smart table (to avoid changing the entire table API), which makes possible to declare smart tuples.

This also makes it easier to experiment with the new API and to change it later,
if needed, because fewer/no people will be using the new API.

ts.add(eq(3), gt(0), 1);

The problem with that are the different types of parameters.
In order for this to work, it would have to take an Object[] and maybe also store it that way in SmartTuples.
Every time accessing the values of the tuple, one would have to check the type and apply an appropriate behaviour.

2 alternatives come to my mind:

• Use only ReExpression.
  This would mean, that eq(x) would have to be used for all constants.
  This could be combined by posting a normal Tuples and a SmartTuples for a given Model.
• Use 2 tuples for 1 tuple inside SmartTuples,
  where the first one contains only ReExpression instances and
  the second one works similar to the existing Tuples.
  In order to evaluate one tuple of SmartTables one would have to evaluate both tuples at the same time.
  Making each value in the tuple nullable, would probably simplify this approach a bit,
  but I don't know if this approach makes any sense to overhaul.
  This way could also be made compatible to your second example from an interface point of view via add(Object[] arg).

IMHO, the first alternative is much simpler and therefore a first draft is easier to create and to evaluate.

[cprudhom]

I agree, the first the solution is better.
By the way, the creation of such expression should be accessible through a unique class, ideally SmartTuples, which can inherit Tuples (and allow to turn a SmartTuples into a Tuples).

Beware, however, that the ReExpression can be composed in very complex expressions, like eq(z.lt(y).ift(y.pow(2).gt(z), 12)). I don't think we want to deal with that. So introducing a small DSL would be better, accessible directly through SmartTuples and limited to int.

SmartTuples s = new SmartTuples();
s.add(SmartTuples.eq(1), SmartTuples.gt(2), SmartTuples.lt(18));
...

[martins-avots]

I agree, the first the solution is better. By the way, the creation of such expression should be accessible through a unique class, ideally SmartTuples, which can inherit Tuples (and allow to turn a SmartTuples into a Tuples).

Is there a need to be able to convert a SmartTuples to Tuples?

Beware, however, that the ReExpression can be composed in very complex expressions, like eq(z.lt(y).ift(y.pow(2).gt(z), 12)). I don't think we want to deal with that. So introducing a small DSL would be better, accessible directly through SmartTuples and limited to int.

Is the complexity of such an expression is an issue?
Of course, a higher complexity decreases the runtime performance,
but that's always an issue for programmers.
The more complex the model, the lower the performance, in general.

[cprudhom]

I have a first prototype, based on STR2 (not Compact table), that makes possible to deal with simple expressions like: eq(a), ne(a), lt(a), le(a), gt(a), ge(a), * and col(i) where a is a value and i is an column index (of the table).
So, a model like the one defined in the article can be expressed as:

import static org.chocosolver.solver.constraints.extension.hybrid.HybridTuples.*;
//...
Model model = new Model();
IntVar x = model.intVar("x", 1, 3);
IntVar y = model.intVar("y", 1, 3);
IntVar z = model.intVar("z", 1, 3);
int a = 1, b = 2, c = 3;
        
HybridTuples tuples = new HybridTuples();
tuples.add(ne(a), any(), eq(c));
tuples.add(eq(c), le(b), ne(a));
tuples.add(lt(c), eq(b), ne(b));
tuples.add(gt(b), ge(b), any());
        
model.table(new IntVar[]{x, y, z}, tuples).post();
Solver solver = model.getSolver();
solver.setSearch(Search.inputOrderLBSearch(x, y, z));
while (solver.solve()) {
    System.out.printf("(%d, %d, %d)\n",
            x.getValue(), y.getValue(), z.getValue());
}

In particular, one can define allEqual relation like:

Model model = new Model();
IntVar x = model.intVar("x", 1, 3);
IntVar y = model.intVar("y", 1, 3);
IntVar z = model.intVar("z", 1, 3);
        
HybridTuples tuples = new HybridTuples();
tuples.add(any(), col(0), col(0));
        
model.table(new IntVar[]{x, y, z}, tuples).post();
Solver solver = model.getSolver();
solver.setSearch(Search.inputOrderLBSearch(x, y, z));
while (solver.solve()) {
    System.out.printf("(%d, %d, %d)\n",
            x.getValue(), y.getValue(), z.getValue());
}

I'm considering an extension to simple arithmetical relations (like add(_, _) or sub(_, _) where _ could be a value or col(i)), but it is already quite complex.

I have started a minimalist DSL from scratch, not reusing already existing classes (like ReExpression or ArExpression).
The current objective is to make it works, check needs and limitations before going forward.

Soon I will push to a dev branch, if one of you want to play around with the code.

[gadavidd]

Thanks @cprudhom , your work is fantastic!

I have an interesting scenario to test and work with Smart Table, I'm playing around with the code now and will come back with some contributions if there are any.

[martins-avots]

I like the split into arithmetical expressions like le and an expression for accessing a value via col.

[gadavidd]

@cprudhom I think that I found a bug on the arithmetical col(i)

For the same example if I propagate resolution the domains of the variables don't actualize

For example, if I have:

[Model model = new Model();
        IntVar x = model.intVar("x", 1, 3);
        IntVar y = model.intVar("y", 1, 3);
        IntVar z = model.intVar("z", 1, 3);

        HybridTuples tuples = new HybridTuples();
        tuples.add(eq(2), col(0), col(0));

        model.table(new IntVar[]{x, y, z}, tuples).post();

        try {
            model.getSolver().propagate();
        }
        catch (ContradictionException e) {
            e.printStackTrace();
        }

The output is:

x = 2
y = {1..3}
z = {1..3}

But if I add the constraint in the same program:

x.eq(2).post();

and then the output is:

x = 2
y = 2
z = 2

Is it expected behavior for col(i)?

[cprudhom]

I too have noticed this propagation failure.
This is related to tuples wherein some variables are related to each other.
The way smart tables are managed from now on is not satisfactory. I believe I need to fully rewamp the algorithm and also the DSL, because unlimited expressions will always be problematic.

[martins-avots]

A way to fix this could be a check during model.table, post or tupples.add.
tupples.add seems to be the best location.

[cprudhom]

See PR #1008

[gadavidd]

@cprudhom I tested the new operators in huge product configurator models (we focus on propagate) and looks like it works better than Oscar. But I didn't make a complete performance test to answer this question yet, because I found a bug with reify compared to Table Constraints. We wrote (with @TramontinLSS) a small test to exemplify this BUG:

public class Main {
    public static void main(String[] args) {

        Model model = new Model();
        IntVar x = model.intVar("x", 0, 6);
        IntVar y = model.intVar("y", 1, 5);

        //HybridTuples tuples = getHybridTuples();

        Tuples tuples = getStandardTuples();

        x.in(3).post();
        y.in(2).post();

        BoolVar r = model.table(new IntVar[]{x, y}, tuples).reify();

        propagate(model, x, y, r);

    }

    private static Tuples getStandardTuples() {
        Tuples tuples = new Tuples();
        tuples.add(2, 2);
        tuples.add(3, 3);
        tuples.add(4, 4);
        return tuples;
    }

    private static HybridTuples getHybridTuples() {
        HybridTuples tuples = new HybridTuples();
        tuples.add(eq(2), eq(2));
        tuples.add(eq(3), eq(3));
        tuples.add(eq(4), eq(4));
        return tuples;
    }

    private static void propagate(Model model, IntVar... vars) {
        try {
            model.getSolver().propagate();
        }
        catch (ContradictionException e) {
            e.printStackTrace();
        }

        System.out.println(String.join(" | ", Stream.of(vars).map(IntVar::toString).toList()));
    }
}

The output is:

x = 3 | y = 2 | REIF_1 = 0

But, if alternately use HybridTuples tuples = getHybridTuples() instead Tuples tuples = getStandardTuples() the output is different:

**CONTRADICTION (STR2 hybrid table constraint with 2 vars and 3 tuples, x = 3) : remove last value**
x = 3 | y = 2 | REIF_1 = 1

It is a bug, right? The REIF should be false in scenarios where the table contradicts other constraints or whole models. In standard tables for some reason, the contradiction is not thrown. Perhaps it needs to handle the contradiction and return `REIF_1 = 0' as solution?

Endly, HybridTable is fantastic and has solved many problems without being combined with Oscar. We'll change to use only choco. The operators in e nin are very important and solve a lot of problems.

Thanks a lot!

[cprudhom]

Thank you for the bug report.
There was an error in the isEntailed() method, which is fix and will be pushed soon.
I found another bug though, related to Many (ie, when a variable has many relationship in a single tuple).
In that case, supports are not correctly computed (it acts as a or while an and is required).
I need to find a fix.

[cprudhom]

I pushed 2 fixes.
@gadavidd If you want to give a try, the remote dev_htable is now up to date.
(and thank you for the feedbacks, I appreciate)

[gadavidd]

During the last week, I extensively tested the hybrid table with different and too big Knowledge-bases (in order of the million items) and it worked well with all operators (I yet didn't use the operator col(i)) and multivalued (operator in). I didn't find any errors. I think the Hybrid Table is ready to commit and I find a better result than Smart Table.

Now I'm working with real values in the tuples with Ibex. If I find any good results I return with information. I think that the theme should be a good paper.

@cprudhom, Hybrid Table is amazing and too helpful! Thank you!