Asymptotic behavior of the quadratic knapsack problem

• 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.

We study the quadratic knapsack problem on instances where the profits are independent random variables defined on the interval [0, 1] and the knapsack capacity is proportional to the number of items (we assume that the weights are arbitrary numbers from the interval [0, 1]). We show asymptotically that the objective value of a very easy heuristic is not far away from the optimal solution. More specifically we show that the ratio of the optimal solution and the objective value of this heuristic almost surely tends to 1 as the size of the knapsack instance tends to infinity. As a consequence using randomly generated instances following this scheme seems to be inappropriate for studying the performance of heuristics and (to some extend) exact methods. However such instances are frequently used in the literature for this purpose. Additionally we introduce a class of test instances based on hidden cliques for which finding a good solution is much harder. We support this by theoretical observations as well as by performing computational experiments.