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

*(English)*Zbl 1387.90175Summary: 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 \(\lceil n/2\rceil\) to attain the optimal value. The bound \(\lceil n/2\rceil\) for the max-cut problem of a graph with equal weight is consistent with M. Laurent’s conjecture in [Math. Oper. Res. 28, No. 4, 871–883 (2003; Zbl 1082.90085)], which was proved recently by H. Fawzi et al. in [“Sparse sum-of-squares certificates on finite abelian groups”, Preprint, arXiv:1503.01207].

##### Keywords:

binary integer quadratic program; max-cut problem with equal weight; conic relaxations; hierarchy of semidefinite relaxations; inexact optimal values
PDF
BibTeX
XML
Cite

\textit{S. Kim} and \textit{M. Kojima}, Discrete Optim. 24, 170--183 (2017; Zbl 1387.90175)

Full Text:
DOI

##### References:

[1] | Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 1115-1145, (1995) · Zbl 0885.68088 |

[2] | Burer, S., On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 479-495, (2009) · Zbl 1180.90234 |

[3] | Arima, N.; Kim, S.; Kojima, M., Simplified copositive and Lagrangian relaxations for linearly constrained quadratic optimization problems in continuous and binary variables, Pac. J. Optim., 10, 437-451, (2014) · Zbl 1327.90161 |

[4] | Kim, S.; Kojima, M.; Toh, K. C., A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems, Math. Program., 156, 161-187, (2016) · Zbl 1342.90123 |

[5] | Lasserre, J. B., Global optimization with polynomials and the problems of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061 |

[6] | Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M., Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17, 218-242, (2006) · Zbl 1109.65058 |

[7] | Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M.; Sugimoto, H., Sparsepop: a sparse semidefinite programming relaxation of polynomial optimization problems, ACM Trans. Math. Software, 35, 2, 15, (2008) |

[8] | Lasserre, J. B., An explicit exact SDP relaxation for nonlinear 0-1 programs, (Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, (2001), Springer-Verlag London, UK), 293-303 · Zbl 1010.90515 |

[9] | Laurent, M., Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope, Math. Oper. Res., 28, 781-883, (2003) · Zbl 1082.90085 |

[10] | H. Fawzi, J. Saunderson, P.A. Parrilo, Sparse sum-of-squares certificates on finite abelian groups, 2015. arXiv:1503.01207. · Zbl 1327.90175 |

[11] | Sakaue, Shinsaku; Takeda, Akiko; Kim, Sunyoung; Ito, Naoki, Exact SDP relaxations with truncated moment matrix for binary polynomial optimization problems, (Mathematical Engineering Technical Reports, 2016-01, (2016), The University of Tokyo) · Zbl 1367.90080 |

[12] | Waki, H.; Muramatsu, M.; Kojima, M., Invariance under affine transformation in semidefinite programming relaxation for polynomial optimization problems, Pac. J. Optim., 5, 297-312, (2009) · Zbl 1192.90138 |

[13] | Fujisawa, K.; Kim, S.; Kojima, M.; Okamoto, Y.; Yamashita, M., Userâ€™s manual for sparsecolo: conversion methods for SPARSE conic-form linear optimization problems, research report B-453, (2009), Dept. of Math. and Comp. Sciecne, Tokyo Institute of Technology Tokyo, Japan |

[14] | Strum, J. F., Sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11 & 12, 625-653, (1999) · Zbl 0973.90526 |

[15] | Henrion, D.; Lasserre, J. B., Gloptipoly: global optimization over polynomials with Matlab and sedumi, ACM Trans. Math. Software, 29, 165-194, (2003) · Zbl 1070.65549 |

[16] | Watkins, D. S., Fundamentals of matrix computations, (2004), John Wiley & Sons |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.