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

[Chris Matrakidis]

Hi Andrew,

Leaving aside the issue of the API for the time being, I did some
additional experiments in this area.

> To resolve this
> issue some time ago I implemented another factorization of the basis
> based on Schur complement (please see comments in src/bflib/scf.h),
> where B0 = L0 * U0 is not changed, so B = B0 can be easily restored as
> in case of "eta file".

I did try this, and it seems to work OK. The attached two patches
implement it on top of the three original patches I sent (pcost1.patch
to pcost3.patch). The first one just makes the pseudocost
initialisation use Schur complement updates, to use as a baseline
since the pseudocosts calculated may be different now. The second ones
introduces a bfd_reset() function that restores the original
factorisation and uses this instead of bfd_copy().

Unfortunately, it looks like that the speed gain from using bfd_reset
does not offset the overhead of Schur complement updates, so
Forrest-Tomlin update with bfd_copy seems to be the preferred option
here.

> 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.

Best Regards,

Chris Matrakidis

schur1.patch
Description: Text Data

schur2.patch
Description: Text Data