Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets
(2016) Principles and Practice of Constraint Programming — Location: Toulouse, France (5.September.2016)
Files
cp2016-compacttable.pdf
Open Access - Adobe PDF
- 1.84 MB
Details
- Authors
- Abstract
- In this paper, we describe Compact-Table (CT), a bitwise algorithm to enforce Generalized Arc Consistency (GAC) on table constraints. 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.
- Affiliations
Citations
Demeulenare, J., Hartert, R., Lecoutre, C., Perrez, G., Perron, L., Régin, J.-C., & Schaus, P. (2016). Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets. Lecture Notes in Computer Science, 9892(9892), 207-223. https://doi.org/10.48550/arXiv.1604.06641 (Original work published 2016)