Friday, February 19, 2010

Performance of similar MIP models

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