Skip to content

Research at St Andrews

Exploiting short supports for improved encoding of arbitrary constraints into SAT

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

Abstract

Encoding to SAT and applying a highly efficient modern SAT solver is an increasingly popular method of solving finite-domain constraint problems. In this paper we study encodings of arbitrary constraints where unit propagation on the encoding provides strong reasoning. Specifically, unit propagation on the encoding simulates generalised arc consistency on the original constraint.
To create compact and efficient encodings we use the concept of short support. Short support has been successfully applied to create efficient propagation algorithms for arbitrary constraints. A short support of a constraint is similar to a satisfying tuple however a short support is not required to assign every variable in scope. Some variables are left free to take any value. In some cases a short support representation is smaller than the table of satisfying tuples by an exponential factor. We present two encodings based on short supports and evaluate them on a set of benchmark problems, demonstrating a substantial improvement over the state of the art.
Close

Details

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings
EditorsMichael Rueher
PublisherSpringer
Pages3-12
ISBN (Electronic)9783319449531
ISBN (Print)9783319449524
DOIs
Publication statusPublished - 2016
Event22nd International Conference on Principles and Practice of Constraint Programming (CP 2016) - Toulouse Business School, Toulouse, France
Duration: 5 Sep 20169 Sep 2016

Publication series

NameLecture Notes in Computer Science
Volume9892
ISSN (Print)0302-9743

Conference

Conference22nd International Conference on Principles and Practice of Constraint Programming (CP 2016)
CountryFrance
CityToulouse
Period5/09/169/09/16

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

View graph of relations

Related by author

  1. A framework for constraint based local search using ESSENCE

    Akgun, O., Attieh, S. W. A., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W., Salamon, A. Z., Spracklen, P. & Wetter, J. P., 13 Jul 2018, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Lang, J. (ed.). International Joint Conferences on Artificial Intelligence, p. 1242-1248 7 p.

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

  2. Metamorphic testing of constraint solvers

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J. & Nightingale, P. W., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 727-736 (Lecture Notes in Computer Science; vol. 11008).

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

  3. Automatic discovery and exploitation of promising subproblems for tabulation

    Akgun, O., Gent, I. P., Jefferson, C. A., Miguel, I. J., Nightingale, P. W. & Salamon, A. Z., 2018, Principles and Practice of Constraint Programming: 24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings. Hooker, J. (ed.). Springer, p. 3-12 (Lecture Notes in Computer Science; vol. 11008).

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

  4. Automatically improving constraint models in Savile Row

    Nightingale, P., Akgün, Ö., Gent, I. P., Jefferson, C., Miguel, I. & Spracklen, P., Oct 2017, In : Artificial Intelligence. 251, p. 35-61 27 p.

    Research output: Contribution to journalArticle

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

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

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

ID: 244287638