Criteria for Barrier method early termination
AnsweredHello 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
Suboptimal 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

Hi Martin,
Suboptimal 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 rescale 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
 NumericFocus to make Gurobi focus more towards numerical accuracy
 decrease the tolerances BarConvTol, BarQCPConvTol to make Gurobi's Barrier algorithm converge quicker
 decrease the FeasibilityTol to possibly overcome numerical issues with constraints
 set the BarHomogeneous parameter to 1
 experiment with the BarCorrectors parameter
Since your model is an LP, you can turn off crossover via the Crossover parameter.
Best regards,
Jaromił0 
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 1E3).
 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 1e05 Prev: 1e06 Min: 1e09 Max: 0.01 Default: 1e06
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 [9e04, 1e+04]
Objective range [4e03, 4e+07] Bounds range [3e02, 4e+05]
RHS range [6e04, 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.67e04 3.50e03 3.70e+01 1303s
Barrier performed 414 iterations in 1303.29 seconds
Suboptimal termination  objective 2.82621316e+08Let me know if you have any ideas.
0 
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 [9e04, 1e+04]
Objective range [4e03, 4e+07]
Bounds range [3e02, 4e+05]
RHS range [6e04, 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.
Comments
3 comments