Automatically generating streamlined constraint models with ESSENCE and CONJURE

James Wetter; Ozgur Akgun; Ian Miguel

doi:10.1007/978-3-319-23219-5_34

Automatically generating streamlined constraint models with ESSENCE and CONJURE

James Wetter^*, Ozgur Akgun, Ian Miguel

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously, effective streamlined models have been constructed by hand, requiring an expert to examine closely solutions to small instances of a problem class and identify regularities. We present a system that automatically generates many conjectured regularities for a given Essence specification of a problem class by examining the domains of decision variables present in the problem specification. These conjectures are evaluated independently and in conjunction with one another on a set of instances from the specified class via an automated modelling tool-chain comprising of Conjure, Savile Row and Minion. Once the system has identified effective conjectures they are used to generate streamlined models that allow instances of much larger scale to be solved. Our results demonstrate good models can be identified for problems in combinatorial design, Ramsey theory, graph theory and group theory - often resulting in order of magnitude speed-ups.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming
Subtitle of host publication	21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings
Editors	Gilles Pesant
Publisher	Springer
Pages	480-496
Number of pages	17
ISBN (Electronic)	9783319232195
ISBN (Print)	9783319232188
DOIs	https://doi.org/10.1007/978-3-319-23219-5_34
Publication status	Published - 13 Aug 2015
Event	21st International Conference on the Principles and Practice of Constraint Programming, CP 2015 - Cork, Ireland Duration: 31 Aug 2015 → 4 Sept 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9255 (LNCS)
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on the Principles and Practice of Constraint Programming, CP 2015
Country/Territory	Ireland
City	Cork
Period	31/08/15 → 4/09/15

Access to Document

10.1007/978-3-319-23219-5_34

Miguel_2016_LectureNotes_AutoEssence_AAM
Copyright © 2015, Springer International Publishing. This work is made available online in accordance with the publisher’s policies. This is the author created, accepted version manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at https://dx.doi.org/10.1007/978-3-319-23219-5_34
Accepted author manuscript, 649 KB

Working Together in ICT: Working Together: Constraint Programming and Cloud Computing
Miguel, I. J. (PI) & Barker, A. D. (CoI)
EPSRC
1/01/13 → 30/09/16
Project: Standard

Ozgur Akgun
- ozgur.akgunst-andrews.acuk
- School of Computer Science - Senior Lecturer, Director of Impact
- Centre for Interdisciplinary Research in Computational Algebra
Person: Academic
Ian James Miguel
- ijmst-andrews.acuk
Person: Academic

Cite this

Wetter, J., Akgun, O., & Miguel, I. (2015). Automatically generating streamlined constraint models with ESSENCE and CONJURE. In G. Pesant (Ed.), Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings (pp. 480-496). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9255 (LNCS)). Springer. https://doi.org/10.1007/978-3-319-23219-5_34

Wetter, James ; Akgun, Ozgur ; Miguel, Ian. / Automatically generating streamlined constraint models with ESSENCE and CONJURE. Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings. editor / Gilles Pesant. Springer, 2015. pp. 480-496 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9dd26cea0c54476f8d0418df430909da,

title = "Automatically generating streamlined constraint models with ESSENCE and CONJURE",

abstract = "Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously, effective streamlined models have been constructed by hand, requiring an expert to examine closely solutions to small instances of a problem class and identify regularities. We present a system that automatically generates many conjectured regularities for a given Essence specification of a problem class by examining the domains of decision variables present in the problem specification. These conjectures are evaluated independently and in conjunction with one another on a set of instances from the specified class via an automated modelling tool-chain comprising of Conjure, Savile Row and Minion. Once the system has identified effective conjectures they are used to generate streamlined models that allow instances of much larger scale to be solved. Our results demonstrate good models can be identified for problems in combinatorial design, Ramsey theory, graph theory and group theory - often resulting in order of magnitude speed-ups.",

author = "James Wetter and Ozgur Akgun and Ian Miguel",

year = "2015",

month = aug,

day = "13",

doi = "10.1007/978-3-319-23219-5_34",

language = "English",

isbn = "9783319232188",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "480--496",

editor = "Gilles Pesant",

booktitle = "Principles and Practice of Constraint Programming",

address = "Netherlands",

note = "21st International Conference on the Principles and Practice of Constraint Programming, CP 2015 ; Conference date: 31-08-2015 Through 04-09-2015",

}

Wetter, J, Akgun, O & Miguel, I 2015, Automatically generating streamlined constraint models with ESSENCE and CONJURE. in G Pesant (ed.), Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9255 (LNCS), Springer, pp. 480-496, 21st International Conference on the Principles and Practice of Constraint Programming, CP 2015, Cork, Ireland, 31/08/15. https://doi.org/10.1007/978-3-319-23219-5_34

Automatically generating streamlined constraint models with ESSENCE and CONJURE. / Wetter, James; Akgun, Ozgur ; Miguel, Ian.
Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings. ed. / Gilles Pesant. Springer, 2015. p. 480-496 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9255 (LNCS)).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Automatically generating streamlined constraint models with ESSENCE and CONJURE

AU - Wetter, James

AU - Akgun, Ozgur

AU - Miguel, Ian

PY - 2015/8/13

Y1 - 2015/8/13

N2 - Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously, effective streamlined models have been constructed by hand, requiring an expert to examine closely solutions to small instances of a problem class and identify regularities. We present a system that automatically generates many conjectured regularities for a given Essence specification of a problem class by examining the domains of decision variables present in the problem specification. These conjectures are evaluated independently and in conjunction with one another on a set of instances from the specified class via an automated modelling tool-chain comprising of Conjure, Savile Row and Minion. Once the system has identified effective conjectures they are used to generate streamlined models that allow instances of much larger scale to be solved. Our results demonstrate good models can be identified for problems in combinatorial design, Ramsey theory, graph theory and group theory - often resulting in order of magnitude speed-ups.

AB - Streamlined constraint reasoning is the addition of uninferred constraints to a constraint model to reduce the search space, while retaining at least one solution. Previously, effective streamlined models have been constructed by hand, requiring an expert to examine closely solutions to small instances of a problem class and identify regularities. We present a system that automatically generates many conjectured regularities for a given Essence specification of a problem class by examining the domains of decision variables present in the problem specification. These conjectures are evaluated independently and in conjunction with one another on a set of instances from the specified class via an automated modelling tool-chain comprising of Conjure, Savile Row and Minion. Once the system has identified effective conjectures they are used to generate streamlined models that allow instances of much larger scale to be solved. Our results demonstrate good models can be identified for problems in combinatorial design, Ramsey theory, graph theory and group theory - often resulting in order of magnitude speed-ups.

U2 - 10.1007/978-3-319-23219-5_34

DO - 10.1007/978-3-319-23219-5_34

M3 - Conference contribution

AN - SCOPUS:84944543071

SN - 9783319232188

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 480

EP - 496

BT - Principles and Practice of Constraint Programming

A2 - Pesant, Gilles

PB - Springer

T2 - 21st International Conference on the Principles and Practice of Constraint Programming, CP 2015

Y2 - 31 August 2015 through 4 September 2015

ER -

Wetter J, Akgun O , Miguel I. Automatically generating streamlined constraint models with ESSENCE and CONJURE. In Pesant G, editor, Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings. Springer. 2015. p. 480-496. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-23219-5_34

Automatically generating streamlined constraint models with ESSENCE and CONJURE

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

Working Together in ICT: Working Together: Constraint Programming and Cloud Computing

Profiles

Ozgur Akgun

Ian James Miguel

Cite this