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