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
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
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!
Please sign in to leave a comment.