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

DOI10.1007/BF01582899zbMath0747.90060MaRDI QIDQ1181908

Kurt M. Anstreicher

Publication date: 27 June 1992

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

zbMATH Keywords

optimalityfeasibilitylower bounding procedurescaled potential algorithm

Mathematics Subject Classification ID

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

Related Items

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, On interior algorithms for linear programming with no regularity assumptions, Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions

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 polynomial Newton method for linear programming
• A combined phase I-phase II projective algorithm for linear programming
• Conical projection algorithms 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
• On Anstreicher's combined phase I-phase II projective algorithm 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
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
• Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method