School of Electronic Engineering and Computer Science

Dr. John H. Drake

Menu

OR Library MKP - Best Known Solutions

Quick Link: Best Known Results

The 0-1 Multidimensional Knapsack Problem (MKP) is a well studied problem whose roots can be traced back to capital budgeting and project selection. The 270 OR Library instances are a standard benchmark library proposed by [ChuBeas:98]. Please send any new results and necessary references to: j.drake [at] qmul.ac.uk

The following table shows the number of instances for which optimal solutions are known for each type of instance (max 10) from OR Library:
m - number of constraints
5 10 30
n - number of variables
Tightness Ratio 100 250 500 100 250 500 100 250 500
0.25 10 10 10 10 10 10 10 0 0
0.5 10 10 10 10 10 10 10 0 0
0.75 10 10 10 10 10 10 10 7 0

Currently optimal solutions are known for 217 of the 270 instances.
The latest version of the best known results can be found here

All results marked by a * have been found in a large number of papers over the years. These results have been verified as optimal using CPLEX 12.5 in the following work:
  • John H. Drake, Ender Özcan and Edmund K. Burke. A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework using the Multidimensional Knapsack Problem. Evolutionary Computation, 24(1): 113-141 (2016). [pdf]
All other references can be found below:

[Boussier:10]
Sylvain Boussier, Michel Vasquez, Yannick Vimont, Saïd Hanafi and Philippe Michelon. A multi-level search strategy for the 0-1 Multidimensional Knapsack Problem. Discrete Applied Mathematics 158(2): 97-109 (2010)

[ChuBea:98]
P. C. Chu and J. E. Beasley. A Genetic Algorithm for the Multidimensional Knapsack Problem. J. Heuristics 4(1): 63-86 (1998)

[DelGro:12]
Federico Della Croce and Andrea Grosso. Improved core problem based heuristics for the 0-1 multi-dimensional knapsack problem. Computers & OR (COR) 39(1): 27-31 (2012)

[VasHao:01]
Michel Vasquez and Jin-Kao Hao. A Hybrid Approach for the 01 Multidimensional Knapsack problem. IJCAI 2001: 328-333

[VasVim:05]
Michel Vasquez and Yannick Vimont. Improved results on the 0-1 multidimensional knapsack problem. European Journal of Operational Research 165(1): 70-81 (2005)

[VimBouVas:08]
Yannick Vimont, Sylvain Boussier and Michel Vasquez. Reduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem. J. Comb. Optim. 15(2): 165-178 (2008)

[WilHan:09]
Christophe Wilbaut and Saïd Hanafi. New convergent heuristics for 0-1 mixed integer programming. European Journal of Operational Research 195(1): 62-74 (2009)


NB: This page was previously hosted at: http://www.cs.nott.ac.uk/~jqd/mkp/results.html.
Last updated: Thursday June 23rd, 2011