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

3 comments:

  1. 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?

    The 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.

    ReplyDelete
  2. Very interesting. Is there a big difference in time to first feasible? Do you see the same performance with different solvers?

    ReplyDelete
  3. The 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