Breaking the symmetries of indistinguishable objects

Indistinguishable objects often occur when modelling problems in constraint programming, as well as in other related paradigms. They occur when objects can be viewed as being drawn from a set of unlabelled objects, and the only operation allowed on them is equality testing. For example, the golfers in the social golfer problem are indistinguishable. If we do label the golfers, then any relabelling of the golfers in one solution gives another valid solution. In this paper, we show how we can break the symmetries resulting from indistinguishable objects. We show how these symmetries induce symmetries of types built from indistinguishable objects, for example in a matrix indexed by indistinguishable objects. We then show how the resulting symmetries can be broken correctly and completely. As the method can be prohibitively expensive, we also study methods for breaking the symmetry only partially. In Essence, a high-level modelling language, indistinguishable objects are encapsulated in ‘unnamed types’. We provide an implementation to automatically break symmetries of unnamed types.