Combining phase I and phase II in a potential reduction algorithm for linear programming

DOI10.1007/BF01581241zbMath0777.90030OpenAlexW1985408040MaRDI QIDQ2368075

Michael J. Todd

Publication date: 22 August 1993

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

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

zbMATH Keywords

complexityconvergenceinterior-point algorithmscombined phase I-phase II method

Mathematics Subject Classification ID

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

Related Items

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, On interior algorithms for linear programming with no regularity assumptions, A little theorem of the big \({\mathcal M}\) in interior point algorithms, Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions

Cites Work

• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• Feasibility issues in a primal-dual interior-point method for linear programming
• On monotonicity in the scaled potential algorithm for linear programming
• Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• 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
• A potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start
• Modified barrier functions (theory and methods)
• On Anstreicher's combined phase I-phase II projective algorithm for linear programming
• On combined phase 1-phase 2 projective methods for linear programming
• Polynomial affine algorithms for linear programming
• Linear updates for a single-phase projective method
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• An Implementation of a Primal-Dual Interior Point Method for Linear Programming
• A Family of Search Directions for Karmarkar's Algorithm