A simplified homogeneous and self-dual linear programming algorithm and its implementation

The authors present a simplification and generalization of the recent homogeneous and self-dual linear programming algorithm. The algorithm does not use any Big-M initial point and achieves -iteration complexity, where n and L are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, the authors code solves NETLIB problems, feasible or infeasible, starting simply from (primal variables), (dual variables), (dual slack variables), where e is the vector of all one. They describe the present computational experience in solving these problems, and compare the results with OB1.60, a state-of-the-art implementation of interior-point algorithms.