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:

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

Solutions failed

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

chart
Number of failed solution attempts
InstanceSizemkp
mknapcb1-01_5x100,mknapcb1-02_5x100,mknapcb1-03_5x100,mknapcb1-04_5x100,mknapcb1-05_5x100,mknapcb1-06_5x100,mknapcb1-07_5x100,mknapcb1-08_5x100,mknapcb1-09_5x100,mknapcb1-10_5x100,mknapcb1-11_5x100,mknapcb1-12_5x100,mknapcb1-13_5x100,mknapcb1-14_5x100,mknapcb1-15_5x100,mknapcb1-16_5x100,mknapcb1-17_5x100,mknapcb1-18_5x100,mknapcb1-19_5x100,mknapcb1-20_5x100,mknapcb1-21_5x100,mknapcb1-22_5x100,mknapcb1-23_5x100,mknapcb1-24_5x100,mknapcb1-25_5x100,mknapcb1-26_5x100,mknapcb1-27_5x100,mknapcb1-28_5x100,mknapcb1-29_5x100,mknapcb1-30_5x100 500 0
mknapcb4-01_10x100,mknapcb4-02_10x100,mknapcb4-03_10x100,mknapcb4-04_10x100,mknapcb4-05_10x100,mknapcb4-06_10x100,mknapcb4-07_10x100,mknapcb4-08_10x100,mknapcb4-09_10x100,mknapcb4-10_10x100,mknapcb4-11_10x100,mknapcb4-12_10x100,mknapcb4-13_10x100,mknapcb4-14_10x100,mknapcb4-15_10x100,mknapcb4-16_10x100,mknapcb4-17_10x100,mknapcb4-18_10x100,mknapcb4-19_10x100,mknapcb4-20_10x100,mknapcb4-21_10x100,mknapcb4-22_10x100,mknapcb4-23_10x100,mknapcb4-24_10x100,mknapcb4-25_10x100,mknapcb4-26_10x100,mknapcb4-27_10x100,mknapcb4-28_10x100,mknapcb4-29_10x100,mknapcb4-30_10x100 1000 0
mknapcb2-01_5x250,mknapcb2-02_5x250,mknapcb2-03_5x250,mknapcb2-04_5x250,mknapcb2-05_5x250,mknapcb2-06_5x250,mknapcb2-07_5x250,mknapcb2-08_5x250,mknapcb2-09_5x250,mknapcb2-10_5x250,mknapcb2-11_5x250,mknapcb2-12_5x250,mknapcb2-13_5x250,mknapcb2-14_5x250,mknapcb2-15_5x250,mknapcb2-16_5x250,mknapcb2-17_5x250,mknapcb2-18_5x250,mknapcb2-19_5x250,mknapcb2-20_5x250,mknapcb2-21_5x250,mknapcb2-22_5x250,mknapcb2-23_5x250,mknapcb2-24_5x250,mknapcb2-25_5x250,mknapcb2-26_5x250,mknapcb2-27_5x250,mknapcb2-28_5x250,mknapcb2-29_5x250,mknapcb2-30_5x250 1250 0
mk_gk01_15x100 1500 0
mk_gk02_25x100,mknapcb3-01_5x500,mknapcb3-02_5x500,mknapcb3-03_5x500,mknapcb3-04_5x500,mknapcb3-05_5x500,mknapcb3-06_5x500,mknapcb3-07_5x500,mknapcb3-08_5x500,mknapcb3-09_5x500,mknapcb3-10_5x500,mknapcb3-11_5x500,mknapcb3-12_5x500,mknapcb3-13_5x500,mknapcb3-14_5x500,mknapcb3-15_5x500,mknapcb3-16_5x500,mknapcb3-17_5x500,mknapcb3-18_5x500,mknapcb3-19_5x500,mknapcb3-20_5x500,mknapcb3-21_5x500,mknapcb3-22_5x500,mknapcb3-23_5x500,mknapcb3-24_5x500,mknapcb3-25_5x500,mknapcb3-26_5x500,mknapcb3-27_5x500,mknapcb3-28_5x500,mknapcb3-29_5x500,mknapcb3-30_5x500,mknapcb5-01_10x250,mknapcb5-02_10x250,mknapcb5-03_10x250,mknapcb5-04_10x250,mknapcb5-05_10x250,mknapcb5-06_10x250,mknapcb5-07_10x250,mknapcb5-08_10x250,mknapcb5-09_10x250,mknapcb5-10_10x250,mknapcb5-11_10x250,mknapcb5-12_10x250,mknapcb5-13_10x250,mknapcb5-14_10x250,mknapcb5-15_10x250,mknapcb5-16_10x250,mknapcb5-17_10x250,mknapcb5-18_10x250,mknapcb5-19_10x250,mknapcb5-20_10x250,mknapcb5-21_10x250,mknapcb5-22_10x250,mknapcb5-23_10x250,mknapcb5-24_10x250,mknapcb5-25_10x250,mknapcb5-26_10x250,mknapcb5-27_10x250,mknapcb5-28_10x250,mknapcb5-29_10x250,mknapcb5-30_10x250 2500 8
mknapcb7-01_30x100,mknapcb7-02_30x100,mknapcb7-03_30x100,mknapcb7-04_30x100,mknapcb7-05_30x100,mknapcb7-06_30x100,mknapcb7-07_30x100,mknapcb7-08_30x100,mknapcb7-09_30x100,mknapcb7-10_30x100,mknapcb7-11_30x100,mknapcb7-12_30x100,mknapcb7-13_30x100,mknapcb7-14_30x100,mknapcb7-15_30x100,mknapcb7-16_30x100,mknapcb7-17_30x100,mknapcb7-18_30x100,mknapcb7-19_30x100,mknapcb7-20_30x100,mknapcb7-21_30x100,mknapcb7-22_30x100,mknapcb7-23_30x100,mknapcb7-24_30x100,mknapcb7-25_30x100,mknapcb7-26_30x100,mknapcb7-27_30x100,mknapcb7-28_30x100,mknapcb7-29_30x100,mknapcb7-30_30x100 3000 8
mk_gk03_25x150 3750 9
mk_gk05_25x200,mknapcb6-01_10x500,mknapcb6-02_10x500,mknapcb6-03_10x500,mknapcb6-04_10x500,mknapcb6-05_10x500,mknapcb6-06_10x500,mknapcb6-07_10x500,mknapcb6-08_10x500,mknapcb6-09_10x500,mknapcb6-10_10x500,mknapcb6-11_10x500,mknapcb6-12_10x500,mknapcb6-13_10x500,mknapcb6-14_10x500,mknapcb6-15_10x500,mknapcb6-16_10x500,mknapcb6-17_10x500,mknapcb6-18_10x500,mknapcb6-19_10x500,mknapcb6-20_10x500,mknapcb6-21_10x500,mknapcb6-22_10x500,mknapcb6-23_10x500,mknapcb6-24_10x500,mknapcb6-25_10x500,mknapcb6-26_10x500,mknapcb6-27_10x500,mknapcb6-28_10x500,mknapcb6-29_10x500,mknapcb6-30_10x500 5000 40
mk_gk04_50x150,mknapcb8-01_30x250,mknapcb8-02_30x250,mknapcb8-03_30x250,mknapcb8-04_30x250,mknapcb8-05_30x250,mknapcb8-06_30x250,mknapcb8-07_30x250,mknapcb8-08_30x250,mknapcb8-09_30x250,mknapcb8-10_30x250,mknapcb8-11_30x250,mknapcb8-12_30x250,mknapcb8-13_30x250,mknapcb8-14_30x250,mknapcb8-15_30x250,mknapcb8-16_30x250,mknapcb8-17_30x250,mknapcb8-18_30x250,mknapcb8-19_30x250,mknapcb8-20_30x250,mknapcb8-21_30x250,mknapcb8-22_30x250,mknapcb8-23_30x250,mknapcb8-24_30x250,mknapcb8-25_30x250,mknapcb8-26_30x250,mknapcb8-27_30x250,mknapcb8-28_30x250,mknapcb8-29_30x250,mknapcb8-30_30x250 7500 71
mk_gk06_50x200 10000 72
mk_gk07_25x500 12500 73
mknapcb9-01_30x500,mknapcb9-02_30x500,mknapcb9-03_30x500,mknapcb9-04_30x500,mknapcb9-05_30x500,mknapcb9-06_30x500,mknapcb9-07_30x500,mknapcb9-08_30x500,mknapcb9-09_30x500,mknapcb9-10_30x500,mknapcb9-11_30x500,mknapcb9-12_30x500,mknapcb9-13_30x500,mknapcb9-14_30x500,mknapcb9-15_30x500,mknapcb9-16_30x500,mknapcb9-17_30x500,mknapcb9-18_30x500,mknapcb9-19_30x500,mknapcb9-20_30x500,mknapcb9-21_30x500,mknapcb9-22_30x500,mknapcb9-23_30x500,mknapcb9-24_30x500,mknapcb9-25_30x500,mknapcb9-26_30x500,mknapcb9-27_30x500,mknapcb9-28_30x500,mknapcb9-29_30x500,mknapcb9-30_30x500 15000 103
mk_gk08_50x500 25000 104
mk_gk09_25x1500 37500 105
mk_gk10_50x1500 75000 106
mk_gk11_100x2500 250000 107