AAAIMar, 2022

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

PDF
TL;DR研究如何建立一种基于 cutting planes 证明系统的证明方法来验证包括对称性破坏和优势破坏等优化问题的解是否计算正确，实验表明我们可以有效地验证布尔可满足性（SAT）求解中全局对称性破坏，从而提供了一种统一的方法来证明一系列高级 SAT 技术，还可应用于最大团解决和约束编程。
symmetry breakingdominance breakingcutting planes proof systemoptimisation problemsmachine-verifiable certificates
发现论文，激发创造
  • 对称性破缺约束：最新结果

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

    Apr, 2012

  • 破坏价值的对称性

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

    Mar, 2009

  • 对称破缺答案集求解

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

    Aug, 2010

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

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

    May, 2022

  • 不同排序打破对称性

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

    Jun, 2013

  • 分而治之：约束满足问题的通用方法

    介绍一种用几何模型来解决多约束条件优化问题的方法，并在布尔可满足性问题和球体堆积问题两个基准测试中说明了其有效性和竞争性。

    Dec, 2007

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

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

    Jul, 2010

  • 破解对称性的复杂性

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

    May, 2020

  • BreakID: ASP 的静态对称性破坏（系统说明）

    本文将最新的 SAT 对称性破解器 BreakID 移植到 ASP，并与当前最先进的对称性破解器 sbass 进行比较，产生了一个可插入 ASP 建模期间的轻量级工具

    Aug, 2016

  • 利用对称性提升可满足性检查

    使用对称性压缩结构来解决满足性问题，通过将句子转化为能够进行领域压缩的句子，检查满足性并找到满足条件的结构，其适用于生成配置问题。

    Nov, 2023