Dealing with 'Sub-optimal termination' in Barrier Method
Answered
I'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 [2e-04, 8e+03]
Objective range [7e-01, 2e+00]
Bounds range [0e+00, 0e+00]
RHS range [9e-01, 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 'Sub-optimal 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.95e-04 5.68e-13 9.85e-08 7682s
117 2.93451614e+04 2.93450620e+04 1.95e-04 4.98e-13 9.85e-08 7745s
Barrier performed 117 iterations in 7745.48 seconds
Sub-optimal termination - objective 2.93451613e+04
Looking at the output, I know the solution it's giving me is sub-optimal 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 trade-off 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 [2e-04, 8e+03]. Maybe our Numerics Guidelines can be helpful.
0
Please sign in to leave a comment.
Comments
1 comment