Combining phase I and phase II in a potential reduction algorithm for linear programming
From MaRDI portal
Publication:2368075
Most interior-point algorithms for linear programming assume that an initial interior point is known. This paper introduces an algorithm for attaining feasibility and optimality together. Convergence is proved, and the complexity is such that roughly \(O(n)\) iterations are required for each additional bit of precision.
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 combined phase I-phase II projective algorithm for linear programming
- A Family of Search Directions for Karmarkar's Algorithm
- 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 \(O(n^ 3L)\) potential reduction algorithm for linear programming
- An Implementation of a Primal-Dual Interior Point Method 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
(11)- Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions
- A combined phase I-phase II scaled potential algorithm for linear programming
- On interior algorithms for linear programming with no regularity assumptions
- 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
- Combining Interior-Point and Pivoting Algorithms for Linear Programming
- A two-phase linear programming approach for redundancy allocation problems
- Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities
- 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
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)
