Computational experience with a primal-dual interior point method for linear programming
From MaRDI portal
This important paper describes the heuristics and implementation details used in the code OB1, which implements a primal-dual interior point algorithm for linear programming. The algorithm is motivated in terms of the logarithmic barrier function, and the strategy for choosing the initial point and the heuristic for decreasing the barrier parameter are described. The authors discuss the main computational engine of the code, namely, the preconditioned conjugate gradient algorithm for solving the sparse linear system of equations that arises at each iteration. The preconditioner is of the incomplete Cholesky type, but special care is needed in handling columns of the constraint matrix which destroy the sparsity of the coefficient matrix. Computational comparisons with the MINOS simplex code are given for problems in the expanded netlib test set.
Recommendations
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- scientific article; zbMATH DE number 4164543
- Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming
- On the Implementation of a Primal-Dual Interior Point Method
- scientific article; zbMATH DE number 5630197
- A primal-dual infeasible-interior-point algorithm for linear programming
- A DUAL INTERIOR PRIMAL SIMPLEX METHOD FOR LINEAR PROGRAMMING METHOD
- Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
- An eligible primal-dual interior-point method for linear optimization
- Feasibility issues in a primal-dual interior-point method for linear programming
Cites work
- Affine-scaling for linear programs with free variables
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- An implementation of Karmarkar's algorithm for linear programming
- Analysis of mathematical programming problems prior to applying the simplex algorithm
- Feasibility issues in a primal-dual interior-point method for linear programming
- Formulating Two-Stage Stochastic Programs for Interior Point Methods
- Further Development of a Primal-Dual Interior Point Method
- Generation of degenerate linear programming problems
- scientific article; zbMATH DE number 3976197 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- scientific article; zbMATH DE number 554736 (Why is no real title available?)
- Implementation of a Dual Affine Interior Point Algorithm for Linear Programming
- Interior path following primal-dual algorithms. I: Linear programming
- Modification of the minimum-degree algorithm by multiple elimination
Cited in
(only showing first 100 items - show all)- Computational experience with a dual affine variant of Karmarkar's method for linear programming
- On finding a vertex solution using interior point methods
- On the complexity of following the central path of linear programs by linear extrapolation. II
- Computational results of an interior point algorithm for large scale linear programming
- A brief description of ALPO
- Solving combinatorial optimization problems using Karmarkar's algorithm
- A diagonal quadratic approximation method for large scale linear programs
- On combined phase 1-phase 2 projective methods for linear programming
- An interior point method for quadratic programs based on conjugate projected gradients
- A weighted least squares study of robustness in interior point linear programming
- Strategic financial risk management and operations research
- Computing Karmarkar's projections in stochastic linear programming
- Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming
- The role of the augmented system in interior point methods
- A parallel interior point algorithm for linear programming on a network of transputers
- A primal-dual infeasible-interior-point algorithm for linear programming
- On the expected optimal value of random assignment problems: Experimental results and open questions
- Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited
- Sensitivity method for basis inverse representation in multistage stochastic linear programming problems
- Primal-dual interior point approach for computing \(l_ 1\)-solutions and \(l_ \infty\)-solutions of overdetermined linear systems
- A primal-dual affine-scaling potential-reduction algorithm for linear programming
- On the number of iterations of Karmarkar's algorithm for linear programming
- Interior dual proximal point algorithm for linear programs
- Superlinear convergence of infeasible-interior-point methods for linear programming
- Primal-dual algorithms for linear programming based on the logarithmic barrier method
- Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming
- Polynomiality of infeasible-interior-point algorithms for linear programming
- Recovering an optimal LP basis from an interior point solution
- A predictor-corrector infeasible-interior-point algorithm for linear programming
- Asymptotic convergence in a generalized predictor-corrector method
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Improved complexity using higher-order correctors for primal-dual Dikin affine scaling
- A QMR-based interior-point algorithm for solving linear programs
- Superlinear and quadratic convergence of some primal - dual interior point methods for constrained optimization
- Linear programming with stochastic elements: An on-line approach
- Higher-order derivatives in linear and quadratic programming
- Advances in design and implementation of optimization software
- Parallel interior-point method for linear and quadratic programs with special structure
- A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows
- Symmetric indefinite systems for interior point methods
- Exploiting special structure in a primal-dual path-following algorithm
- Efficient solution of two-stage stochastic linear programs using interior point methods
- A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points
- An interior point potential reduction method for constrained equations
- The convergence of an interior-point method using modified search directions in final iterations
- Solution of and bounding in a linearly constrained optimization problem with convex, polyhedral objective function
- A generalized homogeneous and self-dual algorithm for linear programming
- A primal-dual interior-point method for linear programming based on a weighted barrier function
- The implementation of linear programming algorithms based on homotopies
- A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems
- Presolving in linear programming
- Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs
- An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
- An infeasible-interior-point algorithm using projections onto a convex set
- A relaxed primal-dual path-following algorithm for linear programming
- A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
- Solving real-world linear ordering problems using a primal-dual interior point cutting plane method
- An interior point method for general large-scale quadratic programming problems
- Gigaflops in linear programming
- Primal-dual methods for linear programming
- An incremental primal-dual method for nonlinear programming with special structure
- Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming
- An interior-point algorithm for linear programming with optimal selection of centering parameter and step size
- An infeasible interior-point arc-search algorithm for nonlinear constrained optimization
- Status determination by interior-point methods for convex optimization problems in domain-driven form
- On the convergence of a predictor-corrector variant algorithm
- Combining phase I and phase II in a potential reduction algorithm for linear programming
- Trajectory-following methods for large-scale degenerate convex quadratic programming
- The complexity of self-regular proximity based infeasible IPMs
- An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints
- Solving quadratically constrained convex optimization problems with an interior-point method
- scientific article; zbMATH DE number 4199963 (Why is no real title available?)
- On the Implementation of a Primal-Dual Interior Point Method
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- Further Development of a Primal-Dual Interior Point Method
- Solving large-scale linear programs by interior-point methods under the Matlab∗Environment†
- A Comparison of Block Pivoting and Interior-Point Algorithms for Linear Least Squares Problems with Nonnegative Variables
- Regularization techniques in interior point methods
- Implementation of interior point methods for mixed semidefinite and second order cone optimization problems
- The BPMPD interior point solver for convex quadratic problems
- LOQO:an interior point code for quadratic programming
- Conic convex programming and self-dual embedding
- On a dual method for a specially structured linear programming problem with application to stochastic programming
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- A COMPARATIVE STUDY OF PARALLEL DECOMPOSITIONS FOR MULTICOMMODITY FLOW PROBLEMS∗
- A logarithm barrier method for linear programming
- A new predictor-corrector infeasible interior-point algorithm for linear optimization in a wide neighborhood
- Multicommodity network flows: A survey. II: Solution methods
- Primal-dual interior-point methods for domain-driven formulations
- A review of termination rules of an inexact primal-dual interior point method for linear programming problems
- Mixed integer programming: A historical perspective with Xpress-MP
- A globally convergent Lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds
- A primal-dual infeasible-interior-point algorithm for multiple objective linear programming problems
- A primal-dual infeasible-interior-point algorithm for multiple objective linear programming problems
- On using exterior penalty approaches for solving linear programming problems
- A polynomial time infeasible interior-point arc-search algorithm for convex optimization
- Riemannian Interior Point Methods for Constrained Optimization on Manifolds
- A little theorem of the big \({\mathcal M}\) in interior point algorithms
- Splitting dense columns in sparse linear systems
- Optimizing over three-dimensional subspaces in an interior-point method for linear programming
This page was built for publication: Computational experience with a primal-dual interior point method for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808184)
