Criteria for Barrier method early termination

Answered

Comments

3 comments

  • Jaromił Najman

    Hi Martin,

    Sub-optimal termination is printed when the barrier algorithm does not make any (or only very small) progress in the solution value and cannot decrease the dual residual, meaning that although the final convergence criterion is met, the dual infeasibility cannot be reduced. This is often the case for problems with numerical issues. It is most often best to re-scale or reformulate the model to avoid shaky numerics. Could you post the coefficient statistics for your model or even the whole log file header?

    You could try to tackle this issue by experimenting with the following parameters

    Since your model is an LP, you can turn off cross-over via the Crossover parameter.

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Martin Staadecker

    Hello Jaromił,

    I few notes:

    - I am already using BarHomogeneous = 1 and have already loosened FeasibilityTol

    - I don't believe it is as much a problem of numerical issues as it is an issue in the difficulty of the problem. 90% of my runs complete with no problem and only a few runs where I've added a constraint or made the problem "harder" become suboptimal.

    - I can't use BarConvTol or BarQCPConvTol as the amount I'd have to decrease it by for it to converge is too big (the primal dual gap at the end of the file is on the order of 1E-3).

    - Here's my log file

    Changed value of parameter BarHomogeneous to 1 [469/1982] Prev: -1 Min: -1 Max: 1 Default: -1
    Changed value of parameter FeasibilityTol to 1e-05 Prev: 1e-06 Min: 1e-09 Max: 0.01 Default: 1e-06
    Changed value of parameter crossover to 0 Prev: -1 Min: -1 Max: 5 Default: -1
    Changed value of parameter method to 2
    Prev: -1 Min: -1 Max: 5 Default: -1 Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (linux64) Thread count: 32 physical cores, 64 logical processors, using up to 32 threads Optimize a model with 17351184 rows, 14308315 columns and 49851652 nonzeros Model fingerprint: 0x15315bb1
    Coefficient statistics:
    Matrix range [9e-04, 1e+04]
    Objective range [4e-03, 4e+07] Bounds range [3e-02, 4e+05]
    RHS range [6e-04, 4e+04]
    Presolve removed 12957396 rows and 9195371 columns (presolve time = 7s) ...
    Presolve removed 13164704 rows and 9402679 columns (presolve time = 12s) ...
    Presolve removed 13806972 rows and 10044947 columns (presolve time = 20s) ... Presolve removed 13806972 rows and 10044947 columns (presolve time = 20s) ...
    Presolve removed 14457506 rows and 10044947 columns (presolve time = 25s) ...
    Presolve removed 14457506 rows and 10044947 columns
    Presolve time: 25.63s
    Presolved: 2893678 rows, 4263368 columns, 12774836 nonzeros Elapsed ordering time = 33s Ordering time: 41.87s
    Barrier statistics: Dense cols : 1803 AA' NZ : 9.070e+06
    Factor NZ : 1.552e+08 (roughly 4.0 GBytes of memory)
    Factor Ops : 3.531e+11 (roughly 1 second per iteration)
    Threads : 32


    Objective Residual
    Iter Primal Dual Primal Dual Compl Time

    ...

    414 3.20489702e+08 3.22310987e+08 1.67e-04 3.50e-03 3.70e+01 1303s

    Barrier performed 414 iterations in 1303.29 seconds
    Sub-optimal termination - objective 2.82621316e+08

     

    Let me know if you have any ideas.

    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Martin,

    Thank you for the update.

    - I don't believe it is as much a problem of numerical issues as it is an issue in the difficulty of the problem. 90% of my runs complete with no problem and only a few runs where I've added a constraint or made the problem "harder" become suboptimal.

    The problem with numerical issues is that the usually only arise in "harder" problems. Thus, it is very well possible that for most of your runs Gurobi is able to successfully tackle the numerics but as soon as you add some complexity, the numerics just get out of hand.

    The reported coefficient statistics are

    Matrix range [9e-04, 1e+04]
    Objective range [4e-03, 4e+07]
    Bounds range [3e-02, 4e+05]
    RHS range [6e-04, 4e+04]

    Our Guidelines for Numerical Issues hold information on recommended coefficient ranges. We recommend to try to keep the coefficient in a range of at most 6 orders of magnitude. Obviously, this is not always possible.

    You could try experimenting with the ScaleFlag parameter to try different scaling techniques. Turning a more aggressive Presolve routine or turning it off completely may also help in this case. A more advanced parameter which might help here is the setting of BarCorrectors. Did you try the NumericFocus parameter? It may affect the performance but can usually help with numerically challenging models.

    Best regards,
    Jaromił

     

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk