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

[Andrew Makhorin]

Chris,

Thank you very much for very useful experiments.

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

If reoptimization takes more simplex iterations than BFD is able to
provide without basis reinversion (i.e. without computing the
factorization from scratch), FT + bfd_copy may win, because updating the
factorization with FT is generally faster than with SC. However, SC has
many important advantages: it is more numerically stable (esp. when
Givens rotations are used for updating a dense submatrix of the SC
factorization), it allows using block-triangular decomposition of the
initial basis, and it allows using dense linear algebra routines (like
BLAS); besides it allows updating the factorization on adding/removing
rows of the basis. The only advantage of FT is its speed; however, if
you try to solve some lp with --ft (default option) and with --cbg or
--cgr, you may notice that the solution times don't differ significantly
(maybe percents, but not times). 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.

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


Best regards,

Andrew Makhorin