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

[Chris Matrakidis]

Hi Andrew,

> I think your design is too complicated. It seems to me that both
> pseudo-cost initialization and strong branching could be implemented
> as a special call to the dual simplex routine.

I agree that this design is too complicated (except maybe the first
part that I think is straightforward). And I really like the idea you
outlined for restoring the original factorisation instead of copying
it.

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. This is something I think is needed, but, admittedly, the
version I showed is not appropriate for this.

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

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 ?


Best Regards,

Chris Matrakidis