Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming

Duality Gap Estimation of Linear Equality Constrained Binary Quadratic Programming

0.00 Avg rating0 Votes
Article ID: iaor20108772
Volume: 35
Issue: 4
Start Page Number: 864
End Page Number: 880
Publication Date: Nov 2010
Journal: Mathematics of Operations Research
Authors: , , ,
Keywords: duality, Lagrangian relaxation
Abstract:

We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the squared norm constraint reformulations are also discussed.

Reviews

Required fields are marked *. Your email address will not be published.