An Implementation of a Primal-Dual Interior Point Method for Linear Programming

Kevin A. McShane
Kevin A. McShane
School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853
Search for more papers by this author
,
Clyde L. Monma
Clyde L. Monma
Mathematics and Operations Research, Bell Communications Research, Morristown, New Jersey 07960
Search for more papers by this author
,
David Shanno
David Shanno
RUTCOR, Rutgers University, New Brunswick, New Jersey 08903
Search for more papers by this author

Kevin A. McShane

School of Operations Research and Industrial Engineering, Cornell University, Ithaca, New York 14853

Search for more papers by this author

Clyde L. Monma

Mathematics and Operations Research, Bell Communications Research, Morristown, New Jersey 07960

Search for more papers by this author

David Shanno

RUTCOR, Rutgers University, New Brunswick, New Jersey 08903

Search for more papers by this author

Published Online:1 May 1989https://doi.org/10.1287/ijoc.1.2.70

Abstract

The purpose of this paper is to describe in detail an implementation of a primal-dual interior point method for solving linear programming problems. Preliminary computational results indicate that this implementation compares favorably with a comparable implementation of a dual affine interior point method, and with MINOS 5.0, a state-of-the-art implementation of the simplex method.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Cited by
- Orbit trajectory analysis and control of in-plane satellite constellation deployment using atmospheric drag
  Acta Astronautica, Vol. 232
- Efficient Reconstruction of Neural Mass Dynamics Modeled by Linear-Threshold Networks
  IEEE Transactions on Automatic Control, Vol. 70, No. 5
- Interior-Point Method
  1 January 2023
- A Non-Archimedean Interior Point Method and Its Application to the Lexicographic Multi-Objective Quadratic Programming
  30 November 2022 | Mathematics, Vol. 10, No. 23
- $$\mathtt {Tenscalc}$$: a toolbox to generate fast code to solve nonlinear constrained minimizations and compute Nash equilibria
  8 February 2022 | Mathematical Programming Computation, Vol. 14, No. 3
- Status determination by interior-point methods for convex optimization problems in domain-driven form
  19 June 2021 | Mathematical Programming, Vol. 194, No. 1-2
- Primal-Dual Newton’s Method with Steepest Descent for Linear Programming
  10 January 2019
- Zonotopic Constrained Kalman Filter Based on a Dual Formulation
- Robust Non-Rigid Motion Tracking and Surface Reconstruction Using $L_0$ Regularization
  IEEE Transactions on Visualization and Computer Graphics, Vol. 24, No. 5
- Active-set prediction for interior point methods using controlled perturbations
  19 January 2016 | Computational Optimization and Applications, Vol. 63, No. 3
- On the convergence of a predictor-corrector variant algorithm
  13 September 2014 | TOP, Vol. 23, No. 2
- A Study of the Complexity of an Infeasible Predictor-Corrector Variant of Mehrotra Algorithm
- Introduction
  10 October 2013
- Integer Linear Programming (ILP)
  10 October 2013
- Pivot Rule
  10 October 2013
- Dual Pivot Rule
  10 October 2013
- Simplex Phase-I Method
  10 October 2013
- Dual Simplex Phase-l Method
  10 October 2013
- Reduced Simplex Method
  10 October 2013
- Improved Reduced Simplex Method
  10 October 2013
- D-Reduced Simplex Method
  10 October 2013
- Criss-Cross Simplex Method
  10 October 2013
- Generalizing Reduced Simplex Method
  10 October 2013
- Geometry of the Feasible Region
  10 October 2013
- Deficient-Basis Method
  10 October 2013
- Dual Deficient-Basis Method
  10 October 2013
- Face Method
  10 October 2013
- Dual Face Method
  10 October 2013
- Pivotal Interior-Point Method
  10 October 2013
- Special Topics
  10 October 2013
- Simplex Method
  10 October 2013
- Duality Principle and Dual Simplex Method
  10 October 2013
- Implementation of the Simplex Method
  10 October 2013
- Sensitivity Analysis and Parametric LP
  10 October 2013
- Variants of the Simplex Method
  10 October 2013
- Decomposition Method
  10 October 2013
- Interior-Point Method
  10 October 2013
- Integral input-to-state stable saddle-point dynamics for distributed linear programming
- On the Complexity of a Mehrotra-Type Predictor-Corrector Algorithm
- Solving scalarized multi‐objective network flow problems using an interior point method
  17 August 2010 | International Transactions in Operational Research, Vol. 17, No. 5
