2016/01/01 by Jordan Demeulenare, Demeulenaere, Jordan, Renaud Hartert +14 · 1 citation
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Blind Source Separation Techniques #Constraint Satisfaction and Optimization #Digital Filter Design and Implementation #Error Correcting Code Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1604.06641
openalex publication_date 2016/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we describe Compact-Table (CT), a bitwise algorithm to enforce Generalized Arc Consistency (GAC) on table con- straints. Although this algorithm is the default propagator for table constraints in or-tools and OscaR, two publicly available CP solvers, it has never been described so far. Importantly, CT has been recently improved further with the introduction of residues, resetting operations and a data-structure called reversible sparse bit-set, used to maintain tables of supports (following the idea of tabular reduction): tuples are invalidated incrementally on value removals by means of bit-set operations. The experimentation that we have conducted with OscaR shows that CT outperforms state-of-the-art algorithms STR2, STR3, GAC4R, MDD4R and AC5-TC on standard benchmarks.