School of Electronic Engineering and Computer Science

Dr. John H. Drake

Menu

MKP - Problem Instances

Quick Links: Chu and Beasley, Glover and Kochenberger, SAC-94

Here, all benchmarks instances from three well known multidimensional knapsack problem (MKP) libraries are provided in a standard format, as used in Drake et al. (2016). This includes:
  • The SAC-94 dataset, based on a variety of real-world problems.
  • The ORLib dataset proposed by Chu and Beasley (1998).
  • The GK dataset proposed by Glover and Kochenberger (n.d).
We would appreciate it if any use of these files is credited with a reference to Drake et al. (2016).

The format of these data files is:
#Variables (n), #Constraints (m), Optimal value (0 if unavailable)
Profit P(j) for each n
n x m matrix of constraints
Capacity b(i) for each m

Download all three benchmark libraries .zip .rar

References:
Chu, P. C. and Beasley, J. E. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4(1):63–86.
Drake, J. H., Ozcan, E. and Burke, E. K. (2016) A Case Study of Controlling Crossover in a Selection Hyper-heuristic Framework using the Multidimensional Knapsack Problem. Evolutionary Computation, 24 (1):113–141.
Glover, F. and Kochenberger, G. (n.d.). Benchmarks for ”the multiple knapsack problem". http://hces.bus.olemiss.edu/tools.html
Chu and Beasley Instances [top]
All Chu and Beasley instances .zip .rar

5 Constraints (m), 100 Variables (n), Tightness Ratio 0.25
OR5x100-0.25_1.dat
OR5x100-0.25_2.dat
OR5x100-0.25_3.dat
OR5x100-0.25_4.dat
OR5x100-0.25_5.dat
OR5x100-0.25_6.dat
OR5x100-0.25_7.dat
OR5x100-0.25_8.dat
OR5x100-0.25_9.dat
OR5x100-0.25_10.dat
5 Constraints (m), 100 Variables (n), Tightness Ratio 0.50
OR5x100-0.50_1.dat
OR5x100-0.50_2.dat
OR5x100-0.50_3.dat
OR5x100-0.50_4.dat
OR5x100-0.50_5.dat
OR5x100-0.50_6.dat
OR5x100-0.50_7.dat
OR5x100-0.50_8.dat
OR5x100-0.50_9.dat
OR5x100-0.50_10.dat

5 Constraints (m), 100 Variables (n), Tightness Ratio 0.75
OR5x100-0.75_1.dat
OR5x100-0.75_2.dat
OR5x100-0.75_3.dat
OR5x100-0.75_4.dat
OR5x100-0.75_5.dat
OR5x100-0.75_6.dat
OR5x100-0.75_7.dat
OR5x100-0.75_8.dat
OR5x100-0.75_9.dat
OR5x100-0.75_10.dat
5 Constraints (m), 250 Variables (n), Tightness Ratio 0.25
OR5x250-0.25_1.dat
OR5x250-0.25_2.dat
OR5x250-0.25_3.dat
OR5x250-0.25_4.dat
OR5x250-0.25_5.dat
OR5x250-0.25_6.dat
OR5x250-0.25_7.dat
OR5x250-0.25_8.dat
OR5x250-0.25_9.dat
OR5x250-0.25_10.dat
5 Constraints (m), 250 Variables (n), Tightness Ratio 0.50
OR5x250-0.50_1.dat
OR5x250-0.50_2.dat
OR5x250-0.50_3.dat
OR5x250-0.50_4.dat
OR5x250-0.50_5.dat
OR5x250-0.50_6.dat
OR5x250-0.50_7.dat
OR5x250-0.50_8.dat
OR5x250-0.50_9.dat
OR5x250-0.50_10.dat
5 Constraints (m), 250 Variables (n), Tightness Ratio 0.75
OR5x250-0.75_1.dat
OR5x250-0.75_2.dat
OR5x250-0.75_3.dat
OR5x250-0.75_4.dat
OR5x250-0.75_5.dat
OR5x250-0.75_6.dat
OR5x250-0.75_7.dat
OR5x250-0.75_8.dat
OR5x250-0.75_9.dat
OR5x250-0.75_10.dat

5 Constraints (m), 500 Variables (n), Tightness Ratio 0.25
OR5x500-0.25_1.dat
OR5x500-0.25_2.dat
OR5x500-0.25_3.dat
OR5x500-0.25_4.dat
OR5x500-0.25_5.dat
OR5x500-0.25_6.dat
OR5x500-0.25_7.dat
OR5x500-0.25_8.dat
OR5x500-0.25_9.dat
OR5x500-0.25_10.dat
5 Constraints (m), 500 Variables (n), Tightness Ratio 0.50
OR5x500-0.50_1.dat
OR5x500-0.50_2.dat
OR5x500-0.50_3.dat
OR5x500-0.50_4.dat
OR5x500-0.50_5.dat
OR5x500-0.50_6.dat
OR5x500-0.50_7.dat
OR5x500-0.50_8.dat
OR5x500-0.50_9.dat
OR5x500-0.50_10.dat
5 Constraints (m), 500 Variables (n), Tightness Ratio 0.75
OR5x500-0.75_1.dat
OR5x500-0.75_2.dat
OR5x500-0.75_3.dat
OR5x500-0.75_4.dat
OR5x500-0.75_5.dat
OR5x500-0.75_6.dat
OR5x500-0.75_7.dat
OR5x500-0.75_8.dat
OR5x500-0.75_9.dat
OR5x500-0.75_10.dat

