arXiv:2511.11029cs.AI2025-11AAAI被引 1

提出更高效对称性破除方法,加速抽象结构约束求解。

Faster Symmetry Breaking Constraints for Abstract Structures

  • 通过优化抽象结构表示,减少对称性破除的复杂约束数量。
  • 在不可区分对象对称场景下,求解速度比现有方法提升显著。
  • 适合使用抽象结构建模的约束规划研究者与应用开发者。

在约束编程中,建模者使用如Essence等高级语言描述问题,其中常涉及抽象结构(如嵌套集合),这些结构需转换为求解器支持的形式(如矩阵)后才能求解。许多问题存在对称性,通过“破除对称”可避免重复搜索对称解,极大加速求解过程。传统方法通过对变量排序并选择最小成员来实现对称性破除,但应用于抽象变量时会产生大量复杂约束,导致性能下降。本文提出一种新的不完全对称性破除方法,通过更优地利用抽象结构的表示方式,显著减少约束数量。实验表明,在处理不可区分对象对称性的常见场景中,该方法比(Akgün et al. 2025)提出的方案更快,尤其在大规模实例上表现突出。

原文摘要 · Abstract (English)

In constraint programming and related paradigms, a modeller specifies their problem in a modelling language for a solver to search and return its solution(s). Using high-level modelling languages such as Essence, a modeller may express their problems in terms of abstract structures. These are structures not natively supported by the solvers, and so they have to be transformed into or represented as other structures before solving. For example, nested sets are abstract structures, and they can be represented as matrices in constraint solvers. Many problems contain symmetries and one very common and highly successful technique used in constraint programming is to "break" symmetries, to avoid searching for symmetric solutions. This can speed up the solving process by many orders of magnitude. Most of these symmetry-breaking techniques involve placing some kind of ordering for the variables of the problem, and picking a particular member under the symmetries, usually the smallest. Unfortunately, applying this technique to abstract variables produces a very large number of complex constraints that perform poorly in practice. In this paper, we demonstrate a new incomplete method of breaking the symmetries of abstract structures by better exploiting their representations. We apply the method in breaking the symmetries arising from indistinguishable objects, a commonly occurring type of symmetry, and show that our method is faster than the previous methods proposed in (Akgün et al. 2025).

约束编程对称性破除抽象结构求解效率

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。