A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start

DOI10.1007/BF01582900zbMath0754.90033OpenAlexW1992975148MaRDI QIDQ1181909

Robert M. Freund

Publication date: 27 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01582900

zbMATH Keywords

interior-point methodspotential function reduction algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems, Combining phase I and phase II in a potential reduction algorithm for linear programming, Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming, Potential-reduction methods in mathematical programming, An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution, New complexity results for the Iri-Imai method, A primal-dual potential reduction method for problems involving matrix inequalities, A combined phase I-phase II scaled potential algorithm for linear programming, A new warmstarting strategy for the primal-dual column generation method, Solving combinatorial optimization problems using Karmarkar's algorithm, On combined phase 1-phase 2 projective methods for linear programming, A warm-start dual simplex solution algorithm for the minimum flow networks with postoptimality analyses, Implementation of warm-start strategies in interior-point methods for linear programming in fixed dimension, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, Active-set prediction for interior point methods using controlled perturbations

Cites Work

• Unnamed Item
• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• A combined phase I-phase II projective algorithm for linear programming
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• On Anstreicher's combined phase I-phase II projective algorithm for linear programming
• Polynomial affine algorithms for linear programming
• A Centered Projective Algorithm for Linear Programming