(QKP) Legend : (0) : number of variables Density : proportion of coefficients non-zero coefficients in the objective function (2) : instance reference (3) : Capacity / Sum ai alpha : difficulty degree ((LB - valmax) / LB) LB : value of the best feasible solution we could find Optimum : optimum value UB : value of the upper bound Gap : relative gap between UB and LB : Gap = (UB-LB)/LB Time UB : CPU time required by the computation of UB # nodes : Number of nodes developped in the Branch-and-Bound Total Time : total CPU time IR : we could solve the instance within the time limit (30,000 s) : yes (1) or no (0) R : using simulated annealing (0 = no; 1 = yes, but in vain; 2 = yes and improvement) fixed : Percentage of fixed variables before the Branch-and-Bound fixaut : Percentage of automatically fixed variables -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | Data | Solution obtained by using Lagrangian Decomposition | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | (0) | Density | (2) | (3) | alpha | LB | Optimum | UB | Gap | Time UB | # nodes | Total time| IR | R | fixed | fixaut | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 1 | 0.93 | 3.39 % | 937149.00 | 937149 | 942489.38 | 0.57 % | 34.59 | 265994 | 556714.87 | 0 | 1 | 41.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 2 | 0.27 | 69.69 % | 303058.00 | 303058 | 304595.88 | 0.51 % | 24.55 | 1652 | 1906.20 | 1 | 1 | 78.50 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 3 | 0.03 | 92.36 % | 29367.00 | 29367 | 29596.51 | 0.78 % | 26.44 | 0 | 342.63 | 1 | 0 | 96.50 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 4 | 0.10 | 83.71 % | 100838.00 | 100838 | 101238.84 | 0.40 % | 18.37 | 0 | 158.13 | 1 | 0 | 94.50 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 5 | 0.78 | 18.40 % | 786635.00 | 786635 | 787487.25 | 0.11 % | 29.01 | 438 | 494.99 | 1 | 0 | 83.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 6 | 0.04 | 90.12 % | 41171.00 | 41171 | 41198.87 | 0.07 % | 27.62 | 0 | 638.06 | 1 | 0 |100.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 7 | 0.69 | 28.06 % | 701094.00 | 701094 | 702021.62 | 0.13 % | 32.86 | 626 | 1013.55 | 1 | 0 | 81.50 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 8 | 0.76 | 20.01 % | 782443.00 | 782443 | 784722.88 | 0.29 % | 34.82 | 126276 | 141160.03 | 0 | 1 | 69.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 9 | 0.63 | 31.03 % | 628951.00 | 628992 | 629587.25 | 0.10 % | 29.76 | 812 | 1245.45 | 1 | 0 | 80.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 200 |100.00 % | 10 | 0.36 | 58.69 % | 378442.00 | 378442 | 379985.19 | 0.41 % | 31.46 | 5166 | 2656.12 | 1 | 1 | 71.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | Average | 0.46 | 49.55 % | 468914.80 | 468919 | 470292.37 | 0.34 % | 28.95 | 40096 | 70633.00 | | | 79.50 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | Std. deviation | 0.32 | 31.49 % | 323318.64 | 323321 | 324294.27 | 0.23 % | 4.77 | 84055 | 167326.46 | | | 16.18 % | 0.00 % | --------------------------------------------------------------------------------------------------------------------------------------------------------------------