论文标题
整数SDP的Chvátal-Gomory程序，具有组合优化的应用
The Chvátal-Gomory Procedure for Integer SDPs with Applications in Combinatorial Optimization
论文作者
论文摘要
在本文中，我们研究了整个Integer Semidefinite程序（ISDPS）的众所周知的Chvátal-Gomory（CG）程序。我们证明了关于通过迭代此过程获得的放松层次结构的几个结果。我们还研究了谱的基本闭合的不同配方。通过利用SDP的总二一个完整性来得出了特定类型的Spectrahedra的基本闭合的多面体描述。此外，我们展示了如何利用ISDP的分支和切割框架中的CG切割（加强）CG。与文献中现有的算法不同，我们方法中的分离程序利用了半决赛和整数约束。我们为组合优化问题引起的几种常见的二进制SDP提供了分离例程。在本文的第二部分中，我们介绍了我们在二次旅行推销员问题（QTSP）中的方法的全面应用。基于定向汉密尔顿周期的代数连接性，引入了两个模型的ISDP。我们表明，由这些配方产生的CG削减包含几个著名的切割平面系列。数值结果说明了我们的分支和切割算法中CG切割的实际强度，该算法的表现优于替代ISDP求解器，并且能够将大型QTSP实例求解以达到最佳性。
In this paper we study the well-known Chvátal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of spectrahedra is derived by exploiting total dual integrality for SDPs. Moreover, we show how to exploit (strengthened) CG cuts in a branch-and-cut framework for ISDPs. Different from existing algorithms in the literature, the separation routine in our approach exploits both the semidefinite and the integrality constraints. We provide separation routines for several common classes of binary SDPs resulting from combinatorial optimization problems. In the second part of the paper we present a comprehensive application of our approach to the quadratic traveling salesman problem (QTSP). Based on the algebraic connectivity of the directed Hamiltonian cycle, two ISDPs that model the QTSP are introduced. We show that the CG cuts resulting from these formulations contain several well-known families of cutting planes. Numerical results illustrate the practical strength of the CG cuts in our branch-and-cut algorithm, which outperforms alternative ISDP solvers and is able to solve large QTSP instances to optimality.
