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

DOI

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
EventTwenty-Second International Joint Conference on Artificial Intelligence - Barcelona, Spain

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. Exploiting short supports for improved encoding of arbitrary constraints into SAT

    Akgün, Ö., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W. 2016 Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings. Rueher, M. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 9892)

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

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

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

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

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