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

DOI10.1007/BF01581241MaRDI QIDQ2368075zbMATH OpenOpenAlexFDO

Authors 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

convergencecomplexityinterior-point algorithmscombined phase I-phase II method

Mathematics Subject Classification ID

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

Recommendations

• A combined phase I-phase II scaled potential algorithm for linear programming
• A Low Complexity Interior-Point Algorithm for Linear Programming
• An infeasible-interior-point potential-reduction algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Combining Interior-Point and Pivoting Algorithms for Linear Programming

Cites work

• A Family of Search Directions for Karmarkar's Algorithm
• 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 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 Implementation of a Primal-Dual Interior Point Method for Linear Programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Computational experience with a primal-dual interior point method for linear programming
• Feasibility issues in a primal-dual interior-point method for linear programming
• Linear updates for a single-phase projective method
• 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
• On monotonicity in the scaled potential 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
• Theoretical efficiency of a shifted-barrier-function algorithm for linear programming

Cited in

(9)

• A Potential Reduction Algorithm with User-Specified Phase I–Phase II Balance for Solving a Linear Program from an Infeasible Warm Start
• A little theorem of the big \({\mathcal M}\) in interior point algorithms
• Feasible region contraction interior point algorithm
• Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions
• A two-phase linear programming approach for redundancy allocation problems
• 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
• Potential-reduction methods in mathematical programming
• Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities

This page was built for publication: Combining phase I and phase II in a potential reduction algorithm for linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368075)