Re: [Help-glpk] Figure out the exiting variable after simplex iteration

[Andrew Makhorin]

> And I now see what you mean about multiple pivots.  I must be
> missing/forgetting something rather fundamental.  If I introduce a new
> column that can improve the objective, why is it there are potentially
> multiple pivots?  I would just expect the new column to enter and some
> other column to exit.  Any brief (or detailed) explanation would be
> appreciated.

This is because every pivot changes not only primal values of variables
but also dual ones (reduced costs). If you have optimal basis, all
reduced costs have correct signs, and the dual basic solution is
therefore feasible. Then you generate a column, i.e. add a new
non-negative variables to the formulation. If its reduced cost has
wrong sign, i.e. the basic solution becomes dual infeasible, the primal
simplex chooses this new variable to made it basic; note that it is the
only non-basic variable that can be chosen so far. However, once the
simplex has changed the basis to the adjacent one, reduced costs of
other non-basic variables have also changed, and there may appear
non-basic variables whose reduced costs have wrong sign indicating dual
infeasibility, though before such variables were "optimal". Thus, in
general case the simplex methods may need more than one iteration to
find the new optimum.