ON INTERIOR ALGORITHMS FOR LINEAR-PROGRAMMING WITH NO REGULARITY ASSUMPTIONS

The linear programming algorithm of Karmarkar (1984), and all interior methods subsequently devised, require a regularity assumption that the primal and/or dual problem possess a nonempty interior. In this note we devise a polynomial-time interior algorithm which will directly 'process' and linear program, with no regularity assumptions whatsoever, without the addition of any 'M' terms. Our method is based on the application of a combined phase I-phase II algorithm to a combined primal-dual problem.