Improved estimation of duality gap in binary quadratic programming using a weighted distance measure

Yong Xia, Ruey Lin Sheu, Xiaoling Sun, Duan Li

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)351-357
Number of pages7
JournalEuropean Journal of Operational Research
Volume218
Issue number2
DOIs
Publication statusPublished - 2012 Apr 16

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Improved estimation of duality gap in binary quadratic programming using a weighted distance measure'. Together they form a unique fingerprint.

Cite this