What is the best method to find for a linear system of inequalities $Ax\ge b$ with dense $A$ of moderate dimension the affine subspace spanned by the feasible points (i.e., the implied equalities $(Ax)i=b_i$) and a relatively interior feasible point in this subspace?
It shouldn't need the solution of many linear programs. I recall vaguely from long ago that appropriate postprocessing of the solution of a single appropriate LP should be sufficient, but don't remember details.
Probably not the most efficient way, but you could do:
$Ax - s = b$
$s \geq 0$
Then maximize $s_{i}$ with respect to the inequalities for $i=1, 2, \ldots, m$. If the maximum value of some $s_{i}$ is 0, then that inequality is one of the implied equalities. You'll want to remove any redundant equations that appear.
Once you've found your system of equations, use LP to find a particular point that satisfies the original inequalities, and then express the affine hull in terms of that particular solution and a basis for the null space of the matrix of implied equality constraints. You can now rewrite the original system of inequalities in terms of the coefficients with respect to this basis and reduce the dimension.
In terms of this new basis, find the Chebyshev center of the feasible set within the implied affine set by solving another LP.
P.S. A little research on the internet found a solution to this problem that requires the solution of only one LP. However, the solution must be strictly complementary (something that you don't get from the simplex method but can get using a primal-dual interior point method.) See Theorem 8 in this 1996 paper by Harvey Greenberg and the earlier sources that he cites:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.8466&rep=rep1&type=pdf
You may want to take a look at a book on linear programming. Finding a starting point for the vertex algorithm of linear programming entails exactly the question you are asking on here. The algorithm used is usually called "phase 1" in linear programming.
