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