Discovery - University of Dundee - Online Publications

Library & Learning Centre

Automatic generation of constraints for partial symmetry breaking

Automatic generation of constraints for partial symmetry breaking

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

View graph of relations

Authors

Research units

Info

Original languageEnglish
Title of host publicationPrinciples and practice of constraint programming - CP 2011
Subtitle of host publication7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings
EditorsJimmy Lee
Place of PublicationBerlin
PublisherSpringer
Pages729-743
Number of pages15
ISBN (Electronic)9783642237867
ISBN (Print)9783642237850
DOIs
StatePublished - 2011
Event17th International Conference on Principles and Practice of Constraint Programming - Perugia, Italy

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume6876
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Principles and Practice of Constraint Programming
Abbreviated titleCP 2011
CountryItaly
CityPerugia
Period12/09/1116/09/11
Internet address

Abstract

Constraint Satisfaction Problems (CSPs) are often highly symmetric. Symmetries can give rise to redundant search, since subtrees may be explored which are symmetric to subtrees already explored. To avoid this redundant search, constraint programmers have designed methods, which try to exclude all but one in each equivalence class of solutions. One problem with many of the symmetry breaking methods that eliminate all the symmetry is that they can have a large running overhead. To counter this flaw many CP practitioners have looked for methods that only eliminate a subset of the symmetries, so called partial symmetry breaking methods, but do so in an efficient manner. Partial symmetry breaking methods often work only when the problem is of a certain type. In this paper, we introduce a new method of finding a small set of constraints which provide very efficient partial symmetry breaking. This method works with all problem classes and modelling techniques. © 2011 Springer-Verlag.

Documents

DOI

Library & Learning Centre

Contact | Accessibility | Policy