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

[Chris Matrakidis]

Andrew,

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

I'm not sure which patch confuses you, so I'll describe all of them,
since they try to address three different issues.
1. pcost1.patch just reuses the same glp_prob to avoid calling
glp_create_prob() and glp_copy_prob() repeatedly, but the
factorisation is still invalidated every time before calling dual
simplex.
2. pcost2.patch and pcost3.patch calculate the factorisation once and
keep a copy which is restored before every call to glp_simplex(). I
tried a simpler version where the factorisation is just copied from
the master LP every time, but this changed the calculated pseudocosts
and the branching seemed to be less accurate, so I decided to leave it
aside until I have time to do more exhaustive testing.
3. dual_API1.patch and dual_API2.patch define an internal API to keep
the data structures inside spydual.c and update them for bound (and
factorisation) changes before the next call. This avoids the overhead
for making multiple copies of the same problem data for each simplex
call but as I said, I'm not happy with the way I designed this API.

So the second point above is the one you are describing, but I also
found that the data copying takes a considerable portion of the time
for pseudocost initialisation.

I hope this makes the intention of the patches clearer, but do ask if
you need more details.

Best Regards,

Chris Matrakidis