Dealing with 'Suboptimal termination' in Barrier Method
AnsweredI'm working with a moderately large LP, and have found the barrier method without crossover to perform reasonably well in terms of computational time. Below are some typical barrier stats:
Optimize a model with 920617 rows, 10254516 columns and 24451038 nonzeros
Coefficient statistics:
Matrix range [2e04, 8e+03]
Objective range [7e01, 2e+00]
Bounds range [0e+00, 0e+00]
RHS range [9e01, 1e+01]
Presolve removed 100508 rows and 9855002 columns (presolve time = 6s) ...
Presolve removed 100734 rows and 9855002 columns
Presolve time: 7.97s
Presolved: 819883 rows, 399514 columns, 14402598 nonzeros
Ordering time: 0.00s
Barrier statistics:
Dense cols : 2
AA' NZ : 1.251e+08
Factor NZ : 1.103e+09 (roughly 10.0 GBytes of memory)
Factor Ops : 1.226e+13 (roughly 60 seconds per iteration)
Threads : 6
A model like this terminates with the 'Suboptimal termination' flag, however the log doesn't show any of the typical warnings which would imply numerical issues. For example, some of the last few lines from the same log file:
116 2.93451614e+04 2.93450620e+04 1.95e04 5.68e13 9.85e08 7682s
117 2.93451614e+04 2.93450620e+04 1.95e04 4.98e13 9.85e08 7745s
Barrier performed 117 iterations in 7745.48 seconds
Suboptimal termination  objective 2.93451613e+04
Looking at the output, I know the solution it's giving me is suboptimal judging by the values I see for dual variables (switching signs for inequality constraints). I've tried allowing crossover, however this usually takes an extraordinarily long time (days). My question is how can I get a handle on the specific numerical issues which are forcing the barrier method to terminate in this way?
Thanks in advance!

You could try tightening the barrier convergence tolerance (BarConvTol). There is a tradeoff between the effort spent in barrier and that spent in crossover. If barrier is performing well (and from what I can see, the last iteration takes pretty much average time), tightening this tolerance can sometimes reduce the time spent in crossover.
You might also want to take a look at the numerical properties of your model. Your matrix range is rather big [2e04, 8e+03]. Maybe our Numerics Guidelines can be helpful.
0
Please sign in to leave a comment.
Comments
1 comment