Improving a Formulation of the Quadratic Knapsack Problem

Daniel Grainger(d.graingerlancaster.ac.uk)
Adam Letchford(A.N.Letchfordlancaster.ac.uk)

Abstract: The Quadratic Knapsack Problem can be formulated, using an idea of Glover, as a mixed 0-1 linear program with only 2n variables. We present a simple method for strengthening that formulation, which gives good results when the profit matrix is dense and non-negative.

Keywords: quadratic knapsack problem, integer programming.

Category 1: Integer Programming (0-1 Programming )

Citation: Working Paper, Department of Management Science, Lancaster University, May 2007.

Download: [PDF]

Entry Submitted: 06/07/2007
Entry Accepted: 06/07/2007
Entry Last Modified: 06/07/2007

Modify/Update this entry