We provide an asymptotic analysis of the quadratic knapsack problem.

We show that an easy heuristic produces solutions which are almost optimal for large classes of test instances.

These include the standard benchmark instances of Gallo et al. (1980).

Hence using them for evaluating the performance of (meta-) heuristics is not very meaningful.

We give a new class of test instances that should be hard to solve.