解决不可区分对象的对称性问题，提升约束求解效率
Breaking the Symmetries of Indistinguishable Objects
- 用未命名类型封装不可区分对象，定义复杂结构中的对称性
- 在Essence语言中实现对未命名类型的完整对称性破缺
- 适用于需处理大量等价解的约束规划场景
不可区分对象常见于约束规划及其他相关范式中，例如社交高球问题中的球手。若对球手进行标记，则任一重标号方案都会产生另一个有效解，因此对称群作用于这些对象。本文提出如何正确地打破由不可区分对象引发的对称性。我们展示了如何在复杂类型（如由不可区分对象索引的矩阵）中正确定义对称性，并实现其正确破缺。在高阶建模语言Essence中，不可区分对象被封装在“未命名类型”中，本文提供了对未命名类型完整的对称性破缺实现。
原文摘要 · Abstract (English)
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. Therefore, we can regard the symmetric group of size $n$ as acting on a set of $n$ indistinguishable objects. In this paper, we show how we can break the symmetries resulting from indistinguishable objects. We show how symmetries on indistinguishable objects can be defined properly in complex types, for example in a matrix indexed by indistinguishable objects. We then show how the resulting symmetries can be broken correctly. In Essence, a high-level modelling language, indistinguishable objects are encapsulated in "unnamed types". We provide an implementation of complete symmetry breaking for unnamed types in Essence.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。