A new upper bound for the 0–1 quadratic knapsack problem

The 0–1 quadratic knapsack problem (QKP) consists in maximizing a positive quadratic pseudo-Boolean function subject to a linear capacity constraint. We present in this paper a new method, based on Lagrangian decomposition, for computing an upper bound of QKP. We report computational experiments which demonstrate the sharpness of the bound (relative error very often less than 1%) for large size instances (up to 500 variables).