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

[Andrew Makhorin]

> However, there was an additional objective for the dual simplex API
> that I left out from my previous email: I was going for something that
> can also be used in the branch & bound procedure to avoid
> reinitialising the internal dual simplex structures between successive
> calls. 

I thought about that. Converting glp_prob to internal primal/dual
simplex structures takes a tiny percentage of the overall solution time,
so I decided not to complicate the interface. Please note that in a
general case the b&b procedure can solve node subproblems in a
"non-chronological" order. BTW, currently due to Forrest-Tomlin update
adding a row (e.g. cutting plane ineq) invalidates the factorization, so
it is computed from scratch every time the reoptimization is needed
while Schur-complement allows updating the factorization even on adding
and deleting rows and columns.

> 
> > The procedure above can be implemented *within* the dual simplex
> > driver and thus can use internal data structures of the simplex
> > routines (no API is needed).
> 
> I feel that this procedure is a bit too high level to include in the
> simplex routines, for two reasons:
> 1. It requires knowledge of the factorisation to use inside the
> simplex routines, breaking modularity.

I don't think so. After the basis has been just factorized from scratch,
i.e. when no updates have been made yet, the basis factorization module
(src/bfd.c) allows to change the factorization used (Forrset-Tomlin or
Schur-complement); there exists something like a mini-api between the
simplex routines and the basis factorization module.

> 2. I don't see how variations of strong branching like the ones
> presented in "Branching on nonchimerical fractionalities" by Fischetti
> and Monaci can be implemented on top of this procedure.

Will think over that.

> 
> Therefore I still think than a different internal API is needed, with
> this procedure (and others) implemented on top of it. I'll think about
> it some more and get back to you with a more detailed proposal for
> this API.
> 
> > 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".
> 
> Is this what you were referring to in
> http://lists.gnu.org/archive/html/help-glpk/2012-06/msg00023.html ?
> 

Yes, I just meant Schur-complement factorization.


Best regards,

Andrew Makhorin