A note on dominance in unbounded knapsack problems

The phenomenon of dominance has been used in practice since the early 1960’s to reduce the solution time in solving knapsack problems. Simulation studies by Martello & Toth and Dudzinski confirmed that even very large randomly generated unbounded knapsack problems have few undominated items and therefore can be reduced to small core problems. This paper presents an analytical study of this phenomenon and discusses the results in the light of algorithm design. The authors show that for large problems the probability of there being only one undominated item in a randomly generated problem approaches 0.592 and that the expected number of undominated items approaches an average of 1.6 only.