### Abstract

Original language | English |
---|---|

Title of host publication | Principles and practice of constraint programming - CP 2011 |

Subtitle of host publication | 7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings |

Editors | Jimmy Lee |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 729-743 |

Number of pages | 15 |

ISBN (Electronic) | 9783642237867 |

ISBN (Print) | 9783642237850 |

DOIs | |

Publication status | Published - 2011 |

Event | 17th International Conference on Principles and Practice of Constraint Programming - Aula magna, Perugia, Italy Duration: 12 Sep 2011 → 16 Sep 2011 http://www.dmi.unipg.it/cp2011/ |

### Publication series

Name | Lecture notes in computer science |
---|---|

Publisher | Springer |

Volume | 6876 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 17th International Conference on Principles and Practice of Constraint Programming |
---|---|

Abbreviated title | CP 2011 |

Country | Italy |

City | Perugia |

Period | 12/09/11 → 16/09/11 |

Internet address |

### Fingerprint

### Keywords

- Automatic Generation
- Constraint satisfaction problems
- Modelling techniques
- Subtrees
- Symmetry-breaking

### Cite this

*Principles and practice of constraint programming - CP 2011: 7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings*(pp. 729-743). (Lecture notes in computer science; Vol. 6876). Berlin: Springer . https://doi.org/10.1007/978-3-642-23786-7_55

}

*Principles and practice of constraint programming - CP 2011: 7th International Conference, CP 2011, Perugia, Italy, September 12-16, 2011. Proceedings.*Lecture notes in computer science, vol. 6876, Springer , Berlin, pp. 729-743, 17th International Conference on Principles and Practice of Constraint Programming , Perugia, Italy, 12/09/11. https://doi.org/10.1007/978-3-642-23786-7_55

**Automatic generation of constraints for partial symmetry breaking.** / Jefferson, Christopher; Petrie, Karen E.

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

TY - GEN

T1 - Automatic generation of constraints for partial symmetry breaking

AU - Jefferson, Christopher

AU - Petrie, Karen E.

PY - 2011

Y1 - 2011

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

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

KW - Automatic Generation

KW - Constraint satisfaction problems

KW - Modelling techniques

KW - Subtrees

KW - Symmetry-breaking

UR - http://www.scopus.com/inward/record.url?scp=80052986326&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-23786-7_55

DO - 10.1007/978-3-642-23786-7_55

M3 - Conference contribution

AN - SCOPUS:80052986326

SN - 9783642237850

T3 - Lecture notes in computer science

SP - 729

EP - 743

BT - Principles and practice of constraint programming - CP 2011

A2 - Lee, Jimmy

PB - Springer

CY - Berlin

ER -