TY - JOUR

T1 - Binary quadratic optimization problems that are difficult to solve by conic relaxations

AU - Kim, Sunyoung

AU - Kojima, Masakazu

N1 - Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - We study conic relaxations including semidefinite programming (SDP) relaxations and doubly nonnegative programming (DNN) relaxations to find the optimal values of binary QOPs. The main focus of the study is on how the relaxations perform with respect to the rank of the coefficient matrix in the objective of a binary QOP. More precisely, for a class of binary QOP instances, which include the max-cut problem of a graph with an odd number of nodes and equal weight, we show numerically that (1) neither the standard DNN relaxation nor the DNN relaxation derived from the completely positive formulation by Burer performs better than the standard SDP relaxation, and (2) Lasserre's hierarchy of SDP relaxations requires solving the SDP with the relaxation order at least ⌈n/2⌉ to attain the optimal value. The bound ⌈n/2⌉ for the max-cut problem of a graph with equal weight is consistent with Laurent's conjecture in 2003, which was proved recently by Fawzi, Saunderson and Parrilo in 2015.

AB - We study conic relaxations including semidefinite programming (SDP) relaxations and doubly nonnegative programming (DNN) relaxations to find the optimal values of binary QOPs. The main focus of the study is on how the relaxations perform with respect to the rank of the coefficient matrix in the objective of a binary QOP. More precisely, for a class of binary QOP instances, which include the max-cut problem of a graph with an odd number of nodes and equal weight, we show numerically that (1) neither the standard DNN relaxation nor the DNN relaxation derived from the completely positive formulation by Burer performs better than the standard SDP relaxation, and (2) Lasserre's hierarchy of SDP relaxations requires solving the SDP with the relaxation order at least ⌈n/2⌉ to attain the optimal value. The bound ⌈n/2⌉ for the max-cut problem of a graph with equal weight is consistent with Laurent's conjecture in 2003, which was proved recently by Fawzi, Saunderson and Parrilo in 2015.

KW - A hierarchy of semidefinite relaxations

KW - Binary integer quadratic program

KW - Conic relaxations

KW - Inexact optimal values

KW - The max-cut problem with equal weight

UR - http://www.scopus.com/inward/record.url?scp=85002820544&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2016.08.001

DO - 10.1016/j.disopt.2016.08.001

M3 - Article

AN - SCOPUS:85002820544

VL - 24

SP - 170

EP - 183

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

ER -