通过消除对称类中不符合词典顺序的解,我们可以打破对称性,但是这种词典 - 领袖法一般情况下很难处理。我们证明在一般情况下使用其他总序关系 (例如格雷码排序或蛇形 - 词典排序) 来打破对称性的计算复杂度是高的。
May, 2020
研究了一种对称性,提出了一种简单有效的方法处理行与列对称性矩阵模型,对该对称性下的对称性破坏约束的陈述作出了一系列正面和负面的结论,并提出了关于破坏行、列和值的对称性的快速算法,实验研究了一些基准问题中,DOUBLELEX 和 SNAKELEX 留下的对称性问题的数量。
Jul, 2010
本文探讨了如何在组合问题中消除对称性,着重介绍了两种常见的对称性消除方法:行和列对称性的对称性破坏约束和值对称性的对称性破坏约束。
Apr, 2012
研究发现,对称性是解决许多约束满足问题的重要因素,其中一种常见类型是对称值。我们研究了打破值对称性的方法,结果确定了消除值对称性的计算限制。虽然在一般情况下,修剪所有对称值是 NP-hard 的,但实验表明在实践中可以打破很多值对称性,这些结果对规划、调度和其他领域的研究人员可能有用,因为值对称性出现在许多不同的领域中。
Mar, 2009
研究如何建立一种基于 cutting planes 证明系统的证明方法来验证包括对称性破坏和优势破坏等优化问题的解是否计算正确,实验表明我们可以有效地验证布尔可满足性(SAT)求解中全局对称性破坏,从而提供了一种统一的方法来证明一系列高级 SAT 技术,还可应用于最大团解决和约束编程。
Mar, 2022
本篇研究在回答集规划(Answer Set Programming)背景下,探讨通过对称性破除来简化解决方案的过程,提出将不相干的逻辑程序转化为有色图的缩减方法,并通过图自同构构建置换对称性,然后通过引入对称性破除约束来破坏对称性。针对此目的,我们设计了一个包含图自同构系统的预处理器。实验证明该系统具有较高的计算效率。
Aug, 2010
本文研究价值优先约束的使用,通过三元约束对其进行编码以有效地打破对称性,并将其扩展到包括花环值和部分可互换性等多种情况,同时探讨了价值优先和对称性破坏约束在变量对称性方面的交互关系。
该论文介绍了如何通过对称性破缺排序约束,识别和分析矩阵模型中的行和列对称性,并高效地解决这种对称性的问题。
Oct, 2019
该论文介绍了基于模型的一种新方法,使用对称解决方案的学习框架来解决复杂的 Partner Units Problem 问题,尤其在电子行业中的应用具有实际意义。
May, 2022
对于建模原子尺度物质性质的模型,以对称性作为归纳偏差普遍被采用。然而,非对称模型也能从数据中学习对称性,并对模型准确性有益。本研究测试了一个仅近似满足旋转不变性的模型在模拟气相、液态和固态水的实际场景中的性能,发现其在插值、大体积情况下几乎无影响。即使在外推气相预测中,该模型仍然非常稳定,尽管有对称性伪迹存在。我们还讨论了系统减小对称性破缺程度的策略,并评估其对观测量收敛性的影响。
Jun, 2024