NDLI: Optimal and efficient filtering algorithms for table constraints

Please wait, while we are loading the content...

Optimal and efficient filtering algorithms for table constraints

Content Provider	Springer Nature Link
Author	Mairy, Jean Baptiste Hentenryck, Pascal Deville, Yves
Copyright Year	2013
Abstract	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 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.
Starting Page	77
Ending Page	120
Page Count	44
File Format	PDF
ISSN	13837133
Journal	Constraints
Volume Number	19
Issue Number	1
e-ISSN	15729354
Language	English
Publisher	Springer US
Publisher Date	2013-11-21
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Propagation Consistency Filtering algorithms Table constraints Artificial Intelligence (incl. Robotics) Optimization Computing Methodologies Operations Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Artificial Intelligence Computational Theory and Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient algorithms for singleton arc consistency

New algorithms for max restricted path consistency

Domain consistency with forbidden values

Complete Bound Consistency for the Global Cardinality Constraint

STR2: optimized simple tabular reduction for table constraints

Grammar constraints

Strong local consistency algorithms for table constraints

Multiconsistency and Robustness with Global Constraints

New filtering algorithms for combinations of among constraints

Optimal and efficient filtering algorithms for table constraints

Similar Documents

Efficient algorithms for singleton arc consistency

New algorithms for max restricted path consistency

Domain consistency with forbidden values

Complete Bound Consistency for the Global Cardinality Constraint

STR2: optimized simple tabular reduction for table constraints

Grammar constraints

Strong local consistency algorithms for table constraints

Multiconsistency and Robustness with Global Constraints

New filtering algorithms for combinations of among constraints

Optimal and efficient filtering algorithms for table constraints