Exploiting short supports for generalised arc consistency for arbitrary constraints

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

Special-purpose constraint propagation algorithms (such as those for the element constraint) frequently make implicit use of short supports — by examining a subset of the variables, they can infer support for all other variables and values and save substantial work. However, to date general purpose propagation algorithms (such as GAC-Schema) rely upon supports involving all variables. We demonstrate how to employ short supports in a new general purpose propagation algorithm called ShortGAC. This works when provided with either an explicit list of allowed short tuples, or a function to calculate the next supporting short tuple. Empirical analyses demonstrate the efficiency of ShortGAC compared to other general-purpose propagation algorithms. In some cases ShortGAC even exhibits similar performance to special-purpose propagators.
Original languageEnglish
Title of host publicationProceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011)
Subtitle of host publicationBarcelona, Catalonia, Spain, July 16-22, 2011
EditorsToby Walsh
Place of PublicationMenlo Park, California
PublisherIJCAI/AAAI
Pages623-628
Number of pages6
ISBN (Electronic)978-1-57735-516-8
DOIs
Publication statusPublished - 2011
EventTwenty-Second International Joint Conference on Artificial Intelligence - Barcelona, Spain
Duration: 16 Jul 201122 Jul 2011

Conference

ConferenceTwenty-Second International Joint Conference on Artificial Intelligence
Country/TerritorySpain
CityBarcelona
Period16/07/1122/07/11

Fingerprint

Dive into the research topics of 'Exploiting short supports for generalised arc consistency for arbitrary constraints'. Together they form a unique fingerprint.

Cite this