> 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 _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk