A combined phase I-phase II scaled potential algorithm for linear programming
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.
- A combined phase I-phase II projective algorithm for linear programming
- A monotonic projective algorithm for fractional linear programming
- A new polynomial-time algorithm for linear programming
- A polynomial Newton method for linear programming
- A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- An extension of Karmarkar's algorithm for linear programming using dual variables
- Conical projection algorithms for linear programming
- scientific article; zbMATH DE number 4151220 (Why is no real title available?)
- Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
- Linear updates for a single-phase projective method
- On Anstreicher's combined phase I-phase II projective algorithm for linear programming
- Polynomial affine algorithms for linear programming
- Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
- Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions
- An improved general Phase-I method in linear programming
- On interior algorithms for linear programming with no regularity assumptions
- Potential-reduction methods in mathematical programming
- Some variants of the Todd low-complexity algorithm
- An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
- Solving real-world linear ordering problems using a primal-dual interior point cutting plane method
- New complexity results for the Iri-Imai method
- A primal-dual potential reduction method for problems involving matrix inequalities
- Combining phase I and phase II in a potential reduction algorithm for linear programming
- On monotonicity in the scaled potential algorithm for linear programming
This page was built for publication: A combined phase I-phase II scaled potential algorithm for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1181908)
