On the gap between the quadratic integer programming problem and its semidefinite relaxation

DOI10.1007/s10107-005-0692-2zbMath1111.90076OpenAlexW2121785204MaRDI QIDQ2492705

Yanyan Li

Publication date: 14 June 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0692-2

zbMATH Keywords

Linear matrix inequalitiesHyperplane arrangementsSemidefinite relaxationQuadratic integer programmingZonotopes

Mathematics Subject Classification ID

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

Related Items (14)

Causal state-feedback parameterizations in robust model predictive control ⋮ New semidefinite programming relaxations for box constrained quadratic program ⋮ An improved lower bound and approximation algorithm for binary constrained quadratic programming problem ⋮ Improved estimation of duality gap in binary quadratic programming using a weighted distance measure ⋮ On duality gap in binary quadratic programming ⋮ Global optimality conditions and optimization methods for quadratic integer programming problems ⋮ New bounds on the unconstrained quadratic integer programming problem ⋮ Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods ⋮ Parametric Lagrangian dual for the binary quadratic programming problem ⋮ Convex reformulation for binary quadratic programming problems via average objective value maximization ⋮ Spectral bounds for unconstrained \((- 1,1)\)-quadratic optimization problems ⋮ Immediate schedule adjustment and semidefinite relaxation ⋮ On linear conic relaxation of discrete quadratic programs ⋮ A note on semidefinite relaxation for 0-1 quadratic knapsack problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum rank and minimum trace of covariance matrices
• Extremal problems on the set of nonnegative definite matrices
• Laplacian eigenvalues and the maximum cut problem
• Computational aspects of the greatest lower bound to the reliability and constrained minimum trace factor analysis
• Improved approximations for max set splitting and max NAE SAT
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Reverse search for enumeration
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• The Vector Partition Problem for Convex Objective Functions
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Semidefinite relaxation and nonconvex quadratic optimization
• Maximally Robust Controllers for Multivariable Systems
• Convex Relaxations of (0, 1)-Quadratic Programming
• Partition of Space
• Handbook of semidefinite programming. Theory, algorithms, and applications
• A polynomial case of unconstrained zero-one quadratic optimization

This page was built for publication: On the gap between the quadratic integer programming problem and its semidefinite relaxation