Optimal and efficient filtering algorithms for table constraints

Simple item page
dc.contributor.authorMairy, Jean-Baptiste
dc.contributor.authorVan Hentenryck, Pascal
dc.contributor.authorDeville, Yves
dc.date.accessioned2015-12-10T23:23:02Z
dc.date.issued2013
dc.date.updated2015-12-10T10:36:11Z
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.identifier.issn1383-7133
dc.identifier.urihttp://hdl.handle.net/1885/66772
dc.publisherKluwer Academic Publishers
dc.sourceConstraints
dc.titleOptimal and efficient filtering algorithms for table constraints
dc.typeJournal article
local.bibliographicCitation.lastpage120
local.bibliographicCitation.startpage77
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.contributor.authoremailrepository.admin@anu.edu.au
local.contributor.authoruidVan Hentenryck, Pascal, u5136864
local.description.embargo2037-12-31
local.description.notesImported from ARIES
local.identifier.absfor080107 - Natural Language Processing
local.identifier.absseo970108 - Expanding Knowledge in the Information and Computing Sciences
local.identifier.ariespublicationu4334215xPUB1341
local.identifier.citationvolume19
local.identifier.doi10.1007/s10601-013-9156-0
local.identifier.scopusID2-s2.0-84891840446
local.identifier.thomsonID000329319300004
local.identifier.uidSubmittedByu4334215
local.type.statusPublished Version

Downloads

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
01_Mairy_Optimal_and_efficient_2013.pdf
Size:
2.76 MB
Format:
Adobe Portable Document Format
Download

Collections

ANU Research Publications

DSpace software copyright © 2002-2024 LYRASIS