By the same authors

Symmetry Breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern

Research output: Contribution to conferencePaper

Author(s)

Department/unit(s)

Publication details

DatePublished - 2004
Number of pages4
Original languageUndefined/Unknown

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.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations