Multi-Constraint Knapsack Problem: Results obtained for Glover-Kochenberger and Chu-Beasley instances

Results obtained using Gurobi for solving the multi-constraint knapsack problem, using models described in Mathematical Optimization: Solving Problems using Python and Gurobi. CPU time limited to 3600 seconds. (Click on values for selecting data to display.)

Benchmark references and sources:

A genetic algorithm for the multidimensional knapsack problem. Chu and Beasley. J Heuristics, 1998 vol. 4 (1) pp. 63-86.
Critical event tabu search for multidimensional knapsack problems. Glover and Kochenberger. In Meta-heuristics: theory and applications, 1996


Performance data
CPU time required
Number of solution failures
Solutions and bounds

Solutions obtained

Legend for columns in the next tables
Label	Description
mkp	standard formulation for the multi-constraint knapsack problem

Solutions and bounds obtained
Instance	Size	mkp
mk_gk01_15x100	1500	3766^*
mk_gk02_25x100	2500	3958^*
mk_gk03_25x150	3750	5656.0, 5659
mk_gk04_50x150	7500	5767.0, 5781
mk_gk05_25x200	5000	7561.0, 7568
mk_gk06_50x200	10000	7676.0, 7696
mk_gk07_25x500	12500	19219.0, 19229
mk_gk08_50x500	25000	18803.0, 18828
mk_gk09_25x1500	37500	58088.0, 58099
mk_gk10_50x1500	75000	57293.0, 57317
mk_gk11_100x2500	250000	95229.0, 95277
mknapcb1-01_5x100	500	24381^*
mknapcb1-02_5x100	500	24274^*
mknapcb1-03_5x100	500	23551^*
mknapcb1-04_5x100	500	23534^*
mknapcb1-05_5x100	500	23991^*
mknapcb1-06_5x100	500	24613^*
mknapcb1-07_5x100	500	25591^*
mknapcb1-08_5x100	500	23410^*
mknapcb1-09_5x100	500	24216^*
mknapcb1-10_5x100	500	24411^*
mknapcb1-11_5x100	500	42757^*
mknapcb1-12_5x100	500	42545^*
mknapcb1-13_5x100	500	41968^*
mknapcb1-14_5x100	500	45090^*
mknapcb1-15_5x100	500	42218^*
mknapcb1-16_5x100	500	42927^*
mknapcb1-17_5x100	500	42009^*
mknapcb1-18_5x100	500	45020^*
mknapcb1-19_5x100	500	43441^*
mknapcb1-20_5x100	500	44554^*
mknapcb1-21_5x100	500	59822^*
mknapcb1-22_5x100	500	62081^*
mknapcb1-23_5x100	500	59802^*
mknapcb1-24_5x100	500	60479^*
mknapcb1-25_5x100	500	61091^*
mknapcb1-26_5x100	500	58959^*
mknapcb1-27_5x100	500	61538^*
mknapcb1-28_5x100	500	61520^*
mknapcb1-29_5x100	500	59453^*
mknapcb1-30_5x100	500	59965^*
mknapcb2-01_5x250	1250	59312^*
mknapcb2-02_5x250	1250	61472^*
mknapcb2-03_5x250	1250	62130^*
mknapcb2-04_5x250	1250	59463^*
mknapcb2-05_5x250	1250	58951^*
mknapcb2-06_5x250	1250	60077^*
mknapcb2-07_5x250	1250	60414^*
mknapcb2-08_5x250	1250	61472^*
mknapcb2-09_5x250	1250	61885^*
mknapcb2-10_5x250	1250	58959^*
mknapcb2-11_5x250	1250	109109^*
mknapcb2-12_5x250	1250	109841^*
mknapcb2-13_5x250	1250	108508^*
mknapcb2-14_5x250	1250	109383^*
mknapcb2-15_5x250	1250	110720^*
mknapcb2-16_5x250	1250	110256^*
mknapcb2-17_5x250	1250	109040^*
mknapcb2-18_5x250	1250	109042^*
mknapcb2-19_5x250	1250	109971^*
mknapcb2-20_5x250	1250	107058^*
mknapcb2-21_5x250	1250	149665^*
mknapcb2-22_5x250	1250	155944^*
mknapcb2-23_5x250	1250	149334^*
mknapcb2-24_5x250	1250	152130^*
mknapcb2-25_5x250	1250	150353^*
mknapcb2-26_5x250	1250	150045^*
mknapcb2-27_5x250	1250	148607^*
mknapcb2-28_5x250	1250	149782^*
mknapcb2-29_5x250	1250	155075^*
mknapcb2-30_5x250	1250	154668^*
mknapcb3-01_5x500	2500	120148^*
mknapcb3-02_5x500	2500	117879^*
mknapcb3-03_5x500	2500	121131^*
mknapcb3-04_5x500	2500	120804^*
mknapcb3-05_5x500	2500	122319^*
mknapcb3-06_5x500	2500	122024^*
mknapcb3-07_5x500	2500	119127^*
mknapcb3-08_5x500	2500	120568^*
mknapcb3-09_5x500	2500	121586^*
mknapcb3-10_5x500	2500	120717^*
mknapcb3-11_5x500	2500	218428^*
mknapcb3-12_5x500	2500	221202^*
mknapcb3-13_5x500	2500	217542^*
mknapcb3-14_5x500	2500	223560^*
mknapcb3-15_5x500	2500	218966^*
mknapcb3-16_5x500	2500	220530^*
mknapcb3-17_5x500	2500	219989^*
mknapcb3-18_5x500	2500	218215^*
mknapcb3-19_5x500	2500	216976^*
mknapcb3-20_5x500	2500	219719^*
mknapcb3-21_5x500	2500	295828^*
mknapcb3-22_5x500	2500	308086^*
mknapcb3-23_5x500	2500	299796^*
mknapcb3-24_5x500	2500	306480^*
mknapcb3-25_5x500	2500	300342^*
mknapcb3-26_5x500	2500	302571^*
mknapcb3-27_5x500	2500	301339^*
mknapcb3-28_5x500	2500	306454^*
mknapcb3-29_5x500	2500	302828^*
mknapcb3-30_5x500	2500	299906^*
mknapcb4-01_10x100	1000	23064^*
mknapcb4-02_10x100	1000	22801^*
mknapcb4-03_10x100	1000	22131^*
mknapcb4-04_10x100	1000	22772^*
mknapcb4-05_10x100	1000	22751^*
mknapcb4-06_10x100	1000	22777^*
mknapcb4-07_10x100	1000	21875^*
mknapcb4-08_10x100	1000	22635^*
mknapcb4-09_10x100	1000	22511^*
mknapcb4-10_10x100	1000	22702^*
mknapcb4-11_10x100	1000	41395^*
mknapcb4-12_10x100	1000	42344^*
mknapcb4-13_10x100	1000	42401^*
mknapcb4-14_10x100	1000	45624^*
mknapcb4-15_10x100	1000	41884^*
mknapcb4-16_10x100	1000	42995^*
mknapcb4-17_10x100	1000	43574^*
mknapcb4-18_10x100	1000	42970^*
mknapcb4-19_10x100	1000	42212^*
mknapcb4-20_10x100	1000	41207^*
mknapcb4-21_10x100	1000	57375^*
mknapcb4-22_10x100	1000	58978^*
mknapcb4-23_10x100	1000	58391^*
mknapcb4-24_10x100	1000	61966^*
mknapcb4-25_10x100	1000	60803^*
mknapcb4-26_10x100	1000	61437^*
mknapcb4-27_10x100	1000	56377^*
mknapcb4-28_10x100	1000	59391^*
mknapcb4-29_10x100	1000	60205^*
mknapcb4-30_10x100	1000	60633^*
mknapcb5-01_10x250	2500	59187.0, 59258
mknapcb5-02_10x250	2500	58781^*
mknapcb5-03_10x250	2500	58097^*
mknapcb5-04_10x250	2500	61000.0, 61074
mknapcb5-05_10x250	2500	58092.0, 58179
mknapcb5-06_10x250	2500	58824^*
mknapcb5-07_10x250	2500	58704^*
mknapcb5-08_10x250	2500	58936.0, 59042
mknapcb5-09_10x250	2500	59387^*
mknapcb5-10_10x250	2500	59208.0, 59283
mknapcb5-11_10x250	2500	110913^*
mknapcb5-12_10x250	2500	108717^*
mknapcb5-13_10x250	2500	108932^*
mknapcb5-14_10x250	2500	110086.0, 110149
mknapcb5-15_10x250	2500	108485^*
mknapcb5-16_10x250	2500	110845.0, 110901
mknapcb5-17_10x250	2500	106077.0, 106127
mknapcb5-18_10x250	2500	106686^*
mknapcb5-19_10x250	2500	109829^*
mknapcb5-20_10x250	2500	106723^*
mknapcb5-21_10x250	2500	151809^*
mknapcb5-22_10x250	2500	148772^*
mknapcb5-23_10x250	2500	151909^*
mknapcb5-24_10x250	2500	151324^*
mknapcb5-25_10x250	2500	151966^*
mknapcb5-26_10x250	2500	152109^*
mknapcb5-27_10x250	2500	153131^*
mknapcb5-28_10x250	2500	153578^*
mknapcb5-29_10x250	2500	149160^*
mknapcb5-30_10x250	2500	149704^*
mknapcb6-01_10x500	5000	117809.0, 117940
mknapcb6-02_10x500	5000	119217.0, 119355
mknapcb6-03_10x500	5000	119215.0, 119328
mknapcb6-04_10x500	5000	118825.0, 118943
mknapcb6-05_10x500	5000	116524.0, 116641
mknapcb6-06_10x500	5000	119481.0, 119611
mknapcb6-07_10x500	5000	119827.0, 119925
mknapcb6-08_10x500	5000	118323.0, 118444
mknapcb6-09_10x500	5000	117815.0, 117909
mknapcb6-10_10x500	5000	119237.0, 119360
mknapcb6-11_10x500	5000	217377.0, 217472
mknapcb6-12_10x500	5000	219077.0, 219178
mknapcb6-13_10x500	5000	217847.0, 217903
mknapcb6-14_10x500	5000	216868.0, 216965
mknapcb6-15_10x500	5000	213859.0, 213964
mknapcb6-16_10x500	5000	215086.0, 215178
mknapcb6-17_10x500	5000	217931.0, 218019
mknapcb6-18_10x500	5000	219984.0, 220094
mknapcb6-19_10x500	5000	214375.0, 214470
mknapcb6-20_10x500	5000	220886.0, 221000
mknapcb6-21_10x500	5000	304387.0, 304448
mknapcb6-22_10x500	5000	302379.0, 302454
mknapcb6-23_10x500	5000	302416.0, 302501
mknapcb6-24_10x500	5000	300784.0, 300844
mknapcb6-25_10x500	5000	304374.0, 304470
mknapcb6-26_10x500	5000	301836.0, 301874
mknapcb6-27_10x500	5000	304952.0, 305046
mknapcb6-28_10x500	5000	296466.0, 296546
mknapcb6-29_10x500	5000	301357.0, 301446
mknapcb6-30_10x500	5000	307089.0, 307141
mknapcb7-01_30x100	3000	21946^*
mknapcb7-02_30x100	3000	21716^*
mknapcb7-03_30x100	3000	20754^*
mknapcb7-04_30x100	3000	21464^*
mknapcb7-05_30x100	3000	21844^*
mknapcb7-06_30x100	3000	22176^*
mknapcb7-07_30x100	3000	21799^*
mknapcb7-08_30x100	3000	21397^*
mknapcb7-09_30x100	3000	22525^*
mknapcb7-10_30x100	3000	20983^*
mknapcb7-11_30x100	3000	40767^*
mknapcb7-12_30x100	3000	41308^*
mknapcb7-13_30x100	3000	41630^*
mknapcb7-14_30x100	3000	41041^*
mknapcb7-15_30x100	3000	40889^*
mknapcb7-16_30x100	3000	41058^*
mknapcb7-17_30x100	3000	41062^*
mknapcb7-18_30x100	3000	42719^*
mknapcb7-19_30x100	3000	42230^*
mknapcb7-20_30x100	3000	41700^*
mknapcb7-21_30x100	3000	57494^*
mknapcb7-22_30x100	3000	60027^*
mknapcb7-23_30x100	3000	58052^*
mknapcb7-24_30x100	3000	60776^*
mknapcb7-25_30x100	3000	58884^*
mknapcb7-26_30x100	3000	60011^*
mknapcb7-27_30x100	3000	58132^*
mknapcb7-28_30x100	3000	59064^*
mknapcb7-29_30x100	3000	58975^*
mknapcb7-30_30x100	3000	60603^*
mknapcb8-01_30x250	7500	56824.0, 57105
mknapcb8-02_30x250	7500	58520.0, 58786
mknapcb8-03_30x250	7500	56572.0, 56890
mknapcb8-04_30x250	7500	56930.0, 57238
mknapcb8-05_30x250	7500	56629.0, 56961
mknapcb8-06_30x250	7500	57205.0, 57537
mknapcb8-07_30x250	7500	56357.0, 56713
mknapcb8-08_30x250	7500	56457.0, 56763
mknapcb8-09_30x250	7500	57474.0, 57831
mknapcb8-10_30x250	7500	56447.0, 56734
mknapcb8-11_30x250	7500	107755.0, 108006
mknapcb8-12_30x250	7500	108379.0, 108649
mknapcb8-13_30x250	7500	106442.0, 106666
mknapcb8-14_30x250	7500	106851.0, 107176
mknapcb8-15_30x250	7500	107414.0, 107700
mknapcb8-16_30x250	7500	107246.0, 107518
mknapcb8-17_30x250	7500	106372.0, 106612
mknapcb8-18_30x250	7500	104013.0, 104298
mknapcb8-19_30x250	7500	106856.0, 107112
mknapcb8-20_30x250	7500	105780.0, 106082
mknapcb8-21_30x250	7500	150138.0, 150318
mknapcb8-22_30x250	7500	149958.0, 150098
mknapcb8-23_30x250	7500	153007.0, 153158
mknapcb8-24_30x250	7500	153234.0, 153388
mknapcb8-25_30x250	7500	150287.0, 150420
mknapcb8-26_30x250	7500	148574.0, 148749
mknapcb8-27_30x250	7500	147477.0, 147632
mknapcb8-28_30x250	7500	152912.0, 153082
mknapcb8-29_30x250	7500	149570.0, 149764
mknapcb8-30_30x250	7500	149668.0, 149826
mknapcb9-01_30x500	15000	115977.0, 116474
mknapcb9-02_30x500	15000	114732.0, 115210
mknapcb9-03_30x500	15000	116682.0, 117208
mknapcb9-04_30x500	15000	115252.0, 115813
mknapcb9-05_30x500	15000	116440.0, 116989
mknapcb9-06_30x500	15000	115710.0, 116222
mknapcb9-07_30x500	15000	114076.0, 114581
mknapcb9-08_30x500	15000	114264.0, 114748
mknapcb9-09_30x500	15000	115419.0, 115773
mknapcb9-10_30x500	15000	117116.0, 117540
mknapcb9-11_30x500	15000	218068.0, 218465
mknapcb9-12_30x500	15000	214621.0, 214963
mknapcb9-13_30x500	15000	215933.0, 216290
mknapcb9-14_30x500	15000	217892.0, 218215
mknapcb9-15_30x500	15000	215640.0, 215983
mknapcb9-16_30x500	15000	215867.0, 216248
mknapcb9-17_30x500	15000	215907.0, 216208
mknapcb9-18_30x500	15000	216444.0, 216879
mknapcb9-19_30x500	15000	217340.0, 217694
mknapcb9-20_30x500	15000	214681.0, 215088
mknapcb9-21_30x500	15000	301675.0, 301932
mknapcb9-22_30x500	15000	300045.0, 300336
mknapcb9-23_30x500	15000	305055.0, 305354
mknapcb9-24_30x500	15000	301987.0, 302342
mknapcb9-25_30x500	15000	304425.0, 304760
mknapcb9-26_30x500	15000	296959.0, 297296
mknapcb9-27_30x500	15000	303342.0, 303646
mknapcb9-28_30x500	15000	306990.0, 307283
mknapcb9-29_30x500	15000	303162.0, 303477
mknapcb9-30_30x500	15000	300535.0, 300884