Skip to content

Research at St Andrews

Generating custom propagators for arbitrary constraints

Research output: Contribution to journalArticlepeer-review

Abstract

Constraint Programming (CP) is a proven set of techniques for solving complex combinatorial problems from a range of disciplines. The problem is specified as a set of decision variables (with finite domains) and constraints linking the variables. Local reasoning (propagation) on the constraints is central to CP. Many constraints have efficient constraint-specific propagation algorithms. In this work, we generate custom propagators for constraints. These custom propagators can be very efficient, even approaching (and in some cases exceeding) the efficiency of hand-optimised propagators.

Given an arbitrary constraint, we show how to generate a custom propagator that establishes GAC in small polynomial time. This is done by precomputing the propagation that would be performed on every relevant subdomain. The number of relevant subdomains, and therefore the size of the generated propagator, is potentially exponential in the number and domain size of the constrained variables.

The limiting factor of our approach is the size of the generated propagators. We investigate symmetry as a means of reducing that size. We exploit the symmetries of the constraint to merge symmetric parts of the generated propagator. This extends the reach of our approach to somewhat larger constraints, with a small run-time penalty.

Our experimental results show that, compared with optimised implementations of the table constraint, our techniques can lead to an order of magnitude speedup. Propagation is so fast that the generated propagators compare well with hand-written carefully optimised propagators for the same constraints, and the time taken to generate a propagator is more than repaid.
Close

Details

Original languageEnglish
Pages (from-to)1-33
Number of pages33
JournalArtificial Intelligence
Volume211
Early online date12 Mar 2014
DOIs
Publication statusPublished - Jun 2014

    Research areas

  • Constraint programming , Constraint satisfaction problem , Propagation algorithms , Combinatorial search

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

View graph of relations

Related by author

  1. 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 journalArticlepeer-review

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

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

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

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

Related by journal

  1. 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 journalArticlepeer-review

  2. The Extended Global Cardinality Constraint: An Empirical Survey

    Nightingale, P., Feb 2011, In: Artificial Intelligence. 175, 2, p. 586-614 29 p.

    Research output: Contribution to journalArticlepeer-review

  3. Implementing logical connectives in constraint programming

    Jefferson, C. A., Moore, N. C. A., Nightingale, P. & Petrie, K. E., Nov 2010, In: Artificial Intelligence. 174, 16-17, p. 1407-1429 23 p.

    Research output: Contribution to journalArticlepeer-review

  4. Filtering Algorithms for the Multiset Ordering Constraint

    Frisch, A., Hnich, B., Kiziltan, Z., Miguel, I. J. & Walsh, T., Feb 2009, In: Artificial Intelligence. 173, 2, p. 299-328 29 p.

    Research output: Contribution to journalArticlepeer-review

ID: 109831917

Top