ECAI 2004 Conference Paper

[full paper]

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

Alan M. Frisch, Christopher Jefferson, Ian. Miguel

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, and then searching for solutions that satisfy the constraints. Modelling choices are crucial to how efficiently the resultant model can be solved. Models generated by experts often are augmented with constraints that break symmetries in the model and thus remove redundancy from the search space, and with implied constraints, which prune some parts of the search space that contain no solutions. Common practice is to choose symmetry-breaking constraints by considering the number of symmetries that they break and the overhead that they incur. This paper argues that, to obtain the best model, the choice of symmetry-breaking constraints must be made not simply on their own merits, but also based on the strength of the implied constraints derivable from them. This approach should be established as a pattern in good constraint modelling practice. In particular, it is demonstrated that sometimes a weaker symmetry-breaking scheme can outperform a stronger one when constraints are added.

Keywords: Constraint programming, Modelling with constraints, Constraint patterns, Symmetry breaking

Citation: Alan M. Frisch, Christopher Jefferson, Ian. Miguel: Symmetry-breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.171-175.