On reduction of duality gap in quadratic knapsack problems

X. J. Zheng; X. L. Sun; D. Li; Y. F. Xu

doi:10.1007/s10898-012-9872-9

On reduction of duality gap in quadratic knapsack problems

X. J. Zheng
, X. L. Sun^*
, D. Li
, Y. F. Xu

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

1 Citation (Scopus)

Abstract

We investigate in this paper the duality gap between quadratic knapsack problem and its Lagrangian dual or semidefinite programming relaxation.We characterize the duality gap by a distance measure from set {0, 1}ⁿ to certain polyhedral set and demonstrate that the duality gap can be reduced by an amount proportional to the square of the distance. We further discuss how to compute the distance measure via cell enumeration method and to derive the corresponding improved upper bound of the problem.

Original language	English
Pages (from-to)	325-339
Journal	Journal of Global Optimization
Volume	54
Issue number	2
Online published	19 Feb 2012
DOIs	https://doi.org/10.1007/s10898-012-9872-9
Publication status	Published - Oct 2012
Externally published	Yes

Research Keywords

Cell enumeration
Duality gap
Lagrangian relaxation
Quadratic knapsack problem
SDP relaxation

Access Output

10.1007/s10898-012-9872-9

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{b50c61764152462aa8889cf0855a8741,

title = "On reduction of duality gap in quadratic knapsack problems",

abstract = "We investigate in this paper the duality gap between quadratic knapsack problem and its Lagrangian dual or semidefinite programming relaxation.We characterize the duality gap by a distance measure from set \{0, 1\}n to certain polyhedral set and demonstrate that the duality gap can be reduced by an amount proportional to the square of the distance. We further discuss how to compute the distance measure via cell enumeration method and to derive the corresponding improved upper bound of the problem.",

keywords = "Cell enumeration, Duality gap, Lagrangian relaxation, Quadratic knapsack problem, SDP relaxation",

author = "Zheng, \{X. J.\} and Sun, \{X. L.\} and D. Li and Xu, \{Y. F.\}",

year = "2012",

month = oct,

doi = "10.1007/s10898-012-9872-9",

language = "English",

volume = "54",

pages = "325--339",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - On reduction of duality gap in quadratic knapsack problems

AU - Zheng, X. J.

AU - Sun, X. L.

AU - Li, D.

AU - Xu, Y. F.

PY - 2012/10

Y1 - 2012/10

N2 - We investigate in this paper the duality gap between quadratic knapsack problem and its Lagrangian dual or semidefinite programming relaxation.We characterize the duality gap by a distance measure from set {0, 1}n to certain polyhedral set and demonstrate that the duality gap can be reduced by an amount proportional to the square of the distance. We further discuss how to compute the distance measure via cell enumeration method and to derive the corresponding improved upper bound of the problem.

AB - We investigate in this paper the duality gap between quadratic knapsack problem and its Lagrangian dual or semidefinite programming relaxation.We characterize the duality gap by a distance measure from set {0, 1}n to certain polyhedral set and demonstrate that the duality gap can be reduced by an amount proportional to the square of the distance. We further discuss how to compute the distance measure via cell enumeration method and to derive the corresponding improved upper bound of the problem.

KW - Cell enumeration

KW - Duality gap

KW - Lagrangian relaxation

KW - Quadratic knapsack problem

KW - SDP relaxation

UR - https://www.scopus.com/pages/publications/84867276071

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84867276071&origin=recordpage

U2 - 10.1007/s10898-012-9872-9

DO - 10.1007/s10898-012-9872-9

M3 - RGC 21 - Publication in refereed journal

SN - 0925-5001

VL - 54

SP - 325

EP - 339

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 2

ER -

On reduction of duality gap in quadratic knapsack problems

Abstract

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this