Skip navigation
Skip navigation

Optimal and efficient filtering algorithms for table constraints

Mairy, Jean-Baptiste; Van Hentenryck, Pascal; Deville, Yves

Description

Filtering algorithms for table constraints can be classified in two categories: constraint-based and value-based. In the constraint-based approaches, the propagation queue only contains information on the constraints that must be reconsidered. For the value-based approaches, the propagation queue also contains information on the removed values. This paper proposes five efficient value-based algorithms for table constraints. Two of them (AC5TCOpt-Tr and AC5TCOpt-Sparse) are proved to have an...[Show more]

dc.contributor.authorMairy, Jean-Baptiste
dc.contributor.authorVan Hentenryck, Pascal
dc.contributor.authorDeville, Yves
dc.date.accessioned2015-12-10T23:23:02Z
dc.identifier.issn1383-7133
dc.identifier.urihttp://hdl.handle.net/1885/66772
dc.description.abstractFiltering algorithms for table constraints can be classified in two categories: constraint-based and value-based. In the constraint-based approaches, the propagation queue only contains information on the constraints that must be reconsidered. For the value-based approaches, the propagation queue also contains information on the removed values. This paper proposes five efficient value-based algorithms for table constraints. Two of them (AC5TCOpt-Tr and AC5TCOpt-Sparse) are proved to have an optimal time complexity of O(r·t+r·d) per table constraint. Substantial experimental results are presented. An empirical analysis is conducted on the effect of the arity of the tables. The experiments show that our propagators are the best when the arity of the table is 3 or 4. Indeed, on instances containing only binary constraints, our algorithms are outperformed by classical AC algorithm AC3rm. AC3rm is dedicated to binary constraints. However, all our algorithms outperform existing state-of-the-art constraint based STR2+ and MDD c and the optimal value-based STR3 algorithms on those instances. On instances with small arity tables (up to arity 4), all our algorithms are generally faster than STR2+, MDD c and than STR3. AC5TCOpt-Sparse is globally the best propagator on those benchmarks. On benchmarks containing large arity tables (arity 5 or more), each of the three existing state-of-the-art algorithms is the winning strategy on one different benchmark.
dc.publisherKluwer Academic Publishers
dc.sourceConstraints
dc.titleOptimal and efficient filtering algorithms for table constraints
dc.typeJournal article
local.description.notesImported from ARIES
local.identifier.citationvolume19
dc.date.issued2013
local.identifier.absfor080107 - Natural Language Processing
local.identifier.ariespublicationu4334215xPUB1341
local.type.statusPublished Version
local.contributor.affiliationMairy, Jean-Baptiste, Universite Catholique de Louvain
local.contributor.affiliationVan Hentenryck, Pascal, College of Engineering and Computer Science, ANU
local.contributor.affiliationDeville, Yves, Universite Catholique de Louvain
local.description.embargo2037-12-31
local.bibliographicCitation.startpage77
local.bibliographicCitation.lastpage120
local.identifier.doi10.1007/s10601-013-9156-0
local.identifier.absseo970108 - Expanding Knowledge in the Information and Computing Sciences
dc.date.updated2015-12-10T10:36:11Z
local.identifier.scopusID2-s2.0-84891840446
local.identifier.thomsonID000329319300004
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_Mairy_Optimal_and_efficient_2013.pdf2.82 MBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator