Interior Point Methods for Linear Programming: Just Call Newton, Lagrange, and Fiacco and McCormick!
INFORMS Journal on Applied AnalyticsPublished 1 August 1990
Roy E. Marsten, Radhika Subramanian, Matthew J. Saltzman, Irvin J. Lustig, David F. Shanno
Citations77
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Interior point methods are the right way to solve large linear programs and are much easier to derive, motivate, and understand than they at first appeared.
Abstract
Interior point methods are the right way to solve large linear programs. They are also much easier to derive, motivate, and understand than they at first appeared. Lagrange told us how to convert a minimization with equality constraints into an unconstrained minimization. Fiacco and McCormick told us how to convert a minimization with inequality constraints into a sequence of unconstrained minimizations. Newton told us how to solve unconstrained minimizations. Linear programs are minimizations with equations and inequalities. Voila!
Keywords
Computer ScienceMathematics
COMBINATORICAA new polynomial-time algorithm for linear programming
4,840 Citations1984Narendra Karmarkar
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Nonlinear programming: sequential unconstrained minimization techniques
2,272 Citations1968Anthony V. Fiacco, Garth P. McCormick
Direct Methods for Sparse Matrices
1,612 Citations2017Iain Duff, A. M. Erisman +1 more
This book aims to be suitable also for a student course, probably at MSc level, and the subject is intensely practical and this book is written with practicalities ever in mind.
Pathways to the Optimal Set in Linear Programming
588 Citations1989Nimrod Megiddo
A Primal-Dual Interior Point Algorithm for Linear Programming
489 Citations1989Masakazu Kojima, Shinji Mizuno +1 more
Mathematical ProgrammingInterior path following primal-dual algorithms. part I: Linear programming
488 Citations1989Renato D. C. Monteiro, Ilan Adler
A primal-dual interior point algorithm for linear programming problems which requires a total of O(n L) number of iterations to find the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem.
Mathematical ProgrammingOn projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
443 Citations1986Philip E. Gill, Walter Murray +3 more
This work reviews classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints and shows a “projected Newton barrier” method to be equivalent to Karmarkar's projective method for a particular choice of the barrier parameter.
Mathematical ProgrammingAn implementation of Karmarkar's algorithm for linear programming
422 Citations1989Ilan Adler, Maurício G. C. Resende +2 more
Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested and compares favorably with the simplex codeMinos 4.0.
ACM Transactions on Mathematical SoftwareModification of the minimum-degree algorithm by multiple elimination
352 Citations1985Joseph W. H. Liu
Experimental results indicate that the modified version of the minimum-degree algorithm retains the fill-reducing property of (and is often better than) the original ordering algorithm and yet requires less computer time.
Linear Algebra and its ApplicationsComputational experience with a primal-dual interior point method for linear programming
311 Citations1991Irvin J. Lustig, Roy E. Marsten +1 more
It is shown that, in a certain way, Lustig's method for obtaining feasibility is equivalent to Newton's method, which demonstrates that the method is in some sense the natural way to reduce infeasibility.
Operations ResearchThe Created Response Surface Technique for Optimizing Nonlinear, Restrained Systems
309 Citations1961Charles W. Carroll
Operations ResearchAn Empirical Evaluation of the KORBX® Algorithms for Military Airlift Applications
123 Citations1990William J. Carolan, James E. Hill +3 more
KORBX® a registered trademark of ATT and some pure network problems were solved using NETFLO, MPSX, and XMP.
INFORMS Journal on ComputingData Structures and Programming Techniques for the Implementation of Karmarkar's Algorithm
95 Citations1989Ilan Adler, Narendra Karmarkar +2 more
This paper describes data structures and programming techniques used in an implementation of Karmarkar's algorithm for linear programming, which relies on a direct factorization scheme, with an extensive symbolic factorization step performed in a preparatory stage of the linear programming algorithm.
INFORMS Journal on Applied AnalyticsKarmarkar’s Linear Programming Algorithm
51 Citations1986John Hooker
The new projective scaling algorithm for linear programming has caused quite a stir in the press, mainly because of reports that it is 50 times faster than the simplex method on large problems and has a polynomial bound on worst-case running time that is better than the ellipsoid algorithm's.
INFORMS Journal on ComputingImplementation of a Dual Affine Interior Point Algorithm for Linear Programming
50 Citations1989Roy E. Marsten, Matthew J. Saltzman +3 more
The dual affine interior point method is extended to handle variables with simple upper bounds as well as free variables and a variant of the big- M artificial variable method to attain feasibility is derived.