On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
复制标题
关于 0/1 Lasserre 层次结构的最难问题公式
DOI：
10.1287/moor.2016.0797
复制
发表时间：
2015
影响因子：
0.7
通讯作者：
M. Mastrolilli
中科院分区：
文献类型：
--
作者：
Adam Kurpisz;Samuli Leppänen;M. Mastrolilli
Lasserre/Sum-of-Squares （SoS）层次结构是一个系统的过程，用于构造一个日益紧密的半定松弛序列。众所周知，该层次结构在n层中收敛到0/1多面体，并捕获用于各种优化问题的最佳可用近似算法中的凸松弛。在本文中，我们刻画了0/1整数线性问题和0/1无约束多项式优化问题的集合，它们在n - 1水平上仍然有一个完整的间隙。从这个意义上讲，这些问题对于Lasserre层次结构来说是最难的。
The Lasserre/Sum-of-Squares (SoS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems. In this paper we characterize the set of 0/1 integer linear problems and unconstrained 0/1 polynomial optimization problems that can still have an integrality gap at level n − 1. These problems are the hardest for the Lasserre hierarchy in this sense.