Improved estimation of duality gap in binary quadratic programming using a weighted distance measure
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 351-357 |
| Journal / Publication | European Journal of Operational Research |
| Volume | 218 |
| Issue number | 2 |
| Online published | 9 Nov 2011 |
| Publication status | Published - 16 Apr 2012 |
| Externally published | Yes |
Link(s)
Abstract
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.
Research Area(s)
- Cell enumeration and hyperplane arrangement, Lagrangian duality gap, Quadratic binary programming, Semidefinite relaxation, Weighted distance measure
Citation Format(s)
Improved estimation of duality gap in binary quadratic programming using a weighted distance measure. / Xia, Yong; Sheu, Ruey-Lin; Sun, Xiaoling et al.
In: European Journal of Operational Research, Vol. 218, No. 2, 16.04.2012, p. 351-357.
In: European Journal of Operational Research, Vol. 218, No. 2, 16.04.2012, p. 351-357.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
