[Help-glpk] Re: Initial Basis

[Andrew Makhorin]

> Suppose I solve a linear programming problem with the simplex
> algorithm, then change a row of coefficients. I then change the
> previously found optimal basis slightly or not at all (by one or zero
> variables -- both cases are relevant here) so that the new basis is
> primal feasible. Given how little I changed from the first problem, it
> seems that I should be able to solve a second one without having to
> restart from scratch. Is this possible?

Yes. If you change a row, the optimal basic solution may either remain
optimal or become primal infeasible, but in both cases it remains dual
feasible, so you can reoptimize the modified lp with the dual simplex
using the previously found basis to start from. If you also change
bounds of some variables and can guarantee that the current basis
remains primal feasible and therefore optimal, you may use the primal or
dual simplex just to compute new solution components. In any case, if
you change your lp slightly, it has sense to start from the previosly
found optimal basis, not from scratch.