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

[Andrew Makhorin]

Chris,

> I have a draft patch that introduces an internal API for keeping the
> dual simplex state between calls and adjusting it for new bounds. It
> works fine and speeds up pseudocost initialisation for all
> configurations of the solver (i.e. combinations of USE_AT, EXCL and
> SHIFT). 

Sorry, I don't catch your idea. On initializing pseudocosts there
appears the same implementation issue as for strong branching (which is
still not implemented in glpk). Namely, given a subset of structural
variables and their new lower and upper bounds we need to solve a set of
LPs introducing one new lower/upper bound for every variable and keeping
other bounds untouched. It is obviously natural to start solving every
LP from the optimal point of the master LP, which (the point) is primal
and dual feasible; introducing a new bound makes the solution primal
infeasible, but keeps its dual feasibility, so for reoptimization the
dual simplex can be used. However, to start the search we need to have
the basis factorization corresponding to the optimal basic solution of
the master LP. Currently the pseudocost routine just invalidates the
factorization to compute it from scratch every time it starts solving a
next LP and thus takes much time. This is the only issue; I see no other
points where the pseudocosts initialization procedure could be improved.


Andrew Makhorin