RE: [Bug-glpk] Re: None

[Robert Fourer]

A note on phase I ...  Andrew Makhorin stated:

> Actually the glpk simplex code for the phase I does find a feasible
> solution, and the difficulty arises when the solver tries to drive
> away an artificial variable from the basis, that is needed to start the
> phase II.

For practical purposes it's better to let the artificial variables stay in phase
II's starting basis.  For phase II they have lower and upper bounds of zero and,
once they leave the basis -- necessarily by a degenerate iteration -- they are 
not
considered again to enter.  If the rows of the constraint matrix are linearly
dependent, then the columns of any square submatrix of the constraint matrix are
likewise dependent, and the artificial variables are needed in order to permit
phase II to proceed with a nonsingular basis matrix.  (This is the case that 
comes
up, for example, given the standard transportation problem formulation.)  An
similar situation arises when the rows are independent but close to being
dependent.

Bob Fourer
address@hidden