Partial Lasserre relaxation for sparse Max-Cut
Partial Lasserre relaxation for sparse Max-Cut
复制标题
DOI：
10.1007/s11081-022-09763-y
复制
发表时间：
2022-08
影响因子：
2.1
通讯作者：
Juan S. Campos;R. Misener;P. Parpas
中科院分区：
文献类型：
--
作者：
Juan S. Campos;R. Misener;P. Parpas
解决或找到像Max-Cut这样的多项式优化问题的边界的常见方法是使用拉瑟尔层次结构的第一级。拉瑟尔层次的更高级别提供更严格的界限，但解决这些松弛通常是计算上棘手的。我们建议加强第一级松弛稀疏最大割问题使用的约束，从二阶拉瑟尔层次。我们探索了各种方法添加一个子集的正半定约束的二阶稀疏松弛通过使用图的弦扩展的最大团。我们将这个想法应用于不同大小和密度的稀疏图，并与最先进的最大切割求解器BiqCrunch和替代稀疏松弛CS-TSSOS相比，提供了其优势和局限性的证据。
A common approach to solve or find bounds of polynomial optimization problems like Max-Cut is to use the first level of the Lasserre hierarchy. Higher levels of the Lasserre hierarchy provide tighter bounds, but solving these relaxations is usually computationally intractable. We propose to strengthen the first level relaxation for sparse Max-Cut problems using constraints from the second order Lasserre hierarchy. We explore a variety of approaches for adding a subset of the positive semidefinite constraints of the second order sparse relaxation obtained by using the maximum cliques of the graph’s chordal extension. We apply this idea to sparse graphs of different sizes and densities, and provide evidence of its strengths and limitations when compared to the state-of-the-art Max-Cut solver BiqCrunch and the alternative sparse relaxation CS-TSSOS.