10 Constraints (m), 100 Variables (n), Tightness Ratio 0.25
OR10x100-0.25_1.dat
OR10x100-0.25_2.dat
OR10x100-0.25_3.dat
OR10x100-0.25_4.dat
OR10x100-0.25_5.dat
OR10x100-0.25_6.dat
OR10x100-0.25_7.dat
OR10x100-0.25_8.dat
OR10x100-0.25_9.dat
OR10x100-0.25_10.dat
10 Constraints (m), 100 Variables (n), Tightness Ratio 0.50
OR10x100-0.50_1.dat
OR10x100-0.50_2.dat
OR10x100-0.50_3.dat
OR10x100-0.50_4.dat
OR10x100-0.50_5.dat
OR10x100-0.50_6.dat
OR10x100-0.50_7.dat
OR10x100-0.50_8.dat
OR10x100-0.50_9.dat
OR10x100-0.50_10.dat

10 Constraints (m), 100 Variables (n), Tightness Ratio 0.75
OR10x100-0.75_1.dat
OR10x100-0.75_2.dat
OR10x100-0.75_3.dat
OR10x100-0.75_4.dat
OR10x100-0.75_5.dat
OR10x100-0.75_6.dat
OR10x100-0.75_7.dat
OR10x100-0.75_8.dat
OR10x100-0.75_9.dat
OR10x100-0.75_10.dat
10 Constraints (m), 250 Variables (n), Tightness Ratio 0.25
OR10x250-0.25_1.dat
OR10x250-0.25_2.dat
OR10x250-0.25_3.dat
OR10x250-0.25_4.dat
OR10x250-0.25_5.dat
OR10x250-0.25_6.dat
OR10x250-0.25_7.dat
OR10x250-0.25_8.dat
OR10x250-0.25_9.dat
OR10x250-0.25_10.dat
10 Constraints (m), 250 Variables (n), Tightness Ratio 0.50
OR10x250-0.50_1.dat
OR10x250-0.50_2.dat
OR10x250-0.50_3.dat
OR10x250-0.50_4.dat
OR10x250-0.50_5.dat
OR10x250-0.50_6.dat
OR10x250-0.50_7.dat
OR10x250-0.50_8.dat
OR10x250-0.50_9.dat
OR10x250-0.50_10.dat

10 Constraints (m), 250 Variables (n), Tightness Ratio 0.75
OR10x250-0.75_1.dat
OR10x250-0.75_2.dat
OR10x250-0.75_3.dat
OR10x250-0.75_4.dat
OR10x250-0.75_5.dat
OR10x250-0.75_6.dat
OR10x250-0.75_7.dat
OR10x250-0.75_8.dat
OR10x250-0.75_9.dat
OR10x250-0.75_10.dat
10 Constraints (m), 500 Variables (n), Tightness Ratio 0.25
OR10x500-0.25_1.dat
OR10x500-0.25_2.dat
OR10x500-0.25_3.dat
OR10x500-0.25_4.dat
OR10x500-0.25_5.dat
OR10x500-0.25_6.dat
OR10x500-0.25_7.dat
OR10x500-0.25_8.dat
OR10x500-0.25_9.dat
OR10x500-0.25_10.dat
10 Constraints (m), 500 Variables (n), Tightness Ratio 0.50
OR10x500-0.50_1.dat
OR10x500-0.50_2.dat
OR10x500-0.50_3.dat
OR10x500-0.50_4.dat
OR10x500-0.50_5.dat
OR10x500-0.50_6.dat
OR10x500-0.50_7.dat
OR10x500-0.50_8.dat
OR10x500-0.50_9.dat
OR10x500-0.50_10.dat
10 Constraints (m), 500 Variables (n), Tightness Ratio 0.75
OR10x500-0.75_1.dat
OR10x500-0.75_2.dat
OR10x500-0.75_3.dat
OR10x500-0.75_4.dat
OR10x500-0.75_5.dat
OR10x500-0.75_6.dat
OR10x500-0.75_7.dat
OR10x500-0.75_8.dat
OR10x500-0.75_9.dat
OR10x500-0.75_10.dat

