Finding an interior point in the optimal face of linear programs

The authors study the problem of finding a point in the relative interior of the optimal face of a linear program. They prove that in the worst case such a point can be obtained in O(n³L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. The authors also show how to find such a point in practice. They report and discuss computational results obtained for the linear programming problems in the NETLIB test set.