Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming

DOI10.1287/moor.1100.0472zbMath1218.90129OpenAlexW2004655545WikidataQ57445460 ScholiaQ57445460MaRDI QIDQ3169124

Yong Xia, Li, Duan, Xiaoling Sun, Xiao Jin Zheng

Publication date: 27 April 2011

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.1100.0472

zbMATH Keywords

SDP relaxationduality gaplinear equality constraintsLagrangian dualcell enumerationbinary quadratic optimization

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Quadratic programming (90C20) Optimality conditions and duality in mathematical programming (90C46)

Related Items (7)

Tightening a copositive relaxation for standard quadratic optimization problems ⋮ A distributed optimization approach via symmetric group actions under time-varying communication networks ⋮ Improved estimation of duality gap in binary quadratic programming using a weighted distance measure ⋮ On duality gap in binary quadratic programming ⋮ 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

Uses Software

• CVX
• Biq Mac

This page was built for publication: Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming