On Integrality in Semidefinite Programming for Discrete Optimization

Frank de Meijer, Renata Sotirov

Research output: Contribution to journalArticleScientificpeer-review


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.

Original languageEnglish
Pages (from-to)1071-1096
Number of pages26
JournalSIAM Journal on Optimization
Issue number1
Publication statusPublished - 2023

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • mixed-integer semidefinite programming
  • discrete positive semidefinite matrices
  • binary quadratic programming
  • quadratic matrix programming
  • association schemes


Dive into the research topics of 'On Integrality in Semidefinite Programming for Discrete Optimization'. Together they form a unique fingerprint.

Cite this