Re: [Help-glpk] Patches to improve pseudocost initialisatiion speed

[Chris Matrakidis]

Andrew,

> Probably there should be an option to
> choose between FT+bfd_copy and SC. In any case bfd_copy would be useful
> addition I think.

Since we are talking about pseudocosts here, where currently only 30
simplex iterations are done, I
see two options:
1. Always use FT update + bfd_copy
2. Choose between bfd_copy and bfd_reset depending on the update
method selected by the user.
My preference would be for the second choice, under the assumption
that the user has selected an alternative update method for additional
accuracy. The attached schur3.patch implements this approach.

>> > This approach, however, limits
>> > the number of simplex iteration (say, to 100-200), since if
>> > refactorization is needed, to keep B0 = L0 * U0 we should stop.
>>
>> I suppose this means that a new simplex flag may be needed, to stop
>> when re-factorisation is required.
>
> Perfectly correct. Currently, if BFD is unable to perform update, the
> simplex routine computes the factorization from scratch and then
> continues the search; however, in the case of estimation of objective
> degradation the dual simplex should stop reporting the current
> super-optimal (i.e. primal infeasible and dual feasible) basic solution.

A suggestion for a way to implement this is in the attached
schur4.patch. This adds a new simplex method GLP_DUALNF, where dual
simplex fails instead of calling the factorization procedure.

Both patches apply on top of the previous ones in the series.


Best Regards,

Chris Matrakidis