Breaking conditional symmetry in automated constraint modelling with CONJURE

Özgür Akgün; Ian Gent; Chris Jefferson; Ian Miguel; Peter Nightingale

doi:10.3233/978-1-61499-419-0-3

Breaking conditional symmetry in automated constraint modelling with CONJURE

Özgür Akgün, Ian Gent, Chris Jefferson, Ian Miguel, Peter Nightingale

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

Abstract

Many constraint problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: model symmetries. We present a systematic method by which the automated constraint modelling tool CONJURE can break conditional symmetry as it enters a model during refinement. Our method extends, and is compatible with, our previous work on automated symmetry breaking in CONJURE. The result is the automatic and complete removal of model symmetries for the entire problem class represented by the input specification. This applies to arbitrarily nested conditional symmetries and represents a significant step forward for automated constraint modelling.

Original language	English
Title of host publication	ECAI 2014
Editors	Torsten Schaub, Gerhard Friedrich, Barry O'Sullivan
Publisher	IOS Press
Pages	3-8
Number of pages	6
ISBN (Electronic)	9781614994190
ISBN (Print)	9781614994183
DOIs	https://doi.org/10.3233/978-1-61499-419-0-3
Publication status	Published - 18 Aug 2014

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Publisher	IOS Press
Volume	263
ISSN (Print)	0922-6389

Access to Document

10.3233/978-1-61499-419-0-3Licence: CC BY

Akgun_2015_IOS_Breaking_CC
© 2014 The Authors and IOS Press. This article is published online with Open Access by IOS Press and distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/deed.en_US).
Final published version, 186 KBLicence: CC BY-NC

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
A Constraint Solver Synthesiser: A Constraint Solver Synthesiser
Miguel, I. J. (PI), Balasubramaniam, D. (CoI), Gent, I. P. (CoI), Kelsey, T. (CoI) & Linton, S. A. (CoI)
EPSRC
1/10/09 → 30/09/14
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 Philip Gent
- Ian.Gentst-andrews.acuk
Person: Academic
Ian James Miguel
- ijmst-andrews.acuk
Person: Academic

Cite this

@inbook{dd9347655a2d45f2bef81ebcb8778daa,

title = "Breaking conditional symmetry in automated constraint modelling with CONJURE",

abstract = "Many constraint problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: model symmetries. We present a systematic method by which the automated constraint modelling tool CONJURE can break conditional symmetry as it enters a model during refinement. Our method extends, and is compatible with, our previous work on automated symmetry breaking in CONJURE. The result is the automatic and complete removal of model symmetries for the entire problem class represented by the input specification. This applies to arbitrarily nested conditional symmetries and represents a significant step forward for automated constraint modelling.",

author = "{\"O}zg{\"u}r Akg{\"u}n and Ian Gent and Chris Jefferson and Ian Miguel and Peter Nightingale",

note = "This work was supported by UK EPSRC EP/K015745/1. Jefferson is supported by a Royal Society University Research Fellowship.",

year = "2014",

month = aug,

day = "18",

doi = "10.3233/978-1-61499-419-0-3",

language = "English",

isbn = "9781614994183",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press",

pages = "3--8",

editor = "Torsten Schaub and Gerhard Friedrich and Barry O'Sullivan",

booktitle = "ECAI 2014",

address = "Netherlands",

}

TY - CHAP

T1 - Breaking conditional symmetry in automated constraint modelling with CONJURE

AU - Akgün, Özgür

AU - Gent, Ian

AU - Jefferson, Chris

AU - Miguel, Ian

AU - Nightingale, Peter

N1 - This work was supported by UK EPSRC EP/K015745/1. Jefferson is supported by a Royal Society University Research Fellowship.

PY - 2014/8/18

Y1 - 2014/8/18

N2 - Many constraint problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: model symmetries. We present a systematic method by which the automated constraint modelling tool CONJURE can break conditional symmetry as it enters a model during refinement. Our method extends, and is compatible with, our previous work on automated symmetry breaking in CONJURE. The result is the automatic and complete removal of model symmetries for the entire problem class represented by the input specification. This applies to arbitrarily nested conditional symmetries and represents a significant step forward for automated constraint modelling.

AB - Many constraint problems contain symmetry, which can lead to redundant search. If a partial assignment is shown to be invalid, we are wasting time if we ever consider a symmetric equivalent of it. A particularly important class of symmetries are those introduced by the constraint modelling process: model symmetries. We present a systematic method by which the automated constraint modelling tool CONJURE can break conditional symmetry as it enters a model during refinement. Our method extends, and is compatible with, our previous work on automated symmetry breaking in CONJURE. The result is the automatic and complete removal of model symmetries for the entire problem class represented by the input specification. This applies to arbitrarily nested conditional symmetries and represents a significant step forward for automated constraint modelling.

U2 - 10.3233/978-1-61499-419-0-3

DO - 10.3233/978-1-61499-419-0-3

M3 - Chapter

AN - SCOPUS:84923169106

SN - 9781614994183

T3 - Frontiers in Artificial Intelligence and Applications

SP - 3

EP - 8

BT - ECAI 2014

A2 - Schaub, Torsten

A2 - Friedrich, Gerhard

A2 - O'Sullivan, Barry

PB - IOS Press

ER -

Breaking conditional symmetry in automated constraint modelling with CONJURE

Abstract

Publication series

Access to Document

Fingerprint

Projects

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

A Constraint Solver Synthesiser: A Constraint Solver Synthesiser

Profiles

Ozgur Akgun

Ian Philip Gent

Ian James Miguel

Cite this