- On Duality Gap in Binary Quadratic Programming Xiaoling Sun(xlsfudan.edu.cn) Chunli Liu (liu.chunlishufe.edu.cn) Duan Li(dlise.cuhk.edu.hk) Jianjun Gao(jjgaose.cuhk.edu.hk) Abstract: We present in this paper new results on the duality gap between the binary quadratic optimization problem and its Lagrangian dual or semidefinite programming relaxation. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the primal problem. We then characterize the zeroness of the duality gap by the distance, $\delta$, between $\{-1,1\}^n$ and certain affine subspace $C$ and show that the duality gap can be reduced by an amount proportional to $\delta^2$. We finally establish the connection between the computation of $\delta$ and cell enumeration of hyperplane arrangement in discrete geometry and further identify two polynomially solvable cases of computing $\delta$. Keywords: binary quadratic optimization; Lagrangian dual;semidefinite programming relaxation; cell enumeration of hyperplane arrangement Category 1: Integer Programming (0-1 Programming ) Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 3: Nonlinear Optimization (Quadratic Programming ) Citation: Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong, August/2008 Download: [PDF]Entry Submitted: 01/02/2010Entry Accepted: 01/03/2010Entry Last Modified: 01/02/2010Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.