Improved estimation of duality gap in binary quadratic programming using a weighted distance measure

DOI10.1016/J.EJOR.2011.10.034MaRDI QIDQ439501zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Yong Xia, Ruey-Lin Sheu, Xiaoling Sun, Duan Li

Publication date 16 August 2012

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2011.10.034

zbMATH Keywords

semidefinite relaxationquadratic binary programmingcell enumeration and hyperplane arrangementLagrangian duality gapweighted distance measure

Mathematics Subject Classification ID

Quadratic programming (90C20) Integer programming (90C10) Boolean programming (90C09)

Recommendations

• Duality gap estimation of linear equality constrained binary quadratic programming
• On duality gap in binary quadratic programming
• On reduction of duality gap in quadratic knapsack problems
• On The Reduction of Duality Gap in Box Constrained Nonconvex Quadratic Program
• Parametric Lagrangian dual for the binary quadratic programming problem

Cites work

• scientific article; zbMATH DE number 4070633 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1383707 (Why is no real title available?)
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Duality gap estimation of linear equality constrained binary quadratic programming
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Nonlinear Programming
• On The Reduction of Duality Gap in Box Constrained Nonconvex Quadratic Program
• On duality gap in binary quadratic programming
• On the gap between the quadratic integer programming problem and its semidefinite relaxation
• Reverse search for enumeration
• Semidefinite Programming
• Semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
• Solving the maximum edge weight clique problem via unconstrained quadratic programming
• Spectral bounds for the maximum cut problem
• Towards strong duality in integer programming

Cited in

(4)

• scientific article; zbMATH DE number 7400716 (Why is no real title available?)
• Duality gap estimation of linear equality constrained binary quadratic programming
• New semidefinite programming relaxations for box constrained quadratic program
• On duality gap in binary quadratic programming

Describes a project that uses

Uses Software

• CVX

This page was built for publication: Improved estimation of duality gap in binary quadratic programming using a weighted distance measure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439501)