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

A M Frisch; C Jefferson; I Miguel

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

A M Frisch, C Jefferson, I Miguel

Computer Science

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

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 demonstrated 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 language	English
Title of host publication	ECAI 2004: 16TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, PROCEEDINGS
Editors	R LopezdeMantaras, L Saitta
Place of Publication	AMSTERDAM
Publisher	IOS Press
Pages	171-175
Number of pages	5
ISBN (Print)	1-58603-452-9
Publication status	Published - 2004
Event	ECAI'2004 - Valencia, Spain Duration: 22 Aug 2004 → 27 Aug 2004

Conference

Conference	ECAI'2004
Country/Territory	Spain
City	Valencia
Period	22/08/04 → 27/08/04

Cite this

@inproceedings{2daa232855b648ba85b6fbbc611e9c7c,

title = "Symmetry breaking as a prelude to implied constraints: A constraint modelling pattern",

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 demonstrated 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.",

author = "Frisch, {A M} and C Jefferson and I Miguel",

year = "2004",

language = "English",

isbn = "1-58603-452-9",

pages = "171--175",

editor = "R LopezdeMantaras and L Saitta",

booktitle = "ECAI 2004: 16TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, PROCEEDINGS",

publisher = "IOS Press",

address = "Netherlands",

note = "ECAI'2004 ; Conference date: 22-08-2004 Through 27-08-2004",

}

TY - GEN

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

AU - Frisch, A M

AU - Jefferson, C

AU - Miguel, I

PY - 2004

Y1 - 2004

N2 - 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 demonstrated 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.

AB - 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 demonstrated 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.

M3 - Conference contribution

SN - 1-58603-452-9

SP - 171

EP - 175

BT - ECAI 2004: 16TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, PROCEEDINGS

A2 - LopezdeMantaras, R

A2 - Saitta, L

PB - IOS Press

CY - AMSTERDAM

T2 - ECAI'2004

Y2 - 22 August 2004 through 27 August 2004

ER -