This is a table with the running times to solve a MIP model with 3000 binary variables. We stop as soon as the gap is 0.05%. The models only differ by a single parameter λ which changes the objective. This table shows how much difference in performance we can see just by going from λ=0.83 to λ=1. This is a good example where just changing one number in the same model can make an easy model very difficult to solve.
λ | obj | nodes | iterations | time |
0% | 19.15 | 29 | 477 | 5.12 |
4% | 19.03 | 45 | 426 | 2.16 |
8% | 18.91 | 64 | 513 | 3.63 |
13% | 18.82 | 76 | 611 | 3.40 |
17% | 18.76 | 18 | 657 | 2.78 |
21% | 18.75 | 13 | 549 | 2.95 |
25% | 18.76 | 17 | 763 | 4.74 |
29% | 18.80 | 28 | 830 | 4.39 |
33% | 18.92 | 21 | 704 | 4.46 |
38% | 19.04 | 168 | 1298 | 6.70 |
42% | 19.25 | 234 | 1234 | 7.12 |
46% | 19.56 | 642 | 3686 | 17.69 |
50% | 19.94 | 886 | 4601 | 16.12 |
54% | 20.64 | 2292 | 21567 | 29.26 |
58% | 21.42 | 1216 | 13781 | 16.64 |
63% | 22.31 | 3233 | 34883 | 34.76 |
67% | 23.47 | 1873 | 23906 | 29.30 |
71% | 24.75 | 7286 | 54077 | 78.80 |
75% | 26.31 | 5939 | 54634 | 82.18 |
79% | 28.04 | 9486 | 85297 | 112.49 |
83% | 29.78 | 7701 | 62220 | 97.78 |
88% | 31.66 | 26102 | 202141 | 332.58 |
92% | 33.65 | 83790 | 849745 | 987.04 |
96% | 35.84 | 102327 | 911254 | 1377.03 |
100% | 38.26 | 822222 | 6998739 | 11749.83 |
Nice example. I'm curious: If I understand correctly, \lambda only appears in the OF. Have the binary values changed in all the solutions in the table? Were the time differences due to the final portion of the attempt to close the gap, or has the performance changed throughout the entire search?
ReplyDeleteThe difference in performance may be due to a widening of the relaxation gap, in which case small variations in the gap threshold would restore the original solution times.
Very interesting. Is there a big difference in time to first feasible? Do you see the same performance with different solvers?
ReplyDeleteThe trouble is closing the gap from 0.15% to 0.05% by moving the best bound. As usual I helped the solver in finding a good solution quickly using some tricks. Unfortunately this is exactly where solvers like Cplex and Gurobi are doing a good job anyway, so the net effectiveness of these tricks is very limited.
ReplyDelete