Abstract
The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming.
We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, An implementation of Karmarkar's algorithm for linear programming, Math. Progr. 44 (1989) 297–335. Errata in: Math. Progr. 50 (1991) 415.
I. Adler and D.D.C. Monteiro, A geometric view of parametric linear programming, Algorithmica 8 (1992) 161–176.
I. Adler and D.D.C. Monteiro, Limiting behavior of the affine scaling continuous trajectories for linear programming problems, Math. Progr. 50 (1991) 29–51.
K.M. Anstreicher, Linear programming and the Newton barrier flow, Math. Progr. 41 (1988) 363–373.
M.D. Asic, V.V. Kovacevic-Vujcic and M.D. Radosavljevic-Nikolic, Asymptotic behavior of Karmarkar's method for linear programming, Math. Progr. 46 (1990) 173–190.
M.D. Asic, V.V. Kovacevic-Vujcic and M.D. Radosavljevic-Nikolic, A note on limiting behavior of the projective and the affine rescaling algorithms, Contemp. Math. 114 (1990) 151–157.
M.L. Balinski and A.W. Tucker, Duality theory of linear programs: A constructive approach with applications, SIAM Rev. 11 (1969) 499–581.
E.R. Barnes, A variation on Karmarkar's algorithm for solving linear programming problems, Math. Progr. 36 (1986) 174–182.
E.R. Barnes, Some results concerning convergence of the affine scaling algorithm, Contemp. Math. 114 (1990) 131–139.
E.R. Barnes, S. Chopra and D.L. Jensen, A polynomial-time version of the affine scaling algorithm, Working Paper 88-101, Graduate School of Business and Administration, New York University, NY (1988).
D.A. Bayer and J.C. Lagarias, The nonlinear geometry of linear programming, I. Affine and projective scaling trajectories, II. Legendre transform coordinates, Trans. AMS 314 (1989) 499–581.
R.E. Bixby, J.W. Gregory, I.J. Lustig, R.E. Marsten and D.F. Shanno, Very large-scale linear programming: A case study in combining interior point and simplex methods, Oper. Res. 40 (1992) 885–897.
R.E. Bixby and M.J. Saltzman, Recovering an optimal LP basis from an interior point solution, Technical Report 607, Department of Mathematical Sciences, Clemson University, Clemson, SC (1992).
V. Chandru and B. Kochar, A class of algorithms for linear programming, Research Memorandum 85-14, Department of Industrial Engineering, Purdue University, West Lafayette, IN (1985).
A. Charnes and K.O. Kortanek, An opposite sign algorithm for purification to an extreme point solution, Memorandum No. 129, Office of Naval Research, Northwestern University, Evanston, IL (1963).
G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
I.I. Dikin, Iterative solution of problems of linear and quadratic programming, Sov. Math. Doklady 8 (1967) 674–675.
I.I. Dikin, On the speed of an iterative process, Upravlyaemye Sistemi 12 (1974) 54–60.
I.I. Dikin, Determination of the interior point of a system of linear inequalities, Cybern. Syst. Anal. 1 (1992).
I.I. Dikin, On the convergence of dual variables, Technical Report, Siberian Energy Institute, Irkutsk, USSR (1991).
A.S. El-Bakry, R.A. Tapia and Y. Zhang, A study of indicators for identifying zero variables in interior point methods, Technical Report 91-15, Department of Mathematical Sciences, Rice University, Houston, TX (1991).
T. Gal,Postoptimal Analysis, Parametric Programming and Related Topics (McGraw-Hill, 1979).
T. Gal, Shadow prices and sensitivity analysis in linear programming under degeneracy, state-of-the-art-survey, OR Spektrum 8 (1986) 59–71.
D.M. Gay, Stopping tests that compute optimal solutions for interior-point linear programming algorithms, in:Advances in Numberical Partial Differential Equations and Optimization, Proc. 5th Mexico-United States Workshop, eds. S. Gomez, J.P. Hennart and R.A. Tapia, Proc. in Applied Mathematics, Vol. 47 (1991) pp. 17–42.
D.M. Gay, A variant of Karmarkar's linear programming problems in standard form, Math. Progr. 37 (1987) 81–90. Errata in: Math. Progr. 40 (1988) 111.
P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Progr. 36 (1986) 183–209.
D. Goldfarb and M.J. Todd, Linear programming, in:Optimization, Handbooks in Operations Research and Management Science, Vol. 1, eds. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, Amsterdam, The Netherlands, 1989) pp. 141–170.
A.J. Goldman and A.W. Tucker, Theory of linear programming, in:Linear Inequalities and Related Systems, eds. H.W. Kuhn and A.W. Tucker, Annals of Mathematical Studies 38 (Princeton University Press, Princeton, NJ, 1956).
C.C. Gonzaga, An algorithm for solving linear programming problems inO(n 3 L) operations, in:Progress in Mathematical Programming: Interior Point and Related Methods, ed. N. Megiddo (Springer, New York, 1989) pp. 1–28.
C.C. Gonzaga, Polynomial affine algorithms for linear programming, Math. Progr. 49 (1990) 7–21.
C.C. Gonzaga, Large step path-following methods for linear programming, part I: Barrier function method, SIAM J. Optim. 1 (1991) 268–279.
C.C. Gonzaga, Large step path-following methods for linear programming, part II: Potential reduction method, SIAM J. Optim. 1 (1991) 280–292.
C.C. Gonzaga, Convergence of the large step primal affine scaling algorithm for primal nondegenerate linear programs, Technical Report ES-230/90, Department of Systems Engineering and Computer Sciences, COPPE Federal University of Rio de Janeiro, Rio de Janeiro, Brazil (1990).
C.C. Gonzaga, Search directions for interior linear programming methods, Algorithmica 6 (1991) 153–181.
C.C. Gonzaga, A simple presentation of Karmarkar's algorithm, Technical Report, Department of Systems Engineering and Computer Sciences, COPPE Federal University of Rio de Janeiro, Rio de Janeiro, Brazil (1988).
C.C. Gonzaga, Path following methods for linear programminig, SIAM Rev. 34 (1992) 167–227.
O. Güler, Existence of interior points and interior paths in nonlinear monotone complementarity problems, Working Paper, The College of Business Administration, The University of Iowa, Iowa City, Iowa (1990), to appear in: Math. Oper. Res.
O. Güler and Y. Ye, Convergence behavior of some interior-point algorithms, Working Paper 91-04, The College of Business Administration, The University of Iowa, Iowa City, Iowa (1991), to appear in: Math. Progr.
O. Güler, C. Roos, T. Terlaky and J.-Ph. Vial, Interior point approach to the theory of linear programming, Technical Report No. 1992.3, Département d'Economie Commerciale et Industrielle, Université de Genève, Switzerland (1992).
Hall and R.J. Vanderbei, private communication (1992).
D. den Hertog, Interior point approach to linear, quadratic and convex programming — Algorithms and complexity, Ph.D. Thesis, Faculty of Mathematics and Informatics, TU Delft, Delft, The Netherlands (1992) (Kluwer, Dordrecht, The Netherlands), to be published.
D. den Hertog and C. Roos, Survey of search directions of interior point methods, Math. Progr. 52 (1991) 481–509.
D. den Hertog, C. Roos and T. Terlaky, A potential-reduction variant of Renegar's short-step path-following method for linear programming, Lin. Alg. Appl. 152 (1991) 43–68.
D. den Hertog, C. Roos and J.-Ph. Vial, A complexity reduction for the long-step path-following algorithm for linear programming, SIAM J. Optim. 2 (1992) 71–87.
H. Imai, On the convexity of the multiplicative version of Karmarkar's potential function, Math. Progr. 40 (1988) 29–32.
M. Iri, A proof of the polynomiality of the Iri-Imai method for linear programming, Technical Report, Department of Mathematical Engineering and Information Physics, The University of Tokyo, Tokyo, Japan (1991).
M. Iri and H. Imai, A multiplicative barrier function method for linear programming, Algorithmica 1 (1986) 455–482.
B. Jansen, C. Roos and T. Terlaky, An interior point approach to postoptimal and parametric analysis in linear programming, Technical Report No. 92-21, Faculty of Mathematics and Informatics, TU Delft, Delft, The Netherlands (1992), to appear in Math. Progr.
J.A. Kaliski, A decomposition variant for large scale linear programming, Ph.D. Thesis, Department of Management Sciences, The University of Iowa, Iowa City, Iowa (1992).
N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984) 373–395.
M. Kojima, Determining basic variables of optimal solutions in Karmarkar's new LP algorithm, Algorithmica 1 (1986) 499–515.
M. Kojima, N. Megiddo and S. Mizuno, Theoretical convergence of large-step primal-dual interior point algorithms for linear programs, Math. Progr. 59 (1993) 1–22.
M. Kojima, S. Mizuno and T. Noma, Limiting behavior of trajectories generated by a continuation method for monotone complementarity problems, Math. Oper. Res. 15 (1990) 662–675.
M. Kojima, S. Mizuno and A. Yoshise, A polynomial-time algorithm for a class of linear complementarity problems, Math. Progr. 4 (1989) 41–26.
M. Kojima, N. Megiddo, T. Noma and A. Yoshise,A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science 538 (Springer, New York, 1991).
M. Kojima, S. Mizuno and A. Yoshise, AnO(√nL) iteration potential-reduction algorithm for linear complementarity problems, Math. Progr. 50 (1991) 331–342.
M. Kojima and K. Tone, An efficient implementation of Karmarkar's new LP algorithm, Research Report on Information Sciences B-180, Department of Information Sciences, Tokyo Institute of Technology, Tokyo 152, Japan (1986).
K.O. Kortanek and J. Zhu, New purification algorithms for linear programming, Naval Res. Log. Quarterly 35 (1988) 571–583.
E. Kranich, Interior point methods for mathematical programming: A bibliography, Diskussionsbeitrag Nr. 171, Gesamthochschule FernUniversität Hagen, Germany (1991). Can be obtained by e-mail: netlib@research.att.com.
I.J. Lustig, An implementation of a strongly polynomial time algorithm for basis recovery (using an interior point method), Technical Report (in preparation), School of Engineering and Applied Science, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ (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. Optim. 2 (1990) 435–449.
I.J. Lustig, R.E. Marsten and D.F. Shanno, Interior method vs. simplex method: Beyond netlib, COAL Newsletter 19 (1991) 41–44.
R.E. Marsten, M.J. Saltzman, D.F. Shanno, J.F. Ballintijn and G.S. Pierce, Implementation of a dual affine interior point algorithm for linear programming, ORSA J. Comput. 1 (1991) 287–297.
L. McLinden, An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem, Pacific J. Math. 88 (1980) 101–161.
L. McLinden, The complementarity problem for maximal monotone multifunctions, in:Variational Inequalities and Complementarity Problems, eds. R.W. Cottle, F. Giannessi and J.L. Lions (Wiley, New York, 1980) pp. 251–270.
N. Megiddo, Pathways to the optimal set in linear programming, in:Progress in Mathematical Programming: Interior and Related Methods, ed. N. Megiddo (Springer, New York, 1989) pp. 131–158.
N. Megiddo, On finding primal- and dual-optimal bases, ORSA J. Comput. 3 (1991) 63–65.
N. Megiddo, Switching from a primal-dual Newton algorithm to a primal-dual (interior) simplex-algorithm, Technical Report RJ 6327, IBM Almaden Research Center, San Jose, CA (1988).
N. Megiddo and M. Shub, Boundary behavior of interior point algorithms in linear programming, Math. Oper. Res. 14 (1987) 97–114.
S. Mehrotra, On finding a vertex solution using interior point methods, Lin. Alg. Appl. 152 (1991) 233–253.
S. Mehrotra, Finite termination and superlinear convergence in primal-dual methods, Technical Report 91-13, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991).
S. Mehrotra, Quadratic convergence in a primal-dual method, Technical Report 91-15, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991).
S. Mehrotra and Y. Ye, On finding the optimal face of linear programs, Technical Report 91-10, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL (1991).
S. Mizuno, M.J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Technical Report No. 944, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY (1991), to appear in: Math. Oper. Res.
D.D.C. Monteiro, On the continuous trajectories for a potential reduction algorithm for linear programming, Math. Oper. Res. 17 (1992) 225–253.
D.D.C. Monteiro, Convergence and boundary behavior of the projective scaling trajectories for linear programming, Contemp. Math. 114 (1991) 213–232.
D.D.C. Monteiro and I. Adler, Interior path-following primal-dual algorithms, Part I: Linear programming, Math. Progr. 44 (1989) 27–41.
D.D.C. Monteiro, I. Adler and M.G.C. Resende, A polynomial-time primal-dual affine scaling algorithms for linear and convex quadratic programming and its power series extension, Math. Oper. Res. 15 (1990) 191–214.
J. Renegar, A polynomial-time algorithm, based on Newton's method, for linear programming, Math. Progr. 40 (1988) 59–93.
C. Roos and J.-Ph. Vial, A polynomial method of approximate centers for linear programming, Math. Progr. 54 (1992) 295–305.
A. Schrijver,Theory of Linear and Integer Programming (Wiley, New York, 1986).
D.F. Shanno, private communication (1991).
H.D. Sherali, B.O. Skarpness and B. Kim, An assumption-free analysis of the scaling algorithm for linear programs, with application to theL 1 estimation problem, Naval Res. Log. Quarterly 35 (1988) 473–492.
Gy. Sonnevend, An “analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in:Lecture Notes in Control and Information Sciences, vol. 84, eds. A. Prékopa, J. Szelezsán and B. Straziczki (Springer, New York, 1985) pp. 866–876.
K. Tanabe, Centered Newton method for mathematical programming, in:Proc. 13th IFIP Conf., eds. M. Iri and K. Yajima (Springer, Berlin, 1988) pp. 197–206.
K. Tanabe, Centered Newton method for nonlinear programming (in Japanese), in: Proc. Inst. Statist. Math. 38 (Tokyo, 1990) 119–120.
K. Tanabe and T. Tsuchiya, Global analysis of dynamical systems associated with Karmarkar's method for linear programming, in:Proc. Annual Meeting of the Operations Research Society of Japan, Chigasaki, Japan (1987) pp. 132–133.
R. A. Tapia and Y. Zhang, A fast optimal basis identification technique for interior point linear programming methods, Technical Report 89-1, Department of Mathematical Sciences, Rice University, Houston, TX (1989).
R.A. Tapia and Y. Zhang, An optimal basis identification technique for interior point linear programming algorithms, Lin. Alg. Appl. 152 (1991) 343–363.
T. Terlaky and S. Zhang, A survey of pivot rules for linear programming, Ann. Oper. Res. 46 (1993), this volume.
M.J. Todd, Improved bounds and containing ellipsoids in Karmarkar's linear programming algorithm, Math. Oper. Res. 13 (1988) 650–659.
M.J. Todd and B. Burrell, An extension of Karmarkar's algorithm for linear programming using dual variables, Algorithmica 1 (1986) 409–424.
M.J. Todd and Y. Ye, A centered projective algorithm for linear programming, Math. Oper. Res. 15 (1990) 508–529.
P. Tseng and Z.Q. Luo, On the convergence of the affine-scaling algorithm, Math. Progr. 52 (1992) 301–319.
T. Tsuchiya, Global convergence property of the affine scaling methods for primal degenerate linear programming problems, Math. Oper. Res. 17 (1992) 527–557.
T. Tsuchiya, Global convergence of the affine scaling methods for degenerate linear programming problems, Math. Progr. 52 (1991) 377–404.
T. Tsuchiya, Quadratic convergence of Iri and Imai's algorithm for degenerate linear programming problems, Research Memorandum No. 412, The Institute of Statistical Mathematics, Tokyo, Japan (1991), to appear in: J. Optim. Theory Appl.
T. Tsuchiya, A study on global and local convergence of interior point algorithms for linear programming (in Japanese), Ph.D. Thesis, Faculty of Engineering, The University of Tokyo, Tokyo, Japan (1991).
T. Tsuchiya and M. Muramatsu, Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems, Research Memorandum 423, The Institute of Statistical Mathematics, Tokyo, Japan (1992).
T. Tsuchiya and K. Tanabe, Local convergence properties of new methods in linear programming, J. Oper. Res. Soc. Japan 33 (1990) 22–45.
R.J. Vanderbei and J.C. Lagarias, Dikin's convergence result for the affine-scaling algorithm, Contemp. Math. 114 (1990) 109–119.
R.J. Vanderbei, M.S. Meketon and B.A. Freedman, A modification of Karmarkar's linear programming algorithm, Algorithmica 1 (1986) 395–407.
J.E. Ward and R.E. Wendell, Approaches to sensitivity analysis in linear programming, Ann. Oper. Res. 27 (1990) 3–38.
C. Witzgall, P.T. Boggs and P.D. Domich, On the convergence behavior of trajectories for linear programming, Contemp. Math. 114 (1990) 161–187.
M.H. Wright, Interior point methods for constrained optimization, in:Acta Numerica, ed. A. Iserles (Cambridge University Press, New York, 1992) pp. 341–407.
H. Yamashita, A polynomially and quadratically convergent method for linear programming, Technical Report, Mathematical Systems Inc., Shinjuku, Tokyo, Japan (1986).
Y. Ye, Karmarkar's algorithm and the ellipsoid method, Oper. Res. Lett. 6 (1987) 177–182.
Y. Ye, Recovering optimal basis in Karmarkar's polynomial algorithm for linear programming, Math. Oper. Res. 15 (1990) 564–572.
Y. Ye, AnO(n 3 L) potential reduction algorithm for linear programming, Math. Progr. 50 (1991) 239–258.
Y. Ye, On the finite convergence of interior-point algorithms for linear programming, Math. Progr. Ser. B 57 (1992) 325–335.
Y. Ye, O. Güler, R.A. Tapia and Y. Zhang, A quadratically convergentO(√nL)-iteration algorithm for linear programming, Technical Report 91-26, Department of Mathematical Sciences, Rice University, Houston, TX (1991), to appear in: Math. Progr.
Y. Ye and J. Kaliski, private communication (1991).
Y. Ye and M. Kojima, Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming, Math. Progr. 39 (1987) 305–317.
Y. Ye, R.A. Tapia and Y. Zhang, A superlinearly convergentO(√nL)-iteration algorithm for linear programming, Technical Report 91-22, Department of Mathematical Sciences, Rice University, Houston, TX (1991).
Y. Ye and M.J. Todd, Containing and shrinking ellipsoids in the path-following algorithm, Math. Progr. 47 (1990) 1–10.
Y. Zhang, R. Tapia and J.E. Dennis, On the superlinear and quadratic convergence of primal-dual interior-point linear programming algorithms, SIAM J. Optim. 2 (1990) 304–324.
Author information
Authors and Affiliations
Additional information
Partially supported by a research fund of SHELL.
On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.
Rights and permissions
About this article
Cite this article
Güler, O., den Hertog, D., Roos, C. et al. Degeneracy in interior point methods for linear programming: a survey. Ann Oper Res 46, 107–138 (1993). https://doi.org/10.1007/BF02096259
Issue Date:
DOI: https://doi.org/10.1007/BF02096259