کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
476858 | 1446082 | 2012 | 7 صفحه PDF | دانلود رایگان |
We present in this paper an improved estimation of duality gap between binary quadratic program and its Lagrangian dual. More specifically, we obtain this improved estimation using a weighted distance measure between the binary set and certain affine subspace. We show that the optimal weights can be computed by solving a semidefinite programming problem. We further establish a necessary and sufficient condition under which the weighted distance measure gives a strictly tighter estimation of the duality gap than the existing estimations.
► An improved estimate for the duality gap of binary quadratic programming is obtained.
► We use the weighted distance measure and the cell enumeration in discrete geometry.
► The optimal choice of the weighted matrix can be found via a SDP.
► We study conditions under which the weighted measure gives a strictly tighter bound.
Journal: European Journal of Operational Research - Volume 218, Issue 2, 16 April 2012, Pages 351–357