A computational study on the quadratic knapsack problem with multiple constraints

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 1, January 2012, Pages 3-11

Haibo, Wang , Gary, Kochenberger , Fred, Glover

The quadratic knapsack problem (QKP) has been the subject of considerable research in recent years. Despite notable advances in special purpose solution methodologies for QKP, this problem class remains very difficult to solve. With the exception of special cases, the state-of-the-art is limited to addressing problems of a few hundred variables and a single knapsack constraint.In this paper we provide a comparison of quadratic and linear representations of QKP based on test problems with multiple knapsack constraints and up to eight hundred variables. For the linear representations, three standard linearizations are investigated. Both the quadratic and linear models are solved…