(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 | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 13 | 0.26 | 72.78 % | 18558.00 | 18558 | 18910.56 | 1.90 % | 9.24 | 352 | 429.24 | 1 | 1 | 62.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 26 | 0.85 | 11.94 % | 56525.00 | 56525 | 56574.63 | 0.09 % | 7.57 | 0 | 14.05 | 1 | 0 | 97.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 39 | 0.06 | 86.90 % | 3752.00 | 3752 | 3807.68 | 1.48 % | 9.13 | 0 | 60.18 | 1 | 0 |100.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 52 | 0.76 | 19.78 % | 50382.00 | 50382 | 50448.08 | 0.13 % | 9.29 | 0 | 37.31 | 1 | 0 | 95.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 65 | 0.93 | 4.83 % | 61494.00 | 61494 | 61623.22 | 0.21 % | 8.40 | 0 | 15.92 | 1 | 0 | 95.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 78 | 0.54 | 37.16 % | 36360.00 | 36360 | 36464.87 | 0.29 % | 8.94 | 0 | 38.93 | 1 | 0 | 96.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 91 | 0.19 | 66.93 % | 14657.00 | 14657 | 14749.58 | 0.63 % | 10.18 | 0 | 81.85 | 1 | 0 | 93.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 104 | 0.26 | 69.94 % | 20452.00 | 20452 | 20525.15 | 0.36 % | 8.17 | 0 | 124.41 | 1 | 0 | 92.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 117 | 0.57 | 35.27 % | 35438.00 | 35438 | 35485.16 | 0.13 % | 15.19 | 0 | 51.27 | 1 | 0 | 96.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 100 | 25.00 % | 130 | 0.40 | 53.30 % | 24930.00 | 24930 | 25191.50 | 1.05 % | 10.43 | 56 | 228.62 | 1 | 1 | 79.00 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | Moyenne | 0.48 | 45.88 % | 32254.80 | 32255 | 32378.04 | 0.63 % | 9.65 | 41 | 108.18 | 1 | 0 | 90.50 % | 0.00 % | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | Ecart type | 0.28 | 26.81 % | 18171.98 | 18172 | 18149.87 | 0.61 % | 2.02 | 105 | 122.99 | 0 | 0 | 10.89 % | 0.00 % | --------------------------------------------------------------------------------------------------------------------------------------------------------------------