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 |
| Label | Description |
| mkp | standard formulation for the multi-constraint knapsack problem |
| Instance | Size | mkp |
| mk_gk01_15x100 | 1500 | 1.59 |
| mk_gk02_25x100 | 2500 | 79.04 |
| mk_gk03_25x150 | 3750 | >3600 |
| mk_gk04_50x150 | 7500 | >3600 |
| mk_gk05_25x200 | 5000 | >3600 |
| mk_gk06_50x200 | 10000 | >3600 |
| mk_gk07_25x500 | 12500 | >3600 |
| mk_gk08_50x500 | 25000 | >3600 |
| mk_gk09_25x1500 | 37500 | >3600 |
| mk_gk10_50x1500 | 75000 | >3600 |
| mk_gk11_100x2500 | 250000 | >3600 |
| mknapcb1-01_5x100 | 500 | 0.92 |
| mknapcb1-02_5x100 | 500 | 0.68 |
| mknapcb1-03_5x100 | 500 | 1.62 |
| mknapcb1-04_5x100 | 500 | 2.61 |
| mknapcb1-05_5x100 | 500 | 1.57 |
| mknapcb1-06_5x100 | 500 | 0.67 |
| mknapcb1-07_5x100 | 500 | 0.26 |
| mknapcb1-08_5x100 | 500 | 0.66 |
| mknapcb1-09_5x100 | 500 | 0.86 |
| mknapcb1-10_5x100 | 500 | 0.84 |
| mknapcb1-11_5x100 | 500 | 0.30 |
| mknapcb1-12_5x100 | 500 | 0.43 |
| mknapcb1-13_5x100 | 500 | 6.12 |
| mknapcb1-14_5x100 | 500 | 1.35 |
| mknapcb1-15_5x100 | 500 | 0.74 |
| mknapcb1-16_5x100 | 500 | 0.24 |
| mknapcb1-17_5x100 | 500 | 0.22 |
| mknapcb1-18_5x100 | 500 | 2.20 |
| mknapcb1-19_5x100 | 500 | 0.22 |
| mknapcb1-20_5x100 | 500 | 0.72 |
| mknapcb1-21_5x100 | 500 | 0.22 |
| mknapcb1-22_5x100 | 500 | 0.30 |
| mknapcb1-23_5x100 | 500 | 0.76 |
| mknapcb1-24_5x100 | 500 | 0.84 |
| mknapcb1-25_5x100 | 500 | 0.36 |
| mknapcb1-26_5x100 | 500 | 0.51 |
| mknapcb1-27_5x100 | 500 | 0.30 |
| mknapcb1-28_5x100 | 500 | 0.34 |
| mknapcb1-29_5x100 | 500 | 0.20 |
| mknapcb1-30_5x100 | 500 | 1.04 |
| mknapcb2-01_5x250 | 1250 | 12.63 |
| mknapcb2-02_5x250 | 1250 | 21.45 |
| mknapcb2-03_5x250 | 1250 | 1.72 |
| mknapcb2-04_5x250 | 1250 | 96.10 |
| mknapcb2-05_5x250 | 1250 | 34.36 |
| mknapcb2-06_5x250 | 1250 | 61.84 |
| mknapcb2-07_5x250 | 1250 | 16.02 |
| mknapcb2-08_5x250 | 1250 | 25.30 |
| mknapcb2-09_5x250 | 1250 | 12.14 |
| mknapcb2-10_5x250 | 1250 | 4.00 |
| mknapcb2-11_5x250 | 1250 | 36.80 |
| mknapcb2-12_5x250 | 1250 | 2.82 |
| mknapcb2-13_5x250 | 1250 | 32.34 |
| mknapcb2-14_5x250 | 1250 | 26.73 |
| mknapcb2-15_5x250 | 1250 | 60.14 |
| mknapcb2-16_5x250 | 1250 | 34.90 |
| mknapcb2-17_5x250 | 1250 | 23.06 |
| mknapcb2-18_5x250 | 1250 | 36.93 |
| mknapcb2-19_5x250 | 1250 | 19.40 |
| mknapcb2-20_5x250 | 1250 | 17.07 |
| mknapcb2-21_5x250 | 1250 | 17.31 |
| mknapcb2-22_5x250 | 1250 | 10.27 |
| mknapcb2-23_5x250 | 1250 | 17.32 |
| mknapcb2-24_5x250 | 1250 | 12.83 |
| mknapcb2-25_5x250 | 1250 | 14.70 |
| mknapcb2-26_5x250 | 1250 | 2.91 |
| mknapcb2-27_5x250 | 1250 | 0.84 |
| mknapcb2-28_5x250 | 1250 | 17.47 |
| mknapcb2-29_5x250 | 1250 | 4.53 |
| mknapcb2-30_5x250 | 1250 | 17.94 |
| mknapcb3-01_5x500 | 2500 | 667.67 |
| mknapcb3-02_5x500 | 2500 | 125.81 |
| mknapcb3-03_5x500 | 2500 | 429.20 |
| mknapcb3-04_5x500 | 2500 | 331.27 |
| mknapcb3-05_5x500 | 2500 | 170.30 |
| mknapcb3-06_5x500 | 2500 | 279.07 |
| mknapcb3-07_5x500 | 2500 | 696.86 |
| mknapcb3-08_5x500 | 2500 | 175.32 |
| mknapcb3-09_5x500 | 2500 | 428.57 |
| mknapcb3-10_5x500 | 2500 | 500.30 |
| mknapcb3-11_5x500 | 2500 | 172.85 |
| mknapcb3-12_5x500 | 2500 | 84.32 |
| mknapcb3-13_5x500 | 2500 | 398.20 |
| mknapcb3-14_5x500 | 2500 | 367.35 |
| mknapcb3-15_5x500 | 2500 | 33.20 |
| mknapcb3-16_5x500 | 2500 | 196.48 |
| mknapcb3-17_5x500 | 2500 | 96.15 |
| mknapcb3-18_5x500 | 2500 | 97.03 |
| mknapcb3-19_5x500 | 2500 | 202.24 |
| mknapcb3-20_5x500 | 2500 | 250.68 |
| mknapcb3-21_5x500 | 2500 | 8.14 |
| mknapcb3-22_5x500 | 2500 | 53.56 |
| mknapcb3-23_5x500 | 2500 | 32.85 |
| mknapcb3-24_5x500 | 2500 | 98.48 |
| mknapcb3-25_5x500 | 2500 | 37.22 |
| mknapcb3-26_5x500 | 2500 | 89.57 |
| mknapcb3-27_5x500 | 2500 | 29.78 |
| mknapcb3-28_5x500 | 2500 | 17.18 |
| mknapcb3-29_5x500 | 2500 | 39.58 |
| mknapcb3-30_5x500 | 2500 | 98.08 |
| mknapcb4-01_10x100 | 1000 | 24.16 |
| mknapcb4-02_10x100 | 1000 | 17.44 |
| mknapcb4-03_10x100 | 1000 | 6.58 |
| mknapcb4-04_10x100 | 1000 | 23.83 |
| mknapcb4-05_10x100 | 1000 | 2.53 |
| mknapcb4-06_10x100 | 1000 | 22.43 |
| mknapcb4-07_10x100 | 1000 | 3.21 |
| mknapcb4-08_10x100 | 1000 | 2.80 |
| mknapcb4-09_10x100 | 1000 | 2.49 |
| mknapcb4-10_10x100 | 1000 | 5.71 |
| mknapcb4-11_10x100 | 1000 | 9.89 |
| mknapcb4-12_10x100 | 1000 | 3.42 |
| mknapcb4-13_10x100 | 1000 | 8.03 |
| mknapcb4-14_10x100 | 1000 | 12.93 |
| mknapcb4-15_10x100 | 1000 | 2.61 |
| mknapcb4-16_10x100 | 1000 | 11.22 |
| mknapcb4-17_10x100 | 1000 | 11.54 |
| mknapcb4-18_10x100 | 1000 | 6.22 |
| mknapcb4-19_10x100 | 1000 | 6.25 |
| mknapcb4-20_10x100 | 1000 | 11.18 |
| mknapcb4-21_10x100 | 1000 | 0.78 |
| mknapcb4-22_10x100 | 1000 | 4.81 |
| mknapcb4-23_10x100 | 1000 | 4.21 |
| mknapcb4-24_10x100 | 1000 | 0.80 |
| mknapcb4-25_10x100 | 1000 | 1.33 |
| mknapcb4-26_10x100 | 1000 | 4.76 |
| mknapcb4-27_10x100 | 1000 | 6.37 |
| mknapcb4-28_10x100 | 1000 | 0.88 |
| mknapcb4-29_10x100 | 1000 | 1.87 |
| mknapcb4-30_10x100 | 1000 | 1.77 |
| mknapcb5-01_10x250 | 2500 | >3600 |
| mknapcb5-02_10x250 | 2500 | 698.54 |
| mknapcb5-03_10x250 | 2500 | 1195.02 |
| mknapcb5-04_10x250 | 2500 | >3600 |
| mknapcb5-05_10x250 | 2500 | >3600 |
| mknapcb5-06_10x250 | 2500 | 1289.30 |
| mknapcb5-07_10x250 | 2500 | 776.16 |
| mknapcb5-08_10x250 | 2500 | >3600 |
| mknapcb5-09_10x250 | 2500 | 2416.18 |
| mknapcb5-10_10x250 | 2500 | >3600 |
| mknapcb5-11_10x250 | 2500 | 3232.45 |
| mknapcb5-12_10x250 | 2500 | 3559.21 |
| mknapcb5-13_10x250 | 2500 | 3409.41 |
| mknapcb5-14_10x250 | 2500 | >3600 |
| mknapcb5-15_10x250 | 2500 | 1457.26 |
| mknapcb5-16_10x250 | 2500 | >3600 |
| mknapcb5-17_10x250 | 2500 | >3600 |
| mknapcb5-18_10x250 | 2500 | 2902.59 |
| mknapcb5-19_10x250 | 2500 | 3171.01 |
| mknapcb5-20_10x250 | 2500 | 875.43 |
| mknapcb5-21_10x250 | 2500 | 709.44 |
| mknapcb5-22_10x250 | 2500 | 2176.49 |
| mknapcb5-23_10x250 | 2500 | 540.26 |
| mknapcb5-24_10x250 | 2500 | 382.86 |
| mknapcb5-25_10x250 | 2500 | 835.73 |
| mknapcb5-26_10x250 | 2500 | 426.03 |
| mknapcb5-27_10x250 | 2500 | 68.65 |
| mknapcb5-28_10x250 | 2500 | 3287.95 |
| mknapcb5-29_10x250 | 2500 | 269.58 |
| mknapcb5-30_10x250 | 2500 | 451.97 |
| mknapcb6-01_10x500 | 5000 | >3600 |
| mknapcb6-02_10x500 | 5000 | >3600 |
| mknapcb6-03_10x500 | 5000 | >3600 |
| mknapcb6-04_10x500 | 5000 | >3600 |
| mknapcb6-05_10x500 | 5000 | >3600 |
| mknapcb6-06_10x500 | 5000 | >3600 |
| mknapcb6-07_10x500 | 5000 | >3600 |
| mknapcb6-08_10x500 | 5000 | >3600 |
| mknapcb6-09_10x500 | 5000 | >3600 |
| mknapcb6-10_10x500 | 5000 | >3600 |
| mknapcb6-11_10x500 | 5000 | >3600 |
| mknapcb6-12_10x500 | 5000 | >3600 |
| mknapcb6-13_10x500 | 5000 | >3600 |
| mknapcb6-14_10x500 | 5000 | >3600 |
| mknapcb6-15_10x500 | 5000 | >3600 |
| mknapcb6-16_10x500 | 5000 | >3600 |
| mknapcb6-17_10x500 | 5000 | >3600 |
| mknapcb6-18_10x500 | 5000 | >3600 |
| mknapcb6-19_10x500 | 5000 | >3600 |
| mknapcb6-20_10x500 | 5000 | >3600 |
| mknapcb6-21_10x500 | 5000 | >3600 |
| mknapcb6-22_10x500 | 5000 | >3600 |
| mknapcb6-23_10x500 | 5000 | >3600 |
| mknapcb6-24_10x500 | 5000 | >3600 |
| mknapcb6-25_10x500 | 5000 | >3600 |
| mknapcb6-26_10x500 | 5000 | >3600 |
| mknapcb6-27_10x500 | 5000 | >3600 |
| mknapcb6-28_10x500 | 5000 | >3600 |
| mknapcb6-29_10x500 | 5000 | >3600 |
| mknapcb6-30_10x500 | 5000 | >3600 |
| mknapcb7-01_30x100 | 3000 | 36.10 |
| mknapcb7-02_30x100 | 3000 | 163.56 |
| mknapcb7-03_30x100 | 3000 | 78.36 |
| mknapcb7-04_30x100 | 3000 | 139.66 |
| mknapcb7-05_30x100 | 3000 | 417.20 |
| mknapcb7-06_30x100 | 3000 | 422.64 |
| mknapcb7-07_30x100 | 3000 | 366.67 |
| mknapcb7-08_30x100 | 3000 | 380.47 |
| mknapcb7-09_30x100 | 3000 | 1168.96 |
| mknapcb7-10_30x100 | 3000 | 53.72 |
| mknapcb7-11_30x100 | 3000 | 299.00 |
| mknapcb7-12_30x100 | 3000 | 509.06 |
| mknapcb7-13_30x100 | 3000 | 742.52 |
| mknapcb7-14_30x100 | 3000 | 105.19 |
| mknapcb7-15_30x100 | 3000 | 298.15 |
| mknapcb7-16_30x100 | 3000 | 178.08 |
| mknapcb7-17_30x100 | 3000 | 242.14 |
| mknapcb7-18_30x100 | 3000 | 160.12 |
| mknapcb7-19_30x100 | 3000 | 9.24 |
| mknapcb7-20_30x100 | 3000 | 105.95 |
| mknapcb7-21_30x100 | 3000 | 21.77 |
| mknapcb7-22_30x100 | 3000 | 57.15 |
| mknapcb7-23_30x100 | 3000 | 99.11 |
| mknapcb7-24_30x100 | 3000 | 10.78 |
| mknapcb7-25_30x100 | 3000 | 11.12 |
| mknapcb7-26_30x100 | 3000 | 20.56 |
| mknapcb7-27_30x100 | 3000 | 36.39 |
| mknapcb7-28_30x100 | 3000 | 22.15 |
| mknapcb7-29_30x100 | 3000 | 71.80 |
| mknapcb7-30_30x100 | 3000 | 87.67 |
| mknapcb8-01_30x250 | 7500 | >3600 |
| mknapcb8-02_30x250 | 7500 | >3600 |
| mknapcb8-03_30x250 | 7500 | >3600 |
| mknapcb8-04_30x250 | 7500 | >3600 |
| mknapcb8-05_30x250 | 7500 | >3600 |
| mknapcb8-06_30x250 | 7500 | >3600 |
| mknapcb8-07_30x250 | 7500 | >3600 |
| mknapcb8-08_30x250 | 7500 | >3600 |
| mknapcb8-09_30x250 | 7500 | >3600 |
| mknapcb8-10_30x250 | 7500 | >3600 |
| mknapcb8-11_30x250 | 7500 | >3600 |
| mknapcb8-12_30x250 | 7500 | >3600 |
| mknapcb8-13_30x250 | 7500 | >3600 |
| mknapcb8-14_30x250 | 7500 | >3600 |
| mknapcb8-15_30x250 | 7500 | >3600 |
| mknapcb8-16_30x250 | 7500 | >3600 |
| mknapcb8-17_30x250 | 7500 | >3600 |
| mknapcb8-18_30x250 | 7500 | >3600 |
| mknapcb8-19_30x250 | 7500 | >3600 |
| mknapcb8-20_30x250 | 7500 | >3600 |
| mknapcb8-21_30x250 | 7500 | >3600 |
| mknapcb8-22_30x250 | 7500 | >3600 |
| mknapcb8-23_30x250 | 7500 | >3600 |
| mknapcb8-24_30x250 | 7500 | >3600 |
| mknapcb8-25_30x250 | 7500 | >3600 |
| mknapcb8-26_30x250 | 7500 | >3600 |
| mknapcb8-27_30x250 | 7500 | >3600 |
| mknapcb8-28_30x250 | 7500 | >3600 |
| mknapcb8-29_30x250 | 7500 | >3600 |
| mknapcb8-30_30x250 | 7500 | >3600 |
| mknapcb9-01_30x500 | 15000 | >3600 |
| mknapcb9-02_30x500 | 15000 | >3600 |
| mknapcb9-03_30x500 | 15000 | >3600 |
| mknapcb9-04_30x500 | 15000 | >3600 |
| mknapcb9-05_30x500 | 15000 | >3600 |
| mknapcb9-06_30x500 | 15000 | >3600 |
| mknapcb9-07_30x500 | 15000 | >3600 |
| mknapcb9-08_30x500 | 15000 | >3600 |
| mknapcb9-09_30x500 | 15000 | >3600 |
| mknapcb9-10_30x500 | 15000 | >3600 |
| mknapcb9-11_30x500 | 15000 | >3600 |
| mknapcb9-12_30x500 | 15000 | >3600 |
| mknapcb9-13_30x500 | 15000 | >3600 |
| mknapcb9-14_30x500 | 15000 | >3600 |
| mknapcb9-15_30x500 | 15000 | >3600 |
| mknapcb9-16_30x500 | 15000 | >3600 |
| mknapcb9-17_30x500 | 15000 | >3600 |
| mknapcb9-18_30x500 | 15000 | >3600 |
| mknapcb9-19_30x500 | 15000 | >3600 |
| mknapcb9-20_30x500 | 15000 | >3600 |
| mknapcb9-21_30x500 | 15000 | >3600 |
| mknapcb9-22_30x500 | 15000 | >3600 |
| mknapcb9-23_30x500 | 15000 | >3600 |
| mknapcb9-24_30x500 | 15000 | >3600 |
| mknapcb9-25_30x500 | 15000 | >3600 |
| mknapcb9-26_30x500 | 15000 | >3600 |
| mknapcb9-27_30x500 | 15000 | >3600 |
| mknapcb9-28_30x500 | 15000 | >3600 |
| mknapcb9-29_30x500 | 15000 | >3600 |
| mknapcb9-30_30x500 | 15000 | >3600 |