Skip to content

Research at St Andrews

Automatic discovery and exploitation of promising subproblems for tabulation

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

Abstract

The performance of a constraint model can often be improved by converting a subproblem into a single table constraint. In this paper we study heuristics for identifying promising subproblems. We propose a small set of heuristics to identify common cases such as expressions that will propagate weakly. The process of discovering promising subproblems and tabulating them is entirely automated in the tool Savile Row. A cache is implemented to avoid tabulating equivalent subproblems many times. We give a simple algorithm to generate table constraints directly from a constraint expression in Savile Row. We demonstrate good performance on the benchmark problems used in earlier work on tabulation, and also for several new problem classes.
Close

Details

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings
EditorsJohn Hooker
PublisherSpringer
Pages3-12
ISBN (Electronic)9783319983349
ISBN (Print)9783319983332
DOIs
StatePublished - 2018
Event24th International Conference on Principles and Practice of Constraint Programming (CP 2018) - Euratechnologies, Lille, France
Duration: 27 Aug 201831 Aug 2018
Conference number: 24
http://cp2018.a4cp.org/

Publication series

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

Conference

Conference24th International Conference on Principles and Practice of Constraint Programming (CP 2018)
Abbreviated titleCP 2018
CountryFrance
CityLille
Period27/08/1831/08/18
Internet address

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

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

  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. Sep 2014 Principles and Practice of Constraint Programming. OSullivan, 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: 253604678