Discovery - University of Dundee - Online Publications

Library & Learning Centre

A theoretical framework for constraint propagator triggering

A theoretical framework for constraint propagator triggering

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

View graph of relations

Authors

Research units

Info

Original languageEnglish
Title of host publicationProceedings of the Ninth International Symposium on Combinatorial Search
EditorsJorge A. Baier, Adi Botea
PublisherAAAI Press
Pages19-27
Number of pages9
ISBN (Print)9781577357698
StatePublished - 2016
EventInternational Symposium on Combinatorial Search - Tarrytown, NY, United States

Conference

ConferenceInternational Symposium on Combinatorial Search
Abbreviated titleSOCS 2016
CountryUnited States
CityTarrytown, NY
Period6/07/168/07/16
Internet address

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.

Documents

Library & Learning Centre

Contact | Accessibility | Policy