Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems

N. Ito, S. Kim, M. Kojima, A. Takeda, K. C. Toh

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Various conic relaxations of quadratic optimization problems in nonnegative variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combinatorial optimization problems can be expressed in several ways, each of which results in different conic relaxations. For the completely positive, doubly nonnegative and semidefinite relaxations of the combinatorial optimization problems, we discuss the equivalences and differences among the relaxations by investigating the feasible regions obtained from different representations of the combinatorial condition which we propose as a generalization of the binary and complementarity condition. We also study theoretically the issue of the primal and dual nondegeneracy, the existence of an interior solution and the size of the relaxations, as a result of different representations of the combinatorial condition. These characteristics of the conic relaxations affect the numerical efficiency and stability of the solver used to solve them. We illustrate the theoretical results with numerical experiments on QAP instances solved by SDPT3, SDPNAL+ and the bisection and projection method.

Original languageEnglish
Pages (from-to)619-653
Number of pages35
JournalJournal of Global Optimization
Issue number4
StatePublished - 1 Dec 2018

Bibliographical note

Funding Information:
N. Ito: This work was supported by Grant-in-Aid for JSPS Research Fellowship JP17J07365. S. Kim: The research was supported by 2017-R1A2B2005119. M. Kojima: This research was supported by Grant-in-Aid for Scientific Research (A) 26242027 and the Japan Science and Technology Agency (JST), the Core Research of Evolutionary Science and Technology (CREST) research project. A. Takeda: The work of this author was supported by Grant-in-Aid for Scientific Research (C), 15K00031.

Publisher Copyright:
© 2018, Springer Science+Business Media, LLC, part of Springer Nature.


  • Binary and complementarity condition
  • Combinatorial quadratic optimization problems
  • Completely positive relaxations
  • Doubly nonnegative relaxations
  • Equivalence of feasible regions
  • Nondegeneracy
  • Semidefinite relaxations


Dive into the research topics of 'Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems'. Together they form a unique fingerprint.

Cite this