  Currently, the simplex method and the interior point method are indisputably
the most popular algorithms for solving linear programs, LPs. Unlike general
conic programs, LPs with a finite optimal value do not require strict
feasibility in order to establish strong duality. Hence strict feasibility is
seldom a concern, even though strict feasibility is equivalent to stability and
a compact dual optimal set. This lack of concern is also true for other types
of degeneracy of basic feasible solutions in LP. In this paper we discuss that
the specific degeneracy that arises from lack of strict feasibility necessarily
causes difficulties in both simplex and interior point methods. In particular,
we show that the lack of strict feasibility implies that every basic feasible
solution, BFS, is degenerate; thus conversely, the existence of a nondegenerate
BFS implies that strict feasibility (regularity) holds. We prove the results
using facial reduction and simple linear algebra. In particular, the facially
reduced system reveals the implicit non-surjectivity of the linear map of the
equality constraint system. As a consequence, we emphasize that facial
reduction involves two steps where, the first guarantees strict feasibility,
and the second recovers full row rank of the constraint matrix. This
illustrates the implicit singularity of problems where strict feasibility
fails, and also helps in obtaining new efficient techniques for preproccessing.
We include an efficient preprocessing method that can be performed as an
extension of phase-I of the two-phase simplex method. We show that this can be
used to avoid the loss of precision for many well known problem sets in the
literature, e.g., the NETLIB problem set.
