A dual phase-1 algorithm for the simplex method that handles all types of vari-
ables is presented. In each iteration it maximizes a piecewise linear function of dual
infeasibilities in order to make the largest possible step towards dual feasibility with
a selected outgoing variable. The algorithm can be viewed as a generalization of
traditional phase-1 procedures. It is based on the multiple use of the expensively
computed pivot row. By small amount of extra work per iteration, the progress it
can make is equivalent to many iterations of the traditional method. While this is its
most important feature, it possesses some additional favorable properties, namely,
it can be e cient in coping with degeneracy and numerical di culties. Both theo-
retical and computational issues are addressed. Some computational experience is
also reported which shows that the potentials of the method can materialize on real
world problems. This paper is based on IC Departmental Technical Report 2000/13
and contains an enhancement of the main algorithm.