Parametric convex quadratic relaxation of the quadratic knapsack problem

M. Fampa, D. Lubke, F. Wang and H. Wolkowicz

European Journal of Operational Research, 2020, vol. 281, issue 1, 36-49

Abstract: 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.

Keywords: Quadratic knapsack problem; Quadratic binary programming; Convex quadratic programming relaxations; Parametric optimization; Valid inequalities (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719306976
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:281:y:2020:i:1:p:36-49

DOI: 10.1016/j.ejor.2019.08.027

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().