Skip to content

Research at St Andrews

An Automated Approach to Generating Efficient Constraint Solvers

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

DOI

Abstract

Combinatorial problems appear in numerous settings, from timetabling to industrial design. Constraint solving aims to find solutions to such problems efficiently and automatically. Current constraint solvers are monolithic in design, accepting a broad range of problems. The cost of this convenience is a complex architecture, inhibiting efficiency, extensibility and scalability. Solver components are also tightly coupled with complex restrictions on their configuration, making automated generation of solvers difficult. We describe a novel, automated, model-driven approach to generating efficient solvers tailored to individual problems and present some results from applying the approach. The main contribution of this work is a solver generation framework called Dominion, which analyses a problem and, based on its characteristics, generates a solver using components chosen from a library. The key benefit of this approach is the ability to solve larger and more difficult problems as a result of applying finer-grained optimisations and using specialised techniques as required.
Close

Details

Original languageEnglish
Title of host publication2012 34th international conference on software engineering (ICSE 2012)
Subtitle of host publicationZurich, Switzerland 2-9 June 2012
PublisherIEEE
Pages661-671
Number of pages11
ISBN (Electronic)978-1-4673-1065-9
ISBN (Print)978-1-4673-1066-6
DOIs
StatePublished - 2012
Event34th International Conference on Software Engineering, ICSE 2012 - Zurich, Switzerland

Conference

Conference34th International Conference on Software Engineering, ICSE 2012
CountrySwitzerland
CityZurich
Period2/06/129/06/12

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

View graph of relations

Related by author

  1. Dominion: an architecture-driven approach to generating efficient constraint solvers

    Balasubramaniam, D., De Silva, L. R., Jefferson, C. A., Kotthoff, L., Miguel, I. J. & Nightingale, P. Jun 2011 Proceedings of the 9th Working IEEE/IFIP Conference on Software Architecture (WICSA): Boulder, Colorado, USA 20-24 June 2011. Los Alamiros, CA: IEEE Computer Society, p. 228-231 4 p.

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

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

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

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

  5. Generating custom propagators for arbitrary constraints

    Gent, I. P., Jefferson, C., Linton, S., Miguel, I. & Nightingale, P. 1 Jun 2014 In : Artificial Intelligence. 211, 1, p. 1-33 33 p.

    Research output: Contribution to journalArticle

ID: 38590505