Re: [Help-glpk] How to tell if lpx_simplex() needs to be restarted?

[Andrew Makhorin]

> For the small to medium-sized data sets, the lpx_simplex(lp) solution
>  pops
> out pretty 
> 
> quickly and there is no problem. I do, however, have some questions
>  when
> the data sets get 
> 
> large. 
> 
> For a really large data set (ne=160,000 and ia with some 200,000
>  elements),
> after 7 hours, 
> 
> the DOS screen reads:
> 
> .
> .
> 257000:   objval = 0.000000000e+000   infeas = 1.000000000e+000 (0)
> .
> .
> 
> and it has been like that for a while and continues to be so. Does
>  this
> mean I have done 
> 
> something wrong? Or is the process still running and I should give it
>  more
> time?
> 
> And on another (smaller) set of data, after 9 hours, the DOS screen
>  reads:
> .
> .
> 850684:   objval 5.138313894e+000   infeas = 4.854494849e-004 (8)
> spx_simplex: numerical instability (primal simplex, phase II)
> 850684:   objval 5.138313894e+000   infeas = 1.000000000e+000 (8)
> 850800:   objval 5.138297412e+000   infeas = 5.798016607e-001 (8)
> .
> .
> .
> 
> and the process continues. sometimes, I get a spx_simplex: numerical
> instability (primal 
> 
> simplex, phase I) message too.
> 
> 
> 9+ hours of simulation seems far too long, compared to the minutes
>  taken
> for the smaller 
> 
> data sets. In general, how do I know if I have done something wrong
>  and I
> should 
> 
> debug/restart the process? And how can I tell if everything is going
>  on
> fine and I should 
> 
> just let the computer do its work?

The simplex falls into an infinite loop due to numerical instability.
Probably the problem is badly scaled. Could you please gzip and send
me the problem data in mps format before the call to lpx_simplex which
leads to cycling?

The solution time for instances like yours (i.e. having 160,000
coefficients) must be not more than 10-15 minutes in worst cases.

Andrew Makhorin