SCIENCE@home

Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets

J. Demeulenaere,Renaud Hartert,Christophe Lecoutre,G. Perez,Laurent Perron,Jean-Charles Régin,P. Schaus

Published 2016 in International Conference on Principles and Practice of Constraint Programming

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-32 of 32 references · Page 1 of 1

CITED BY

Showing 1-64 of 64 citing papers · Page 1 of 1