*********************************************************** * QUADRATIC KNAPSACK PROBLEM (QKP) * * 20 instances solved by lagrangian decomposition * * 300 variables - Density : 50 % * *********************************************************** Legend : (1) Capacity/Sum ai alpha measures the difficulty level of the instance (2) Percentage of fixed variables (3) Total CPU time (seconds) (4) CPU time for computing the secondes) ------------------------------------------------------------------------------------------------------------------------------------- | References | (1) | alpha | Best primal LB | Optimum | Best dual UB | (2) | Nodes | (3) Time | (UB-LB)/LB| (4) Tim UB| ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_1 | 0.46 | 46.83 % | 513379.0000 | 513379 | 513761.1250 | 91.67 % | 104 | 2007.62 | 0.07 % | 115.77 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_2 | 0.10 | 83.12 % | 105543.0000 | 105543 | 105701.0859 | 98.00 % | 0 | 3857.80 | 0.15 % | 141.83 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_3 | 0.77 | 16.72 % | 875769.0000 | 875788 | 876133.0000 | 94.67 % | 6 | 815.80 | 0.04 % | 66.73 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_4 | 0.27 | 68.21 % | 307124.0000 | 307124 | 307559.6875 | 89.33 % | 172 | 2102.16 | 0.14 % | 126.27 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_5 | 0.64 | 29.45 % | 727820.0000 | 727820 | 728281.5000 | 93.00 % | 56 | 2051.13 | 0.06 % | 131.06 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_6 | 0.66 | 27.85 % | 734053.0000 | 734053 | 734370.2500 | 96.00 % | 0 | 850.82 | 0.04 % | 120.24 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_7 | 0.04 | 92.59 % | 43595.0000 | 43595 | 43825.9531 | 95.33 % | 0 | 1632.62 | 0.53 % | 87.10 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_8 | 0.68 | 27.84 % | 767938.0000 | 767977 | 768520.8125 | 88.67 % | 504 | 3555.53 | 0.08 % | 82.84 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_9 | 0.67 | 30.11 % | 761351.0000 | 761351 | 761759.0625 | 95.33 % | 0 | 7021.10 | 0.05 % | 147.04 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_10 | 0.87 | 10.73 % | 996070.0000 | 996070 | 996285.0625 | 95.67 % | 0 | 5004.69 | 0.02 % | 72.15 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_11 | 0.37 | 56.51 % | 423256.0000 | 423256 | 424258.3438 | 89.33 % | 490 | 6435.63 | 0.24 % | 131.21 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_12 | 0.37 | 56.93 % | 407877.0000 | 407905 | 408690.7188 | 91.33 % | 184 | 7609.05 | 0.20 % | 121.80 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_13 | 0.19 | 75.85 % | 205370.0000 | 205566 | 205925.9219 | 88.33 % | 516 | 4050.44 | 0.27 % | 111.82 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_14 | 0.85 | 10.43 % | 972675.0000 | 972880 | 973586.0625 | 80.00 % | 5876 | 20811.39 | 0.09 % | 125.78 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_15 | 0.85 | 11.50 % | 958289.0000 | 958289 | 959251.2500 | 84.33 % | 4266 | 12375.14 | 0.10 % | 83.51 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_16 | 0.91 | 6.91 % | 1037861.0000 | 1038127 | 1038524.5000 | 87.67 % | 578 | 4505.86 | 0.06 % | 96.86 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_17 | 0.22 | 74.29 % | 253808.0000 | 253808 | 254085.0469 | 96.67 % | 0 | 4956.06 | 0.11 % | 118.29 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_18 | 0.08 | 88.95 % | 98772.0000 | 98772 | 99274.1641 | 96.33 % | 0 | 2264.25 | 0.51 % | 93.47 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_19 | 0.49 | 41.54 % | 559341.0000 | 559374 | 559626.3750 | 94.67 % | 6 | 2881.33 | 0.05 % | 153.27 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_50_20 | 0.77 | 18.16 % | 890901.0000 | 890913 | 891341.6875 | 93.33 % | 44 | 934.52 | 0.05 % | 103.54 | ------------------------------------------------------------------------------------------------------------------------------------- Moyenne | 0.51 | 43.73 % | | 91.98 % | 640 | 4786.15 | 0.14 % | 111.53 | ------------------------------------------------------------------------------------------------------------------------------------- E. type | 0.28 | 28.08 % | | 4.51 % | 1512 | 4591.19 | 0.14 % | 24.21 | -------------------------------------------------------------------------------------------------------------------------------------