Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Parametric Convex Quadratic Relaxation of the Quadratic Knapsack Problem
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.ORCID iD: 0000-0001-8978-5649
2019 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 281, no 1, p. 36-49Article in journal (Refereed) Published
Abstract [en]

We consider a parametric convex quadratic programming (CQP) relaxation for the quadratic knapsack problem (QKP). This relaxation maintains partial quadratic information from the original QKP by perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to matrix space. We present a primal-dual interior point method to optimize the perturbation of the quadratic function, in a search for the tightest upper bound for the QKP. We prove that the same perturbation approach, when applied in the context of semidefinite programming (SDP) relaxations of the QKP, cannot improve the upper bound given by the corresponding linear SDP relaxation. The result also applies to more general integer quadratic problems. Finally, we propose new valid inequalities on the lifted matrix variable, derived from cover and knapsack inequalities for the QKP, and present separation problems to generate cuts for the current solution of the CQP relaxation. Our best bounds are obtained alternating between optimizing the parametric quadratic relaxation over the perturbation and applying cutting planes generated by the valid inequalities proposed.

Place, publisher, year, edition, pages
2019. Vol. 281, no 1, p. 36-49
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-248416DOI: 10.1016/j.ejor.2019.08.027ISI: 000495480100004Scopus ID: 2-s2.0-85071384662OAI: oai:DiVA.org:kth-248416DiVA, id: diva2:1302914
Note

QCR 20190513. QC 20191204

Available from: 2019-04-08 Created: 2019-04-08 Last updated: 2019-12-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Wang, Fei
By organisation
Optimization and Systems Theory
In the same journal
European Journal of Operational Research
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 3 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf