Barrier: Inflated problem iterates and solves much faster

Answered

Comments

2 comments

  • Yuriy Zinchenko

    Hello Leo:

    The differences are likely to come from the way AA' is factored inside the barrier.

    You can see that by comparing the 'lean' and 'inflated' log lines, focusing on number of non-zeros (think, Choleski factorization) and the respective estimated number of operations required, namely

    <lean>

    Barrier statistics:
    Dense cols : 126
    AA' NZ : 4.517e+06
    Factor NZ : 1.333e+08 (roughly 1.7 GBytes of memory)
    Factor Ops : 5.380e+11 (roughly 8 seconds per iteration)

    <inflated>

    Barrier statistics:
    Dense cols : 136
    AA' NZ : 7.220e+06
    Factor NZ : 3.767e+07 (roughly 1.7 GBytes of memory)
    Factor Ops : 2.222e+09 (less than 1 second per iteration)
    Threads : 4


    There is a number of things you can try to see if the number of non-zeros and FLOP can be reduced for the leaner model.

    1) The row and column ordering could effect the factorization (even dramatically, in some cases).  Since you seem to do well for the inflated model, I would try to closely match this ordering, if possible, for the leaner model.

    2) You can experiment with the choice of the ordering algorithm Gurobi uses; basically, try all the options on a leaner model and see what happens (you do not need to push for the solution and terminate once you see the barrier stats), see here,

    https://www.gurobi.com/documentation/9.0/refman/barorder.html

    3) The number of dense columns may also play a big role in factorization -- you can think of these columns as being initiAlly removed from A, and added only later once factorization is achieved.  Only as a last resort, you can try chaining the dense column threshold setting GURO_PAR_BARDENSETHRESH parameter to some value, e.g., set it to 50, 100, 200, 400 etc., and 40, 25, 12 ... and see what happens.  Note the latter setting is undocumented and we do not guarantee that this will remain in place for any of the later version of Gurobi, so again, I would experiment with this only as a last resort.

     

     

    It is also possible that the leaner model is sufficiently different, and you will be stuck with an expensive factorization no matter what.  But, I would say it is worth a try.

     

    Hope this helps.

     

    0
    Comment actions Permalink
  • Leonard Göke

    Thank you for this very comprehensive answer! It provided me with a much better understanding about what is going on. I was actually able to solve the problem by updating the Gurobi package for Julia (not Gurobi itself), which probably affected the internal order of rows and columns. I’m now also achieving the performance improvements on the leaner model that I was hoping for.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk