Skip to content

Research at St Andrews

A theoretical framework for constraint propagator triggering

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

Abstract

CSP instances are commonly solved by backtracking search combined with constraint propagation. During search, constraint solvers aim to remove any literals (variable-value pair) that can be shown not to be part of any solution. This literal removal, called propagation, is the beating heart of modern constraint solvers. A significant proportion of the runtime of propagating constraint solvers is spent running propagation algorithms. Therefore any mechanism for reducing how frequently propagators are called leads directly to significant performance improvements. One family of popular techniques is dynamic triggering – these techniques aim to avoid invoking a propagator when it would remove no literals. While this technique has been successful in practice, it has not yet been studied theoretically. This paper provides a theoretical framework for understanding when dynamic triggering will be successful. In particular, we prove when a literal deletion does not require a propagator to be executed. To achieve this, we describe supports: a support for a constraint is a set of literals whose presence in a search state ensures that propagating the constraint will not remove any literals. Therefore running the propagator when a literal outside the support is deleted is a waste of time. By characterising supports and giving a definition of dynamic and static supports for the CSP, we provide the framework for a proper analysis. We show how the number of triggers required for different constraints varies widely. For some constraints, dynamic triggering allows very small supports, for others the number of required supports is provably large.
Close

Details

Original languageEnglish
Title of host publicationProceedings of the 9th Annual Symposium on Combinatorial Search, SoCS 2016
EditorsJorge A. Baier, Adi Botea
PublisherAAAI Press
Pages19-27
Number of pages9
Volume2016-January
ISBN (Electronic)9781577357698
Publication statusPublished - 20 Jun 2016
Event9th Annual Symposium on Combinatorial Search, SoCS 2016 - Tarrytown, United States
Duration: 6 Jul 20168 Jul 2016
Conference number: 9
http://socs16.search-conference.org/

Conference

Conference9th Annual Symposium on Combinatorial Search, SoCS 2016
Abbreviated titleSoCS 2016
CountryUnited States
CityTarrytown
Period6/07/168/07/16
Internet address

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

View graph of relations

Related by author

  1. Athanor: high-level local search over abstract constraint specifications in Essence

    Attieh, S., Dang, N., Jefferson, C., Miguel, I. & Nightingale, P., 10 Aug 2019, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19). Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1056-1063 8 p.

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

  2. GAP – Groups, Algorithms, and Programming, Version 4.10.2

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 19 Jun 2019

    Research output: Non-textual formSoftware

  3. New refiners for permutation group search

    Jefferson, C., Pfeiffer, M. & Waldecker, R., May 2019, In : Journal of Symbolic Computation. 92, p. 70-92 23 p.

    Research output: Contribution to journalArticle

  4. Minimal and canonical images

    Jefferson, C., Jonauskyte, E., Pfeiffer, M. & Waldecker, R., 1 Mar 2019, In : Journal of Algebra. 521, p. 481-506

    Research output: Contribution to journalArticle

  5. GAP – Groups, Algorithms, and Programming, Version 4.10.1

    The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 23 Feb 2019

    Research output: Non-textual formSoftware

ID: 258372250

Top