30 Constraints (m), 100 Variables (n), Tightness Ratio 0.25
OR30x100-0.25_1.dat
OR30x100-0.25_2.dat
OR30x100-0.25_3.dat
OR30x100-0.25_4.dat
OR30x100-0.25_5.dat
OR30x100-0.25_6.dat
OR30x100-0.25_7.dat
OR30x100-0.25_8.dat
OR30x100-0.25_9.dat
OR30x100-0.25_10.dat
30 Constraints (m), 100 Variables (n), Tightness Ratio 0.50
OR30x100-0.50_1.dat
OR30x100-0.50_2.dat
OR30x100-0.50_3.dat
OR30x100-0.50_4.dat
OR30x100-0.50_5.dat
OR30x100-0.50_6.dat
OR30x100-0.50_7.dat
OR30x100-0.50_8.dat
OR30x100-0.50_9.dat
OR30x100-0.50_10.dat
30 Constraints (m), 100 Variables (n), Tightness Ratio 0.75
OR30x100-0.75_1.dat
OR30x100-0.75_2.dat
OR30x100-0.75_3.dat
OR30x100-0.75_4.dat
OR30x100-0.75_5.dat
OR30x100-0.75_6.dat
OR30x100-0.75_7.dat
OR30x100-0.75_8.dat
OR30x100-0.75_9.dat
OR30x100-0.75_10.dat

30 Constraints (m), 250 Variables (n), Tightness Ratio 0.25
OR30x250-0.25_1.dat
OR30x250-0.25_2.dat
OR30x250-0.25_3.dat
OR30x250-0.25_4.dat
OR30x250-0.25_5.dat
OR30x250-0.25_6.dat
OR30x250-0.25_7.dat
OR30x250-0.25_8.dat
OR30x250-0.25_9.dat
OR30x250-0.25_10.dat
30 Constraints (m), 250 Variables (n), Tightness Ratio 0.50
OR30x250-0.50_1.dat
OR30x250-0.50_2.dat
OR30x250-0.50_3.dat
OR30x250-0.50_4.dat
OR30x250-0.50_5.dat
OR30x250-0.50_6.dat
OR30x250-0.50_7.dat
OR30x250-0.50_8.dat
OR30x250-0.50_9.dat
OR30x250-0.50_10.dat
30 Constraints (m), 250 Variables (n), Tightness Ratio 0.75
OR30x250-0.75_1.dat
OR30x250-0.75_2.dat
OR30x250-0.75_3.dat
OR30x250-0.75_4.dat
OR30x250-0.75_5.dat
OR30x250-0.75_6.dat
OR30x250-0.75_7.dat
OR30x250-0.75_8.dat
OR30x250-0.75_9.dat
OR30x250-0.75_10.dat

30 Constraints (m), 500 Variables (n), Tightness Ratio 0.25
OR30x500-0.25_1.dat
OR30x500-0.25_2.dat
OR30x500-0.25_3.dat
OR30x500-0.25_4.dat
OR30x500-0.25_5.dat
OR30x500-0.25_6.dat
OR30x500-0.25_7.dat
OR30x500-0.25_8.dat
OR30x500-0.25_9.dat
OR30x500-0.25_10.dat
30 Constraints (m), 500 Variables (n), Tightness Ratio 0.50
OR30x500-0.50_1.dat
OR30x500-0.50_2.dat
OR30x500-0.50_3.dat
OR30x500-0.50_4.dat
OR30x500-0.50_5.dat
OR30x500-0.50_6.dat
OR30x500-0.50_7.dat
OR30x500-0.50_8.dat
OR30x500-0.50_9.dat
OR30x500-0.50_10.dat
30 Constraints (m), 500 Variables (n), Tightness Ratio 0.75
OR30x500-0.75_1.dat
OR30x500-0.75_2.dat
OR30x500-0.75_3.dat
OR30x500-0.75_4.dat
OR30x500-0.75_5.dat
OR30x500-0.75_6.dat
OR30x500-0.75_7.dat
OR30x500-0.75_8.dat
OR30x500-0.75_9.dat
OR30x500-0.75_10.dat


Glover and Kochenberger Instances [top]
All Glover and Kochenberger instances .zip .rar

GK01.dat
GK02.dat
GK03.dat
GK04.dat
GK05.dat
GK06.dat
GK07.dat
GK08.dat
GK09.dat
GK10.dat
GK11.dat


SAC-94 Instances [top]
All SAC-94 instances .zip .rar

A. Freville and G. Plateau
hp1.dat
hp2.dat
pb1.dat
pb2.dat
pb4.dat
pb5.dat
pb6.dat
pb7.dat
C.C. Petersen
pet2.dat
pet3.dat
pet4.dat
pet5.dat
pet6.dat
pet7.dat
S. Senyu and Y. Toyada
sento1.dat
sento2.dat
H.M. Weingartner and D.N. Ness
weing1.dat
weing2.dat
weing3.dat
weing4.dat
weing5.dat
weing6.dat
weing7.dat
weing8.dat
W. Shi
weish01.dat
weish02.dat
weish03.dat
weish04.dat
weish05.dat
weish06.dat
weish07.dat
weish08.dat
weish09.dat
weish10.dat
weish11.dat
weish12.dat
weish13.dat
weish14.dat
weish15.dat
weish16.dat
weish17.dat
weish18.dat
weish19.dat
weish20.dat
weish21.dat
weish22.dat
weish23.dat
weish24.dat
weish25.dat
weish26.dat
weish27.dat
weish28.dat
weish29.dat
weish30.dat

NB: This page was previously hosted at http://www.cs.nott.ac.uk/~jqd/mkp/index.html