On Duality Gap in Binary Quadratic Programming

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$.


Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong, August/2008



View On Duality Gap in Binary Quadratic Programming