Skip to main content

Criteria for Barrier method early termination

Answered
Martin Staadecker
Gurobi-versary
First Comment
First Question

Hello there!

I often get the following error when running the barrier algorithm (method=2) on a large LP model.

Barrier performed 308 iterations in 5531.94 seconds
Sub-optimal termination - objective 1.14188261e+08

My question is what are the conditions that cause this error? Is it that if too little progress is made on an iteration then Gurobi stops the barrier algorithm? If so, how is "progress" defined (size of primal dual objective gap?). Is there a tolerance I can modify to change when Gurobi "gives up" and moves on to crossover? Would improving the numerical properties of the model reduce the likelihood of Gurobi giving up?

I would much rather that the model found the barrier solution even if this took more time since crossover takes even longer. Is there a parameter I can tweak to achieve this?

Thank you!

Martin

0

Comments

3 comments

Date Votes
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    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
  • Martin Staadecker
    • Edited
    Gurobi-versary
    First Comment
    First Question

    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
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    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

Please sign in to leave a comment.

Didn't find what you were looking for?

New post