We study subclasses of the quadratic knapsack problem, 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 the 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 new class of test instances for which finding a good solution is much harder. We support this by theoretical observations as well as by performing computational experiments.
Citation
University of Graz, Department of Statistics and Operations Research, Universitaetsstr. 15, A-8010 Graz, Austria