Unexpected behaviour of Crossover algorithm

Answered

Comments

5 comments

  • Silke Horn

    Hi Henrik,

    If you look at the logs, you can see that the barrier was a bit faster with the bigger tolerance: 424.06 seconds for 1e-7 versus 428.05 seconds for 1e-9. However, the crossover took a lot longer with the bigger tolerance. This is expected! A tighter tolerance in the barrier will make the crossover easier and vice versa. It is always a trade-off between time spent in barrier versus time spent in crossover. For your model, the extra time in barrier really seems to pay off :-).

    Silke

    0
    Comment actions Permalink
  • Henrik Büsing

    Hi Silke,

    Thank you very much for your answer!

    But the barrier tolerance is the same in both cases, namely 0.0. And the barrier logs are (except for the time) absolutely identical. Thus, I would say the starting point for the crossover is the same. Additionally, I thought only the barrier tolerance (which is 0.0 in both cases) does influence the barrier algorithm and not the optimality tolerance (which is different) and only influences the crossover.

    What I do not understand is the following: When I finish with the barrier algorithm, I have exactly the same result. Why is the beginning of the crossover then not the same?

    Thank you!
    Henrik

    0
    Comment actions Permalink
  • Silke Horn

    You're right. I hadn't paid attention to the objectives and iteration numbers before. Maybe the differences are due to chance? Have you tried running the same settings multiple times with different seeds? https://www.gurobi.com/documentation/8.1/refman/seed.html

    0
    Comment actions Permalink
  • Henrik Büsing

    Dear Silke,

    I had not paid attention to the seed value up to now. I have now examined seed values from
    0 to 10 for optimality tolerances of 1e-7 and 1e-9. In 6 of the 11 cases the run-time behaves as
    expected, i.e., the solution times for a tolerance of 1e-7 is less than for 1e-9. In 5 of 11
    cases it's the other way round (see figure).

    What bothers me even more than this behaviour is the huge difference in run-time: I have a factor
    >3 in run-time (for tol=1e-9; or even >6 for tol=1e-7) from the fastest to the slowest seed value.

    Where does this huge sensitivity come from? Is it the tight tolerance I have chosen? And how can I
    avoid that time-to-solution depends that much on a good seed value?

    Thank you!
    Henrik

    0
    Comment actions Permalink
  • Silke Horn

    Hi Henrik,

    When using the barrier algorithm, the random seed affects mostly the ordering (and maybe the cleanup).

    For some models it has a bigger influence on running time than for others. I am not sure why the influence is so big for this model, but I can see that it may have some numerical issue though due to a huge range of matrix coefficients (Matrix range [2e-07, 5e+02]).

    Maybe you can try to improve/reformulate the model so that this range becomes smaller. I would also suggest to scale up the matrix and objective coefficients a bit (since they are currently rather close to -- or even below -- the default feasibility tolerances). Improving the model numerics could also help with the volatility when using different seeds.

    Silke

     

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk