Computational experience with a primal-dual interior point method for linear programming

DOI10.1016/0024-3795(91)90275-2zbMath0731.65049OpenAlexW2030490984WikidataQ60140256 ScholiaQ60140256MaRDI QIDQ808184

Roy E. Marsten, Irvin J. Lustig, David F. Shanno

Publication date: 1991

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(91)90275-2

zbMATH Keywords

linear programminglogarithmic barrier functionpreconditionerimplementationcomputational experienceprimal-dual interior point algorithmpreconditioned conjugate gradient algorithmcode OB1incomplete Cholesky typeMINOS simplex code

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)

Related Items

Conic convex programming and self-dual embedding, 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, A Schur complement approach to preconditioning sparse linear least-squares problems with some dense rows, Combining phase I and phase II in a potential reduction algorithm for linear programming, Computational experience with a globally convergent primal-dual predictor-corrector algorithm for linear programming, Polynomiality of infeasible-interior-point algorithms for linear programming, The convergence of an interior-point method using modified search directions in final iterations, 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, Status determination by interior-point methods for convex optimization problems in domain-driven form, Improved complexity using higher-order correctors for primal-dual Dikin affine scaling, A QMR-based interior-point algorithm for solving linear programs, 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 COMPARATIVE STUDY OF PARALLEL DECOMPOSITIONS FOR MULTICOMMODITY FLOW PROBLEMS∗, Superlinear and quadratic convergence of some primal - dual interior point methods for constrained optimization, A primal-dual interior-point method for linear programming based on a weighted barrier function, Trajectory-following methods for large-scale degenerate convex quadratic programming, Linear programming with stochastic elements: An on-line approach, 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, A polynomial arc-search interior-point algorithm for linear programming, Primal-dual methods for linear programming, An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints, An incremental primal-dual method for nonlinear programming with special structure, A polynomial time infeasible interior-point arc-search algorithm for convex optimization, Regularization techniques in interior point methods, Unnamed Item, A globally convergent Lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds, 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, Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming, Solving combinatorial optimization problems using Karmarkar's algorithm, A little theorem of the big \({\mathcal M}\) in interior point algorithms, A diagonal quadratic approximation method for large scale linear programs, On combined phase 1-phase 2 projective methods for linear programming, Mixed integer programming: A historical perspective with Xpress-MP, Implementation of interior point methods for mixed semidefinite and second order cone optimization problems, A logarithm barrier method for linear programming, On using exterior penalty approaches for solving linear programming problems, A Comparison of Block Pivoting and Interior-Point Algorithms for Linear Least Squares Problems with Nonnegative Variables, Primal-Dual Interior-Point Methods for Domain-Driven Formulations, The complexity of self-regular proximity based infeasible IPMs, 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, 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 method for quadratic programs based on conjugate projected gradients, A weighted least squares study of robustness in interior point linear programming, 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, An interior point potential reduction method for constrained equations, An interior-point algorithm for linear programming with optimal selection of centering parameter and step size, Solving quadratically constrained convex optimization problems with an interior-point method, An infeasible interior-point arc-search algorithm for nonlinear constrained optimization, Strategic financial risk management and operations research, A New Predictor-corrector Infeasible Interior-point Algorithm for Linear Optimization in aWide Neighborhood, 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, Unnamed Item, Higher-order derivatives in linear and quadratic programming, Solving large-scale linear programs by interior-point methods under the Matlab^∗Environment^†, A parallel interior point algorithm for linear programming on a network of transputers, The BPMPD interior point solver for convex quadratic problems, LOQO:an interior point code for quadratic programming, Advances in design and implementation of optimization software, Splitting dense columns in sparse linear systems, A primal-dual infeasible-interior-point algorithm for linear programming, On the expected optimal value of random assignment problems: Experimental results and open questions, Optimizing over three-dimensional subspaces in an interior-point method for linear programming, Applying the progressive hedging algorithm to stochastic generalized networks, Parallel interior-point method for linear and quadratic programs with special structure, 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, On the convergence of a predictor-corrector variant algorithm

Uses Software

• NETLIB LP Test Set

Cites Work

• Feasibility issues in a primal-dual interior-point method for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• Affine-scaling for linear programs with free variables
• An implementation of Karmarkar's algorithm for linear programming
• Generation of degenerate linear programming problems
• Modification of the minimum-degree algorithm by multiple elimination
• Formulating Two-Stage Stochastic Programs for Interior Point Methods
• An Implementation of a Primal-Dual Interior Point Method for Linear Programming
• Implementation of a Dual Affine Interior Point Algorithm for Linear Programming
• Further Development of a Primal-Dual Interior Point Method
• Analysis of mathematical programming problems prior to applying the simplex algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item