A combined phase I-phase II scaled potential algorithm for linear programming (Q1181908)

The article presents a new method for solving a problem of linear programming in the standard form (a feasible set is described by linear equalities and nonnegative variables). It is a simple extension of the scaled potential algorithm which simultaneously obtains feasibility (phase I) and optimality (phase II) in the linear program without the addition of ``big \(M\)'' coefficients in the objective function. It uses a particularly simple lower bounding procedure requiring the solution of a single scalar quadratic equation. The algorithm is motivated by an algorithm of Freund and by Todd's improvement of a previous algorithm of the author. Convergence results are very similar to those of Todd.