Semidefinite Relaxations of the Quadratic Knapsack Problem

We consider convex relaxations for the quadratic knapsack problem,
QKP. We use a parametric convex quadratic semidefinite programming
relaxation. This maintains partial quadratic information from the
original QKP by perturbing the quadratic form to obtain a convex
quadratic term and then linearizing the concave remainder. Our best
bounds are obtained from alternating between optimizing the parametric
quadratic SDP relaxation over the perturbation and finding and adding
a best cutting plane.