Skip to content

Research at St Andrews

Exploiting short supports for generalised arc consistency for arbitrary constraints

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

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.
Close

Details

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
StatePublished - 2011

Conference

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

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatically improving constraint models in Savile Row through associative-commutative common subexpression elimination

    Nightingale, P., Akguen, O., Gent, I. P., Jefferson, C. & Miguel, I. Sep 2014 Principles and Practice of Constraint Programming. OSullivan, B. (ed.). Cham: Springer International Publishing, p. 590-605 16 p. (Lecture Notes in Computer Science; vol. 8656)

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

  2. Generating custom propagators for arbitrary constraints

    Gent, I. P., Jefferson, C., Linton, S., Miguel, I. & Nightingale, P. 1 Jun 2014 In : Artificial Intelligence. 211, 1, p. 1-33 33 p.

    Research output: Contribution to journalArticle

  3. Qualitative modelling via constraint programming

    Kelsey, T., Kotthoff, L., Jefferson, C. A., Linton, S. A., Miguel, I. J., Nightingale, P. & Gent, I. P. Apr 2014 In : Constraints. 19, 2, p. 163-173

    Research output: Contribution to journalArticle

  4. Breaking conditional symmetry in automated constraint modelling with CONJURE

    Akgun, O., Gent, I. P., Jefferson, C., Miguel, I. & Nightingale, P. 2014 ECAI 2014. Schaub, T., Friedrich, G. & O'Sullivan, B. (eds.). IOS Press, Vol. 263, p. 3-8 6 p. (Frontiers in Artificial Intelligence and Applications; vol. 263)

    Research output: Chapter in Book/Report/Conference proceedingChapter

ID: 17630250