Symmetry-breaking as a prelude to implied constraints: A constraint modelling pattern

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

15 Citations (Scopus)

Abstract

Finite-domain constraint programming can be used to solve a wide range of problems by first modelling the problem as a set of constraints that characterise the problem's solutions, then searching for solutions that satisfy the constraints. Experts often augment models with implied constraints and constraints that break symmetries in the model. An emerging pattern in the modelling process, highlighted and <lemonstrated here, is that some powerful implied constraints can be derived only after symmetry-breaking constraints have been added. Furthermore, the choice between alternative symmetry-breaking constraints is commonly made by considering either the amount of symmetry broken or the strength of pruning obtained in comparison with the overhead of enforcing the constraints. We demonstrate that the choice should also consider the strength of the implied constraints derivable from the symmetry breaking constraints. We also discuss future automation of the selection of symmetry-breaking constraints and the derivation of implied constraints.

Original languageEnglish
Title of host publicationECAI 2004 - 16th European Conference on Artificial Intelligence, including Prestigious Applications of Intelligent Systems, PAIS 2004 - Proceedings
EditorsRamon Lopez de Mantaras, Lorenza Saitta
PublisherIOS Press
Pages171-175
Number of pages5
ISBN (Electronic)9781586034528
Publication statusPublished - 1 Jan 2004
Event16th European Conference on Artificial Intelligence, ECAI 2004 - Valencia, Spain
Duration: 22 Aug 200427 Aug 2004

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume110
ISSN (Print)0922-6389

Conference

Conference16th European Conference on Artificial Intelligence, ECAI 2004
Country/TerritorySpain
CityValencia
Period22/08/0427/08/04

Fingerprint

Dive into the research topics of 'Symmetry-breaking as a prelude to implied constraints: A constraint modelling pattern'. Together they form a unique fingerprint.

Cite this