Extending Compact-Table to Basic Smart Tables

Verhaeghe, Hélène [UCL] Lecoutre, Christophe [UCL] Deville, Yves [UCL] Schaus, Pierre [UCL] et al.

Table constraints are instrumental in modelling combinatorial prob- lems with Constraint Programming. Recently, Compact-Table (CT) has been pro- posed and shown to be as an efficient filtering algorithm for table constraints, notably because of bitwise operations. CT has already been extended to handle non-ordinary tables, namely, short tables and/or negative tables. In this paper, we introduce another extension so as to deal with basic smart tables, which are ta- bles containing universal values (∗), restrictions on values (6 = v) bounds (≤ v or ≥ v) and sets (∈ S). Such tables offer the user a better expressiveness and permit to deal efficiently with compressed tuples. Our experiments show a substantial speedup when compression is possible (and a very limited overhead otherwise).