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

DOI10.1016/j.disopt.2016.08.001zbMath1387.90175OpenAlexW2510996638MaRDI QIDQ1751225

Sunyoung Kim, Kojima, Masakazu

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.08.001

zbMATH Keywords

conic relaxationsbinary integer quadratic programhierarchy of semidefinite relaxationsinexact optimal valuesmax-cut problem with equal weight

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Quadratic programming (90C20)

Related Items

Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems, A Newton-bracketing method for a simple conic optimization problem

Uses Software

• SeDuMi
• SparsePOP
• GloptiPoly
• SparseCoLO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Global Optimization with Polynomials and the Problem of Moments
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• GloptiPoly
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems