Skip to content

Research at St Andrews

An Automated Approach to Generating Efficient Constraint Solvers

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

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
Duration: 2 Jun 20129 Jun 2012

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

ID: 38590505