- An optimal bandwidth allocation and data droppage scheme for differentiated services in a wireless network
  30 March 2009 | Wireless Communications and Mobile Computing, Vol. 10, No. 6
- Interior Point Methods for Nonlinear Optimization
  21 January 2010
- Fortran subroutines for network flow optimization using an interior point algorithm
  Pesquisa Operacional, Vol. 28, No. 2
- Dynamic Optimal Power Flow with Minimal Inter-Temporal Control Variable Changes
  Electric Power Components and Systems, Vol. 33, No. 10
- Product-form Cholesky factorization in interior point methods for second-order cone programming
  29 December 2004 | Mathematical Programming, Vol. 103, No. 1
- Quality-based I/O resource managementfor multimedia document database servers
  Multimedia Systems, Vol. 10, No. 3
- State Estimation of Systems With UPFCs Using the Interior Point Method
  IEEE Transactions on Power Systems, Vol. 19, No. 3
- State estimation of systems with embedded FACTS devices
- A Study of Preconditioners for Network Interior Point Methods
  Computational Optimization and Applications, Vol. 24, No. 1
- Advances in design and implementation of optimization software
  European Journal of Operational Research, Vol. 140, No. 2
- Interior-point methods for linear programming: a review
  International Journal of Mathematical Education in Science and Technology, Vol. 33, No. 3
- Parallel Interior Point Schemes for Solving Multistage Convex Programming
  Annals of Operations Research, Vol. 108, No. 1-4
- An easy way to teach interior-point methods
  European Journal of Operational Research, Vol. 130, No. 1
- Real power loss minimization using interior point method
  International Journal of Electrical Power & Energy Systems, Vol. 23, No. 1
- New Complexity Analysis of the Primal—Dual Newton Method for Linear Optimization
  Annals of Operations Research, Vol. 99, No. 1-4
- A truncated primal-infeasible dual-feasible network interior point method
  Networks, Vol. 35, No. 2
- Optimal mechanism design using interior-point methods
  Mechanism and Machine Theory, Vol. 35, No. 1
- A primal–dual interior point algorithm with an exact and differentiable merit function for nonlinear programming
  30 January 2008 | Optimization Methods and Software, Vol. 14, No. 1-2
- Interior-point methods and their applications to power systems: a classification of publications and software codes
  IEEE Transactions on Power Systems, Vol. 15, No. 1
- Improving an interior-point-based OPF by dynamic adjustments of step sizes and tolerances
  IEEE Transactions on Power Systems, Vol. 14, No. 2
- Projective Algorithms
- Interior Point Methods and Applications in Power Systems
- Bibliography
  14 October 2011
- Linear programming with stochastic elements: An on-line approach
  Computers & Mathematics with Applications, Vol. 33, No. 9
- An interior multiobjective primal-dual linear programming algorithm based on approximated gradients and efficient anchoring points
  Computers & Operations Research, Vol. 24, No. 4
- Several Algorithms to Determine Multipliers for Use in Cone-Ratio Envelopment Approaches to Efficiency Evaluations in DEA
- An Interior Multiobjective Linear Programming Algorithm Using Aspirations
- Numerical path following
- Q-SUPERLINEAR CONVERGENCE OF PRIMAL-DUAL INTERIOR POINT QUASI-NEWTON METHODS FOR CONSTRAINED OPTIMIZATION
  Journal of the Operations Research Society of Japan, Vol. 40, No. 3
- Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization
  Mathematical Programming, Vol. 75, No. 3
- An infeasible interior-point algorithm for optimal power-flow problems
  Electric Power Systems Research, Vol. 39, No. 1
- An Investigation of Interior-Point Algorithms for the Linear Transportation Problem
  SIAM Journal on Scientific Computing, Vol. 17, No. 5
- A predictor-corrector method for extended linear-quadratic programming
  Computers & Operations Research, Vol. 23, No. 8
- A Bilevel Programming Method for Pipe Network Optimization
  SIAM Journal on Optimization, Vol. 6, No. 3
- Convergence of an Infeasible Interior-Point Algorithm from Arbitrary Positive Starting Points
  SIAM Journal on Optimization, Vol. 6, No. 2
- Using aspiration levels in an interior primal-dual multiobjective linear programming algorithm
  Journal of Multi-Criteria Decision Analysis, Vol. 5, No. 1
- Using approximate gradients in developing an interactive interior primal-dual multiobjective linear programming algorithm
  European Journal of Operational Research, Vol. 89, No. 1
- Affine Scaling Algorithm
- Implementation of Interior-Point Methods for Large Scale Linear Programs
- Complementarity Problems
- A primal-dual interior-point method for linear programming based on a weighted barrier function
  Journal of Optimization Theory and Applications, Vol. 87, No. 2
- Primal—dual methods for linear programming
  Mathematical Programming, Vol. 70, No. 1-3
- Global Convergence of a Long-Step Affine Scaling Algorithm for Degenerate Linear Programming Problems
  SIAM Journal on Optimization, Vol. 5, No. 3
- Treatment of inequality constraints in power system state estimation
  IEEE Transactions on Power Systems, Vol. 10, No. 2
- Symmetric Quasidefinite Matrices
  SIAM Journal on Optimization, Vol. 5, No. 1
- On the convergence of the iteration sequence in primal-dual interior-point methods
  Mathematical Programming, Vol. 68, No. 1-3
- An interior point method for state estimation with current magnitude measurements and inequality constraints
- Primal-dual algorithms for linear programming based on the logarithmic barrier method
  Journal of Optimization Theory and Applications, Vol. 83, No. 1
- Superlinear convergence of infeasible-interior-point methods for linear programming
  Mathematical Programming, Vol. 66, No. 1-3
- Interior dual proximal point algorithm for linear programs
  European Journal of Operational Research, Vol. 77, No. 1
- Monotonicity of Primal and Dual Objective Values in Primal-dual Interior-point Algorithms
  SIAM Journal on Optimization, Vol. 4, No. 3
- A multiobjective interior primal-dual linear programming algorithm
  Computers & Operations Research, Vol. 21, No. 4
- A Study of Indicators for Identifying Zero Variables in Interior-Point Methods
  SIAM Review, Vol. 36, No. 1
- Global convergence in infeasible-interior-point algorithms
  Mathematical Programming, Vol. 65, No. 1-3
- On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
  SIAM Journal on Optimization, Vol. 4, No. 1
- A Genuine Quadratically Convergent Polynomial Interior Point Algorithm for Linear Programming
- Computational Methods For Linear Programming
- Stable Barrier-Projection and Barrier-Newton Methods for Linear and Nonlinear Programming
- Barrier-newton methods in mathematical programming
  23 June 2005
- The design and application of IPMLO. A FORTRAN library for linear optimization with interior point methods
  29 March 2011 | RAIRO - Operations Research, Vol. 28, No. 1
- The theory of linear programming:skew symmetric self-dual problems and the central path *
  Optimization, Vol. 29, No. 3
- An interior multiobjective primal-dual linear programming algorithm using approximated gradients and sequential generation of anchor points
  Optimization, Vol. 30, No. 2
- Computational experience with a primal-dual interior-point method for smooth convex programming
  Optimization Methods and Software, Vol. 3, No. 4
- A comparison of algorithms for least absolute value state estimation electric power networks
- A parallel formulation of interior point algorithms
- An extension of the potential reduction algorithm for linear complementarity problems with some priority goals
  Linear Algebra and its Applications, Vol. 193
- A Path-Following Algorithm for Linear Programming Using Quadratic and Logarithmic Penalty Functions
  SIAM Journal on Control and Optimization, Vol. 31, No. 6
- A primal—dual infeasible-interior-point algorithm for linear programming
  Mathematical Programming, Vol. 61, No. 1-3
- A Noninterior Continuation Method for Quadratic and Linear Programming
  SIAM Journal on Optimization, Vol. 3, No. 3
- Interior Dual Least 2-Norm Algorithm for Linear Programs
  SIAM Journal on Control and Optimization, Vol. 31, No. 4
- An interior point method for quadratic programs based on conjugate projected gradients
  Computational Optimization and Applications, Vol. 2, No. 1
- Convergence behavior of interior-point algorithms
  Mathematical Programming, Vol. 60, No. 1-3
- Primal-dual interior point approach for computingl 1-solutions andl ?-solutions of overdetermined linear systems
  Journal of Optimization Theory and Applications, Vol. 77, No. 2
- Large-Step Interior Point Algorithms for Linear Complementarity Problems
  SIAM Journal on Optimization, Vol. 3, No. 2
- Theoretical convergence of large-step primal—dual interior point algorithms for linear programming
  Mathematical Programming, Vol. 59, No. 1-3
