Efficient Reification of Table Constraints

Khong, Minh Thanh [UCL] Deville, Yves [UCL] Schaus, Pierre [UCL] Lecoutre, Christophe

Reifying a constraint c consists in associating a Boolean variable b with c such that c is satisfied if and only if b is true, which can be denoted by c^reif: c <=> b. Reification is useful for logically combining constraints and counting how many reified constraints can be satisfied. Since table constraints play an important role within constraint programming, in this paper, we are interested in their reification. We introduce a filtering algorithm that allows us to establish generalized arc consistency on reified table constraints, with no spatial overhead. We also propose a flexible approach that can generally reify any subsets of constraints.