On Integrality in Semidefinite Programming for Discrete Optimization
Authors:
- 15 March 2024
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 34 (1) , 1071-1096
Abstract
It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed-integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems.Keywords
All Related Versions
This publication has 42 references indexed in Scilit:
- Handling Symmetries in Mixed-Integer Semidefinite Programs2023
- Relaxations of Combinatorial Problems Via Association Schemes2011
- Semidefinite Relaxations for Integer Programming2009
- The clique partitioning problem: Facets and patching facetsNetworks, 2001
- Semidefinite Programming Methods for the Symmetric Traveling Salesman ProblemLecture Notes in Computer Science, 1999
- Connections between semidefinite relaxations of the max-cut and stable set problemsMathematical Programming, 1997
- The partition problemMathematical Programming, 1993
- Facets of the clique partitioning polytopeMathematical Programming, 1990
- The boolean quadric polytope: Some characteristics, facets and relativesMathematical Programming, 1989
- Geometric Algorithms and Combinatorial Optimization1988