Optimization Online


Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems

Naoki Ito (naoki ito***at***mist.i.u-tokyo.ac.jp)
Sunyoung Kim (skim***at***ewha.ac.kr)
Masakazu Kojima (masakazukojima***at***mac.com)
Akiko Takeda (atakeda***at***ism.ac.jp)
Kim-Chuan Toh (mattohkc***at***nus.edu.sg)

Abstract: Various conic relaxations of quadratic optimization problems in nonnega- tive 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 combi- natorial optimization problems can be expressed in several ways, each of which results in different conic relaxations. For the completely positive, doubly nonnegative and semidefi- nite relaxations of the combinatorial optimization problems, we prove the equivalences and differences among the relaxations by investigating the feasible regions obtained from dif- ferent representations of the combinatorial condition, 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 results on QAP instances solved by SDPT3, SDPNAL+ and the bisection and projection method.

Keywords: ombinatorial optimization problems, binary and complementarity con- dition, completely positive relaxations, doubly nonnegative relaxations, semidefinite relax- ations, equivalence of feasible regions, nondegeneracy

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 07/22/2017
Entry Accepted: 07/22/2017
Entry Last Modified: 07/22/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society