Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems

N. Ito (), S. Kim (), M. Kojima (), A. Takeda () and K.-C. Toh ()
Additional contact information
N. Ito: FAST RETAILING CO., LTD.
S. Kim: Ewha W. University
M. Kojima: Chuo University
A. Takeda: The University of Tokyo
K.-C. Toh: National University of Singapore

Journal of Global Optimization, 2018, vol. 72, issue 4, No 2, 619-653

Abstract: Abstract 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.

Keywords: Combinatorial quadratic optimization problems; Binary and complementarity condition; Completely positive relaxations; Doubly nonnegative relaxations; Semidefinite relaxations; Equivalence of feasible regions; Nondegeneracy; 90C20; 90C22; 90C25; 90C26 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0676-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:72:y:2018:i:4:d:10.1007_s10898-018-0676-4

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0676-4

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().