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.

Time: Fri 2017-10-06 11.00 - 12.00

Lecturer: Fei Wang

Location: Seminar room F11, Lindstedtsvägen 22

2017-10-06T11:00 2017-10-06T12:00 Semidefinite Relaxations of the Quadratic Knapsack Problem Semidefinite Relaxations of the Quadratic Knapsack Problem
Top page top