
[full paper] 
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 symmetrybreaking 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 symmetrybreaking 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 symmetrybreaking 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: Symmetrybreaking 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.171175.