*********************************************************** * QUADRATIC KNAPSACK PROBLEM (QKP) * * 20 instances solved by lagrangian decomposition * * 300 variables - Density : 25 % * *********************************************************** 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_25_1 | 5,00%| 93,82% | 29140,0000 | 29140 | 29733,6328 | 96,33% | 0 | 5783,50 | 2,04% | 133,56 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_2 |50,00%| 47,07% | 281948,0000 | 281990 | 283724,531 | 72,67% | 854 | 27535,97 | 0,63% | 185,95 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_3 |40,00%| 54,81% | 231075,0000 | 231075 | 232766,781 | 96,67% | 0 | 19843,92 | 0,73% | 149,51 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_4 |76,00%| 22,22% | 444712,0000 | 444759 | 445027,719 | 93,00% | 52 | 2445,30 | 0,07% | 119,30 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_5 | 3,00%| 92,29% | 14988,0000 | 14988 | 15764,6729 | 97,33% | 0 | 4350,15 | 5,18% | 115,57 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_6 |45,00%| 50,10% | 269782,0000 | 269782 | 269877,938 | 98,33% | 0 | 3876,28 | 0,04% | 165,61 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_7 |84,00%| 15,55% | 484900,0000 | 485263 | 485585,438 | 77,67% | 3892 | 11926,92 | 0,14% | 79,27 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_8 | 1,00%| 94,25% | 9343,0000 | 9343 | 9566,8066 | 97,67% | 0 | 1192,20 | 2,40% | 86,96 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_9 |43,00%| 53,69% | 250761,0000 | 250761 | 251149,625 | 97,67% | 0 | 6406,64 | 0,15% | 167,78 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_10 |66,00%| 29,09% | 383377,0000 | 383377 | 383721,531 | 95,33% | 0 | 2459,30 | 0,09% | 161,93 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_11 |39,00%| 57,31% | 228681,0000 | 228681 | 229620,047 | 100,00% | 0 | 18065,87 | 0,41% | 149,93 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_12 |68,00%| 28,34% | 392829,0000 | 392829 | 392996,781 | 98,00% | 0 | 5277,01 | 0,04% | 122,54 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_13 |69,00%| 25,76% | 395598,0000 | 395598 | 396255,844 | 86,67% | 322 | 4262,97 | 0,17% | 148,38 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_14 |79,00%| 20,82% | 461950,0000 | 462104 | 462322,438 | 85,33% | 624 | 1912,75 | 0,08% | 99,82 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_15 | 4,00%| 92,50% | 24502,0000 | 24516 | 25322,5586 | 93,33% | 36 | 5564,81 | 3,35% | 118,02 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_16 |10,00%| 83,22% | 60063,0000 | 60063 | 60621,1758 | 96,33% | 0 | 6010,71 | 0,93% | 143,80 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_17 |77,00%| 17,55% | 431207,0000 | 431225 | 431749,344 | 90,33% | 196 | 2736,45 | 0,13% | 138,51 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_18 |91,00%| 8,23% | 516936,0000 | 516936 | 517216,25 | 94,67% | 4 | 1495,76 | 0,05% | 159,48 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_19 |35,00%| 62,76% | 203262,0000 | 203262 | 204305,109 | 86,67% | 290 | 22089,40 | 0,51% | 171,75 | ------------------------------------------------------------------------------------------------------------------------------------- | r_300_25_20 |54,00%| 42,87% | 311251,0000 | 311251 | 311450,844 | 94,33% | 8 | 2074,09 | 0,06% | 157,59 | ------------------------------------------------------------------------------------------------------------------------------------- Moyenne |46,95%| 49,61% | | 92,42% |313,90 | 7 765,50 | 0,86% | 138,76 | ------------------------------------------------------------------------------------------------------------------------------------- E.type |28,92%| 28,27% | | 7,06% |852,23 | 7 600,04 | 1,33% | 28,22 | -------------------------------------------------------------------------------------------------------------------------------------