Name
Title | ||
|---|---|---|
Compact-Table: Efficiently Filtering Table Constraints With Reversible Sparse Bit-Sets |
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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-44953-1_14 | PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2016 |
DocType | Volume | ISSN |
Conference | 9892 | 0302-9743 |
Citations | PageRank | References |
6 | 0.45 | 18 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jordan Demeulenaere | 1 | 6 | 0.45 |
| Renaud Hartert | 2 | 56 | 4.15 |
| Christophe Lecoutre | 3 | 709 | 45.10 |
| guillaume perez | 4 | 19 | 3.03 |
| Laurent Perron | 5 | 240 | 53.16 |
| Jean-charles Régin | 6 | 1312 | 96.59 |
| Pierre Schaus | 7 | 127 | 24.63 |