[Bug-glpk] Re: None

[Andrew Makhorin]

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

The glpk simplex code used on the phase I is based on the method of one
artificial variable. This variable is introduced in the basis to make the
solution primal feasible, and its activity is a measure of infeasibility,
so the objective on the phase I is minimization of this variable. If the
artificial variable has zero activity, the phase I is finished; however,
it may happen that having zero activity the artificial variable is still
basic, in which case it must be removed from the basis by replacing by any
other dependent variable. It must be necessarily removed (at the end of
the phase I or phase II), because in the original problem there is no such
variable.

Unfortunately, I do not remember in which article the method was
suggested (somewhere in the mid of 1980's), but its idea is very easy,
and all necessary formulae can be easily derived (for details please see
comments to the routine lpx_prim_art in the file glplpx6a.c).

Andrew Makhorin