Extending Compact-Table to Negative and Short Tables

Authors

  • Hélène Verhaeghe Université Catholique de Louvain
  • Christophe Lecoutre Université d'Artois
  • Pierre Schaus Université Catholique de Louvain

DOI:

https://doi.org/10.1609/aaai.v31i1.11127

Keywords:

Table constraints, Extensional constraints, Negative table, Short tuple, Filtering algorithm, Reversible-sparse-bitset

Abstract

Table constraints are very useful for modeling combinatorial constrained problems, and thus play an important role in Constraint Programming (CP). During the last decade, many algorithms have been proposed for enforcing the property known as Generalized Arc Consistency (GAC) on such constraints. A state-of-the art GAC algorithm called Compact-Table (CT), which has been recently proposed, significantly outperforms all previously proposed algorithms. In this paper, we extend this algorithm in order to deal with both short supports and negative tables, i.e., tables that contain universal values and conflicts. Our experimental results show the interest of using this fast general algorithm.

Downloads

Published

2017-02-12

How to Cite

Verhaeghe, H., Lecoutre, C., & Schaus, P. (2017). Extending Compact-Table to Negative and Short Tables. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.11127

Issue

Section

Main Track: Search and Constraint Satisfaction