Optimization Online


On Duality Gap in Binary Quadratic Programming

Xiaoling Sun(xls***at***fudan.edu.cn)
Chunli Liu (liu.chunli***at***shufe.edu.cn)
Duan Li(dli***at***se.cuhk.edu.hk)
Jianjun Gao(jjgao***at***se.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/2010
Entry Accepted: 01/03/2010
Entry Last Modified: 01/02/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society