MMJul, 2010

关于破坏行和列对称性的静态约束的复杂度和完备性

PDF
TL;DR研究了一种对称性，提出了一种简单有效的方法处理行与列对称性矩阵模型，对该对称性下的对称性破坏约束的陈述作出了一系列正面和负面的结论，并提出了关于破坏行、列和值的对称性的快速算法，实验研究了一些基准问题中，DOUBLELEX 和 SNAKELEX 留下的对称性问题的数量。
发现论文，激发创造
  • 对称性破缺约束：最新结果

    本文探讨了如何在组合问题中消除对称性，着重介绍了两种常见的对称性消除方法：行和列对称性的对称性破坏约束和值对称性的对称性破坏约束。

    Apr, 2012

  • 不同排序打破对称性

    该研究论文探讨了如何打破对称问题，介绍了 Lex-Leader 方法和两种替代方法（Gray code 排序和 Snake-Lex 排序），同时发现使用其他排序方式可以更好地对齐目标函数和分支启发式。

    Jun, 2013

  • 矩阵模型中打破行列对称性的评论

    该论文介绍了如何通过对称性破缺排序约束，识别和分析矩阵模型中的行和列对称性，并高效地解决这种对称性的问题。

    Oct, 2019

  • 破坏价值的对称性

    研究发现，对称性是解决许多约束满足问题的重要因素，其中一种常见类型是对称值。我们研究了打破值对称性的方法，结果确定了消除值对称性的计算限制。虽然在一般情况下，修剪所有对称值是 NP-hard 的，但实验表明在实践中可以打破很多值对称性，这些结果对规划、调度和其他领域的研究人员可能有用，因为值对称性出现在许多不同的领域中。

    Mar, 2009

  • 组合优化的认证对称性和支配破坏

    研究如何建立一种基于 cutting planes 证明系统的证明方法来验证包括对称性破坏和优势破坏等优化问题的解是否计算正确，实验表明我们可以有效地验证布尔可满足性（SAT）求解中全局对称性破坏，从而提供了一种统一的方法来证明一系列高级 SAT 技术，还可应用于最大团解决和约束编程。

    Mar, 2022

  • 破解对称性的复杂性

    通过消除对称类中不符合词典顺序的解，我们可以打破对称性，但是这种词典 - 领袖法一般情况下很难处理。我们证明在一般情况下使用其他总序关系 (例如格雷码排序或蛇形 - 词典排序) 来打破对称性的计算复杂度是高的。

    May, 2020

  • 复杂组合问题对称性约束的高效规避

    该论文介绍了基于模型的一种新方法，使用对称解决方案的学习框架来解决复杂的 Partner Units Problem 问题，尤其在电子行业中的应用具有实际意义。

    May, 2022

  • 对称破缺答案集求解

    本篇研究在回答集规划（Answer Set Programming）背景下，探讨通过对称性破除来简化解决方案的过程，提出将不相干的逻辑程序转化为有色图的缩减方法，并通过图自同构构建置换对称性，然后通过引入对称性破除约束来破坏对称性。针对此目的，我们设计了一个包含图自同构系统的预处理器。实验证明该系统具有较高的计算效率。

    Aug, 2010

  • 利用值先例破坏对称性

    本文研究价值优先约束的使用，通过三元约束对其进行编码以有效地打破对称性，并将其扩展到包括花环值和部分可互换性等多种情况，同时探讨了价值优先和对称性破坏约束在变量对称性方面的交互关系。

    Mar, 2009

  • 通过在线矩阵 - 向量乘积猜想统一和加强动态问题的难度

    探索使用次立方算法解决在线布尔矩阵向量乘法问题的困难程度，并将此问题与许多动态问题的困难程度联系起来，以展示它们之间的多项式时间困难性，并可能为它们展示深入的无条件下界或突破共同的障碍，并为一些未解决的问题提供了一个新的，统一的证明方法。

    Nov, 2015