2022/01/25 by Frank de Meijer, de Meijer, Frank, Renata Sotirov +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #FOS: Mathematics #Optimization and Control (math.OC) #Process Optimization and Integration
paper · doi:10.48550/arxiv.2201.10224
openalex publication_date 2022/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.