Abstract
In the past 10 years the interior point methods (IPM) for linear programming have gained extraordinary interest as an alternative to the sparse simplex based methods. This has initiated a fruitful competition between the two types of algorithms which has led to very efficient implementations on both sides. The significant difference between interior point and simplex based methods is reflected not only in the theoretical background but also in the practical implementation. In this paper we give an overview of the most important characteristics of advanced implementations of interior point methods. First, we present the infeasible-primal-dual algorithm which is widely considered the most efficient general purpose IPM. Our discussion includes various algorithmic enhancements of the basic algorithm. The only shortcoming of the “traditional” infeasible-primal-dual algorithm is to detect a possible primal or dual infeasibility of the linear program. We discuss how this problem can be solved with the homogeneous and self-dual model.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
I. Adler, N. Karmarkar, M. G. C. Resende, and G. Veiga. Data structures and programming techniques for the implementation of Karmarkar’s algorithm.ORSA J. on Comput., 1 (2): 84–106, 1989.
E. D. Andersen. Finding all linearly dependent rows in large-scale linear programming.Optimization Methods and Software, 6: 219–227, 1995.
E. D. Andersen and K. D. Andersen. Presolving in Linear Programming. Preprint 35, Dept. of Math, and Computer Sci., Odense University, 1993. To appear in Math. Programming.
E. D. Andersen and Y. Ye. Combining interior-point and pivoting algorithms for linear programming. Technical report, Department of Management Sciences, The University of Iowa, 1994. Available via anonymous ftp from ftp://col.biz.uiowa.edu/pub/papers/cross.ps.Z, to appear in Management Science.
K. D. Andersen. A modified Schur complement method for handling dense columns in interior point methods for linear programming. Technical report, Dept. of Math, and Computer Sci., Odense University, 1994. Submitted to ACM Transaction on Mathematical Software.
M. Arioli, J. W. Demmel, and I. S. Duff. Solving sparse linear systems with sparse backward error.SIAM J. Mat. Anal. Appl, 10 (2): 165–190, 1989.
M. Arioli, I. S. Duff, and P. P. M. de Rijk. On the augmented system approach to sparse least-squares problems.Numer. Math., 55: 667–684, 1989.
J. R. Birge, R. M. Freund, and R. Vanderbei. Prior reduced fill-in solving equations in interior point algorithms.Oper. Res. Lett., 11: 195–198, 1992.
R. E. Bixby. Progress in linear programming.ORSA J. on Comput., 6 (1): 15–22, 1994.
R. E. Bixby and M. J. Saltzman. Recovering an optimal basis from an interior point solution.Oper. Res. Lett., 15 (4): 169–178, 1993.
A. Björk. Methods for sparse linear least squares problems. In J. R. Bunch and D. J. Rose, editors,Sparse Matrix Computation, pages 177–201. Academic Press INC., 1976.
A. L. Brearley, G. Mitra, and H. P. Williams. Analysis of mathematical programming problems prior to applying the simplex algorithm.Math. Programming, 15: 54–83, 1975.
J. R. Bunch and B. N. Parlett. Direct methods for solving symmetric indefinit systems of linear equations.SIAM J. Numer. Anal., 8: 639–655, 1971.
T. J. Carpenter, I. J. Lustig, J. M. Mulvey, and D. F. Shanno. Separable quadratic programming via a primal-dual interior point method and its use in a sequential procedure.ORSA J. on Comput., 5: 182–191, 1993.
S. F. Chang and S. T. McCormick. A hierachical algorithm for making sparse matrices sparse.Math. Programming, 56: 1–30, 1992.
I. C. Choi, C. L. Monma, and D. F. Shanno. Further Development of a Primal- Dual Interior Point Method.ORSA J. on Comput., 2 (4): 304–311, 1990.
E. Christiansen and K. O. Kortanek. Computation of the collapse state in limit analysis using the LP primal affine scaling algorithm.J. Comput. Appl. Math 34: 47–63, 1991.
P. D. Domich, P. T. Boggs, J. E. Rogers, and C. Witzgall. Optimizing over three dimensional subspaces in an interior-point method for linear programming.Linear Algebra Appl, 152: 315–342, 1991.
I. S. Duff, A. M. Erisman, and J. K. Reid.Direct methods for sparse matrices. Oxford University Press, New York, 1989.
I. S. Duff, N. I. M. Gould, J. K. Reid, J. A. Scott, and K. Turner. The factorization of sparse symmetric indefinite matrices.IMA J. Numer. Anal., 11: 181–204, 1991.
S. C. Eisenstat, M. C. Gursky, M. H. Schultz, and A. H. Sherman. The Yale sparse matrix package, I. the symmetric code.Internat. J. Numer. Methods Engrg., 18: 1145–1151, 1982.
A. S. El-Bakry, R. A. Tapia, and Y. Zhang. A study of indicators for identifying zero variables in interior-point methods.SIAM Rev, 36 (l): 45–72, 1994.
A. V. Fiacco and G. P. McCormick.Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley and Sons, New York, 1968.
J. J. H. Forrest and D. Goldfarb. Steepest-edge simplex algorithms for linear programming.Math. Programming, 57: 341–374, 1992.
J. J. H. Forrest and J. A. Tomlin.Implementing the simplex method for optimization subroutine libraryIBM Systems J, 31 (1): 11–25, 1992
R. Fourer and S. Mehrotra. Solving symmetric indefinite systems in an interior point method for linear programming.Math. Programming, 62: 15–40, 1993.
K. R. Frisch. The logarithmic potential method of convex programming. Technical report, University Institute of Economics, Oslo, Norway, 1955.
D. M. Gay. Electronic mail distribution of linear programming test problems.COAL Newsletter, 13: 10–12, 1985.
A. George and J. W. -H. Liu.Computing Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs, NJ, 1981.
A. George and J. W. -H. Liu. The evolution of the minimum degree ordering algorithmSIAM Rev, 31: 1–19, 1989.
P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin, and M. H. Wright. On the projected Newton barrier methods for linear programming and an equivalence to Karmarkar’ s projective method.Math. Programming, 36: 183–209, 1986.
J. L. Goffin and J. P. Vial. Cutting planes and column generation techniques with the projective algorithm.J. Optim. Theory Appl., 65: 409–429, 1990.
A. J. Goldman and A. W. Tucker. Polyhedral convex cones. In H. W. Kuhn and A. W. Tucker, editors,Linear Inequalities and related Systems, pages 19–40, Princeton, New Jersey, 1956. Princeton University Press.
A. J. Goldman and A. W. Tucker. Theory of linear programming. In H. W. Kuhn and A. W. Tucker, editors,Linear Inequalities and related Systems, pages 53–97, Princeton, New Jersey, 1956. Princeton University Press.
J. Gondzio. Splitting dense columns of constraint matrix in interior point methods for large scale linear programming.Optimization, 24: 285–297, 1992.
J. Gondzio. Multiple centrality corrections in a primal-dual method for linear programming. Technical Report 1994.20, Logilab, HEC Geneva, Section of Management Studies, University of Geneva, November 1994. Revised May 1995, to appear in Computational Optimization and Applications.
J. Gondzio. Presolve analysis of linear programs prior to applying the interior point method. Technical Report 1994.3, Logilab, HEC Geneva, Section of Management Studies, University of Geneva, 1994. Revised Dec. 1994, to appear in ORSA J. on Comp.
J. Gondzio. HOPDM (version 2.12) - A fast LP solver based on a primal-dual interior point method.European J. Oper. Res., 85: 221–225, 1995.
H. J. Greenberg. The use of the optimal partition in a linear programming solution for postoptimal analysis.Oper. Res. Lett., 15 (4): 179–186, 1994.
O. Güler and Y. Ye. Convergence behaviour of interior-point algorithms.Math. Programming, 60 (2): 215–228, 1993.
A. J. Hoffman, M. Mannos, D. Sokolowsky, and N. Wiegman. Computational experience in solving linear programs.Journal of the Society for Industrial and Applied Mathematics, 1: 17–33, 1953.
P. -F. Hung and Y. Ye. An asymptotical 0$$\[\left({\sqrt n L} \right)$$-iteration path-following linear programming algorithm that uses wide neighborhoods. Technical report, Department of Mathematics, The University of Iowa, March 1994. To appear in SIAM J. on Optimization.
B. Jansen, C. Roos, and T. Terlaky. An interior point approach to postoptimal and parametric analysis in linear programming. InInterior point methods. Eövös Loránd University, Department of Operations Research, H-1088 Budapest, Múzeum krt. 6–8., Hungary, 1992.
B. Jansen, C. Roos, T. Terlaky, and J. P. Vial. Primal-dual target following algorithms for linear programming. Technical Report 93–107, Faculty of Technical Mathematics and Informatics, Technical University Delft, Delft, The Netherlands, 1993.
B. Jansen, T. Terlaky, and C. Roos. The theory of linear programming: Skew symmetric self-dual problems and the central path.Optimization, 29: 225–233, 1994.
N. K. Karmarkar. A polynomial-time algorithm for linear programming.Combinatorica, 4: 373–395, 1984.
N. K. Karmarkar, J. C. Lagarias, L. Slutsman, and P. Wang. Power series variants of Karmarkar-type algorithms.ATjadeT Tech. J., 68: 20–36, 1989.
M. Kojima, N. Megiddo, and S. Mizuno. A primal-dual infeasible-interior-point algorithm for linear programming.Math. Programming, 61: 263–280, 1993.
M. Kojima, S. Mizuno, and A. Yoshise. A primal-dual interior point algorithm for linear proramming. In N. Megiddo, editor,Progress in Mathematical Programming: Interior-Point Algorithms and Related Methods, pages 29–47. Springer Verlag, Berlin, 1989.
J. W. -H. Liu. A generalized envelope method for sparse factorization by rowsACM Trans. Math. Software, 17 (1): 112–129, 1991.
I. J. Lustig, R. E. Marsten, and D. F. Shanno. Computational experience with a primal-dual interior point method for linear programmingLinear Algebra Appl, 20: 191–222, 1991.
I. J. Lustig, R. E. Marsten, and D. F. Shanno. The interaction of algorithms and architectures for interior point methods. In P. M. Pardalos, editor,Advances in optimization and parallel computing, pages 190–205. Elsevier Sciences Publishers B.V., 1992.
I. J. Lustig, R. E. Marsten, and D. F. Shanno. On implementing Mehrotra’ s predictor-corrector interior-point method for linear programming.SIAM J. on Optim., 2 (3): 435–449, 1992.
I. J. Lustig, R. E. Marsten, and D. F. Shanno. Interior point methods for linear programming: Computational state of the art.ORSA J. on Comput., 6 (1): 1–15, 1994.
H. M. Markowitz.The elimination form of the inverse and its application to linear programmingManagement Sci, 3: 255–269, 1957.
I. Maros and Cs. Mészáros. The role of the augmented system in interior point methods. Technical Report TR/06/95, Brunei University, Department of Mathematics and Statistics, London, 1995.
K. A. McShane, C. L. Monma, and D. F. Shanno. An implementation of a primal-dual method for linear programming.ORSA J. on Comput., l(2): 70–83, 1989.
N. Megiddo. Pathways to the optimal set in linear programming. In N. Megiddo, editor,Progress in Mathematical Programming: Interior-Point Algorithms and Related Methods, pages 131–158. Springer Verlag, 1989.
N. Megiddo. On finding primal- and dual- optimal basesORSA J. on Comput 3 (l): 63–65, 1991.
S. Mehrotra. Handling free variables in interior methods. Technical Report 91–06, Department of Industrial Engineering and Managment Sciences, Northwestern University, Evanston, USA., March 1991.
S. Mehrotra. High order methods and their performance. Technical Report 90–16R1, Department of Industrial Engineering and Managment Sciences, Northwestern University, Evanston, USA., 1991.
S. Mehrotra. On the implementation of a primal-dual interior point method.SIAM J. on Optim., 2 (4): 575–601, 1992.
O. du Merle, J. L. Goffin, and J. P. Vial. A short note on the comparative behaviour of Kelley’s cutting plane method and the analytic center cutting plane method. Technical Report 1996. 4, Logilab, HEC Geneva, Section of Management Studies, University of Geneva, January 1996.
Cs. Mészáros. Fast Cholesky factorization for interior point methods of linear programming. Technical report, Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, 1994. To appear in Computers jade Mathematics with Applications.
Cs. Mészáros. The “inexact” minimum local fill-in ordering algorithm. Working paper WP 95–7, Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, 1995.
Cs. Mészáros. The augmented system variant of IPMs in two-stage stochastic linear programming computation. Working paper WP 95–1, Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, 1995.
J.L. NazarethComputer Solution of Linear Programs. Oxford University Press, New York, 1987.
J. von Neumann. On a maximization problem. Technical report,Institute for Advanced Study (Princeton, NJ, USA), 1947.
E. Ng and B. W. Peyton. A supernodal Cholesky factorization algorithm for shared-memory multiprocessors.SIAM J. Sci. Statist. Comput., 14(4):761–769
L. Portugal, F. Bastos, J. Judice, J. Paixõ, and T. Terlaky. An investigation of interior point algorithms for the linear transportation problems. Technical Report 93–100, Faculteit der Technische Wiskunde en Informatica, Technische Universiteit Delft, Nederlands, 1993.
M. G. C. Resende and G. Veiga. An efficient implementation of a network interior point method. Technical report,AT&T Bell Laboratores, Murray Hill, NJ, USA, February 1992.
E. Rothberg and A. Gupta. Efficient Sparse Matrix Factorization on High- Performance Workstations-Exploiting the Memory Hierarchy.ACM Trans. Math. Software, 17 (3): 313–334, 1991.
G. Sonnevend, J. Stoer, and G. Zhao. Subspace methods for solving linear programming problems. Technical report, Institut fur Angewandte Mathematik und Statistic, Universitat Wurzburg, Wurzburg, Germany, January 1994.
G.W. Stewart. Modifying pivot elements in Gaussian elimination.Math. Comp., 28: 537–542, 1974.
G. W. Stewart. On scaled projections and pseudoinversesLinear Algebra Appl, 112: 189–193, 1989.
R. Subramanian, R. P. S. Scheff Jr., J. D. Qillinan, D. S. Wiper, and R. E. Marsten. Coldstart: Fleet assigment at Delta Air Lines.Interfaces, 24(1)
U. H. Suhl. MPOS — Mathematical optimization systemEuropean J. Oper. Res, 72 (2): 312–322, 1994.
U. H. Suhl and L. M. Suhl. Computing sparse LU factorizations for large-scale linear programming basesORSA J. on Comput, 2 (4): 325–335, 1990.
W. F.Tinney and J. W. Walker.Direct solution of sparse network equations by optimally ordered triangular factorization. InProceedings of IEEE,volume 55, pages 1801–1809. 1967.
A. W. Tucker. Dual systems of homogeneous linear relations. InLinear inequalities and related systems, pages 3–18. Princeton University Press, Princeton, NJ, 1956.
K. Turner.Computing projections for Karmarkar algorithmLinear Algebra Appl, 152: 141–154, 1991.
R. J. Vanderbei. Splitting dense columns in sparse linear systemsLinear Algebra Appl, 152: 107–117, 1991.
R. J. Vanderbei and T. J. Carpenter. Symmetric indefinite systems for interior point methodsMath. Programming, 58: 1–32, 1993.
X. Xu. An O$$\[\left({\sqrt n L} \right)$$-iteration large-step infeasible path-following algorithm for linear programming. Technical report, College of Business Administration, The University of Iowa, Iowa City, IA 52242, August 1994.
X. Xu. On the implementation of a homogeneous and self-dual linear programming algorithm. Technical report, 1994. Manuscript.
X. Xu, P.-F. Hung, and Y. Ye. A simplified homogeneous and self-dual linear programming algorithm and its implementation. Technical report, Department of Management Sciences, The University of Iowa, 1993.
X. Xu and Y. Ye. A generalized homogeneous and self-dual algorithm for linear programmingOper. Res. Lett., 17: 181–190, 1995.
M. Yannakakis. Computing the minimum fill-in is NP-completeSIAM J. Algebraic Discrete Methods, pages 77–79, 1981.
Y. Ye. On the finite convergence of interior-point algorithms for linear programmingMath. Programming, 57: 325–335, 1992.
Y. Ye, M. J. Todd, and S. Mizuno. An O$$\[\left({\sqrt n L} \right)$$- iteration homogeneous and self-dual linear programming algorithm.Math. Oper. Res., 19: 53–67, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Kluwer Academic Publishers
About this chapter
Cite this chapter
Anderson, E.D., Gondzio, J., Mészáros, C., Xu, X. (1996). Implementation of Interior-Point Methods for Large Scale Linear Programs. In: Terlaky, T. (eds) Interior Point Methods of Mathematical Programming. Applied Optimization, vol 5. Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-3449-1_6
Download citation
DOI: https://doi.org/10.1007/978-1-4613-3449-1_6
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4613-3451-4
Online ISBN: 978-1-4613-3449-1
eBook Packages: Springer Book Archive