Hard multidimensional multiple choice knapsack problems, an empirical study

Bing Han (1) , Jimmy Leblet (1) , Gwendal Simon (2, 1)

1 INFO - Département informatique
2 REOP - Réseaux d'opérateurs

Recent advances in algorithms for the multidimensional multiple choice knapsack problems have enabled us to solve rather large problem instances. However, these algorithms are evaluated with very limited benchmark instances. In this study, we propose new methods to systematically generate comprehensive benchmark instances. Some instances with special correlation properties between parameters are found to be several orders of magnitude harder than those currently used for benchmarking the algorithms. Experiments on an existing exact algorithm and two generic solvers show that instances whose weights are uncorrelated with the profits are easier compared with weakly or strongly correlated cases. Instances with classes containing similar set of profits for items and with weights strongly correlated to the profits are the hardest among all instance groups investigated. These hard instances deserve further study and understanding their properties may shed light to better algorithms.

Mots clés: Exact algorithm; Performance evaluation; Knapsack problem

Domaines: Interface homme-machine [cs.HC]; Réseaux et télécommunications [cs.NI]

Bing Han, Jimmy Leblet, Gwendal Simon. Hard multidimensional multiple choice knapsack problems, an empirical study. Computers and Operations Research, 2009, 37 (1), pp.172 - 181. ⟨10.1016/j.cor.2009.04.006⟩. ⟨hal-02367635⟩