- Combining phase I and phase II in a potential reduction algorithm for linear programming
  Mathematical Programming, Vol. 59, No. 1-3
- On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise
  Algorithmica, Vol. 9, No. 2
- Solving symmetric indefinite systems in an interior-point method for linear programming
  Mathematical Programming, Vol. 62, No. 1-3
- A primal—dual affine-scaling potential-reduction algorithm for linear programming
  Mathematical Programming, Vol. 62, No. 1-3
- A Superlinearly Convergent Polynomial Primal-Dual Interior-Point Algorithm for Linear Programming
  SIAM Journal on Optimization, Vol. 3, No. 1
- Eine parallele Implementation des Karmarkar—Verfahrens
- Interior-Point Methodology for Linear Programming: Duality, Sensitivity Analysis and Computational Aspects
- On combined phase 1-phase 2 projective methods for linear programming
  Algorithmica, Vol. 9, No. 1
- Near boundary behavior of primal—dual potential reduction algorithms for linear programming
  Mathematical Programming, Vol. 58, No. 1-3
- Continuation and path following
  7 November 2008 | Acta Numerica, Vol. 2
- Numerical experiments with the symmetric affine scaling algorithm on degenerate linear programming problema
  20 March 2007 | Optimization, Vol. 27, No. 1-2
- Optimal Power Flow Application to Composite Power System Reliability Analysis
- Accelerated Interior Point Methods for Least Absolute Value State Estimation in Electric Power Networks
- On the Implementation of a Primal-Dual Interior Point Method
  SIAM Journal on Optimization, Vol. 2, No. 4
- An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
  SIAM Journal on Optimization, Vol. 2, No. 3
- The interior-point method for linear programming
  IEEE Software, Vol. 9, No. 4
- Path-Following Methods for Linear Programming
  SIAM Review, Vol. 34, No. 2
- Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited
  Journal of Optimization Theory and Applications, Vol. 73, No. 2
- On the finite convergence of interior-point algorithms for linear programming
  Mathematical Programming, Vol. 57, No. 1-3
- On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
  SIAM Journal on Optimization, Vol. 2, No. 2
- Modified barrier functions (theory and methods)
  Mathematical Programming, Vol. 54, No. 1-3
- Interior point approach to linear programming: theory, algorithms & parametric analysis
- IMPLEMENTATION OF AN INTERIOR POINT LP ALGORITHM ON A SHARED-MEMORY VECTOR MULTIPROCESSOR
- Implementation of interior-point algorithms for some entropy optimization problems
  4 March 2011 | Optimization Methods and Software, Vol. 1, No. 1
- Preconditioners for Indefinite Systems Arising in Optimization
  SIAM Journal on Matrix Analysis and Applications, Vol. 13, No. 1
- A brief description of ALPO
  Operations Research Letters, Vol. 10, No. 9
- Splitting dense columns in sparse linear systems
  Linear Algebra and its Applications, Vol. 152
- Computational experience with a primal-dual interior point method for linear programming
  Linear Algebra and its Applications, Vol. 152
- On finding a vertex solution using interior point methods
  Linear Algebra and its Applications, Vol. 152
- Optimizing over three-dimensional subspaces in an interior-point method for linear programming
  Linear Algebra and its Applications, Vol. 152
- Global convergence of the affine scaling methods for degenerate linear programming problems
  Mathematical Programming, Vol. 52, No. 1-3
- Comparative analysis of affine scaling algorithms based on simplifying assumptions
  Mathematical Programming, Vol. 52, No. 1-3
- An O(n 3 L) potential reduction algorithm for linear programming
  Mathematical Programming, Vol. 50, No. 1-3
- Power system state estimation with inequality constraints
- Feasibility issues in a primal-dual interior-point method for linear programming
  Mathematical Programming, Vol. 49, No. 1-3

Volume 1, Issue 2

Spring 1989

Pages 61-133

Article Information

Metrics

Information

Published Online:May 01, 1989

Cite as

Kevin A. McShane, Clyde L. Monma, David Shanno, (1989) An Implementation of a Primal-Dual Interior Point Method for Linear Programming. ORSA Journal on Computing 1(2):70-83.

https://doi.org/10.1287/ijoc.1.2.70

Keywords

programming: linear: algorithms

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

An Implementation of a Primal-Dual Interior Point Method for Linear Programming

Abstract

Volume 1, Issue 2

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News