Probabilistic Analysis of the Multidimensional Knapsack Problem

We analyse the multi-constraint zero-one knapsack problem, under the assumption that all coefficients are drawn from a uniform [0, 1] distribution and there are m = 0(1) constraints as the number of variables grows. We show that results on the single-constraint problem can be extended to this situation. Chiefly, we generalise a result of Lueker on the duality gap, and a result of Goldberg/Marchetti-Spaccamela on exact solvability. In the latter case, our methods differ markedly from those for the single-constraint result.