Multiple centrality corrections in a primal-dual method for linear programming. (English) Zbl 0860.90084
Summary: A modification of the (infeasible) primal-dual interior point method is developed. The method uses multiple corrections to improve the centrality of the current iterate. The maximum number of corrections the algorithm is encouraged to make depends on the ratio of the efforts to solve and to factorize the KKT systems. For any LP problem, this ratio is determined right after preprocessing the KKT system and prior to the optimization process. The harder the factorization, the more advantageous the higher-order corrections might prove to be.
The computational performance of the method is studied on more difficult Netlib problems as well as on tougher and larger real-life LP models arising from applications. The use of multiple centrality corrections gives on the average a 25% to 40% reduction in the number of iterations compared with the widely used second-order predictor-corrector method. This translates into 20% to 30% savings in CPU time.
The computational performance of the method is studied on more difficult Netlib problems as well as on tougher and larger real-life LP models arising from applications. The use of multiple centrality corrections gives on the average a 25% to 40% reduction in the number of iterations compared with the widely used second-order predictor-corrector method. This translates into 20% to 30% savings in CPU time.
MSC:
| 90C05 | Linear programming |
References:
| [1] | A. Altman and J. Gondzio, ”An efficient implementation of a higher order primal-dual interior point method for large sparse linear programs,” Archives of Control Sciences, vol. 2, nos. 1/2, pp. 23–40, 1993. · Zbl 0799.90083 |
| [2] | R.E. Bixby, ”Progress in linear programming,” ORSA Journal on Computing, vol. 6, pp. 15–22, 1994. · Zbl 0798.90101 · doi:10.1287/ijoc.6.1.15 |
| [3] | T.J. Carpenter, I.J. Lustig, J.M. Mulvey, and D.F. Shanno, ”Higher order predictor-corrector interior point methods with application to quadratic programming,” SIAM Journal on Optimization, vol. 3, pp. 696–725, 1993. · Zbl 0794.90043 · doi:10.1137/0803036 |
| [4] | P.D. Domich, P.T. Boggs, J.E. Rogers, and Ch. Witzgall, ”Optimizing over three-dimensional subspaces in an interior-point method for linear programming,” Linear Algebra and its Applications, vol. 152, pp. 315–342, 1991. · Zbl 0731.65051 · doi:10.1016/0024-3795(91)90280-A |
| [5] | I.S. Duff, A.M. Erisman, and J.K. Reid, Direct Methods for Sparse Matrices, Oxford University Press: New York, 1989. · Zbl 0666.65024 |
| [6] | D.M. Gay, ”Electronic mail distribution of linear programming test problems,” Mathematical Programming Society COAL Newsletter, vol. 13, pp. 10–12, 1985. |
| [7] | J. Gondzio, ”Presolve analysis of linear programs prior to applying an interior point method,” Technical Report 1994.3, Department of Management Studies, University of Geneva, Switzerland, 1994, revised in 1994, ORSA Journal on Computing (to appear). · Zbl 0890.90143 |
| [8] | J. Gondzio and T. Terlaky, ”A computational view of interior point methods for linear programming,” in Advances in Linear and Integer Programming, J. Beasley (Ed.) Oxford University Press: Oxford, 1995 (to appear). · Zbl 1010.90524 |
| [9] | C.C. Gonzaga, ”Path-following methods for linear programming,” SIAM Review, vol. 34, pp. 167–224, 1992. · Zbl 0763.90063 · doi:10.1137/1034048 |
| [10] | C.C. Gonzaga, Private communication, 1994. |
| [11] | P.-F. Hung and Y. Ye, ”An asymptotical 155–1 path-following linear programming algorithm that uses long steps,” Technical Report, Department of Mathematics, University of Iowa, Iowa City, USA, March 1994, SIAM Journal on Optimization (to appear). |
| [12] | 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, to appear in a special issue of Annals of Operation Research, K. Anstreicher and R. Freund (Eds.). |
| [13] | N.K. Karmarkar, J.C. Lagarias, L. Slutsman, and P. Wang, ”Power series variants of Karmarkar-type algorithms,” AT&T Technical Journal, vol. 68, pp. 20–36, 1989. · Zbl 0682.90060 |
| [14] | M. Kojima, S. Mizuno, and A. Yoshise, ”A primal-dual interior point algorithm for linear programming,” in Progress in Mathematical Programming: Interior Point and Related Methods, N. Megiddo (Ed.), Springer-Verlag: New York, 1989, pp. 29–48. · Zbl 0708.90049 |
| [15] | R. Loulou, ”Cost minimization of Quebec’s and Ontario’s energy system in the long term,” Technical Report, GERAD, McGill University, Montreal, Canada, 1994. |
| [16] | I.J. Lustig, R.E. Marsten, and D.F. Shanno, ”On implementing Mehrotra’s predictor-corrector interior point method for linear programming,” SIAM Journal on Optimization, vol. 2, pp. 435–449, 1992. · Zbl 0771.90066 · doi:10.1137/0802022 |
| [17] | I.J. Lustig, R.E. Marsten, and D.F. Shanno, ”Interior point methods for linear programming: Computational State of the Art,” ORSA Journal on Computing, vol. 6, pp. 1–14, 1994. · Zbl 0798.90100 · doi:10.1287/ijoc.6.1.1 |
| [18] | N. Megiddo, ”Pathways to the optimal set in linear programming,” in Progress in Mathematical Programming: Interior Point and Related Methods, N. Megiddo (Ed.), Springer-Verlag: New York, 1989, pp. 131–158. · Zbl 0687.90056 |
| [19] | S. Mehrotra, ”Higher order methods and their performance,” Technical Report 90–16R1, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, USA, 1991. · Zbl 0737.65050 |
| [20] | S. Mehrotra, ”On the implementation of a primal-dual interior point method,” SIAM Journal on Optimization, vol. 2, pp. 575–601, 1992. · Zbl 0773.90047 · doi:10.1137/0802028 |
| [21] | S. Messner, ”User’s guide for the matrix generator of MESSAGE II,” IIASA WP-84–71a, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1984. |
| [22] | N. Nakicenovic, A. Gruebler, A. Inaba, S. Messner, S. Nilsson, Y. Nishimura, H.-H. Rogner, A. Schaefer, L. Schrattenholzer, M. Strubegger, J. Swisher, D. Victor, and D. Wilson, ”Long-term strategies for mitigating global warming,” Energy–The International Journal (special issue), vol. 18, no. 5, pp. 409–601, 1993. |
| [23] | P.A. Okken et al., ”Energy systems and CO2 Constraints,” Technical Report ECN-C-93–014, Energieonderzoek Centrum Nederland, Petten, 1994. |
| [24] | P. Schaumann et al., ”Integrierte Gesamtstrategien der Minderung energiebedingter Treibhausgasemissionen (2005/2020),” Studie im Auftrag der Enquete-Kommission ”Schutz der Erdatmosphaere” des 12, Deutschen Budnestages, Stuttgart, 1994. |
| [25] | G. Sonnevend, J. Stoer, and G. Zhao, ”Subspace methods for solving linear programming problems,” Technical Report, Institut fur Angewandte Mathematik und Statistik, Universitat Wurzburg, Wurzburg, Germany, 1994. · Zbl 0924.90109 |
| [26] | M. Strubegger, ”User’s guide for the post-processor of MESSAGE II,” IIASA WP-84–71b, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1984. |
| [27] | J.-P. Waaub and R. Loulou, ”CO2 control with cooperation in Quebec and Ontario: A MARKAL perspective,” Energy Studies Review, vol. 4, no. 3, pp. 278–296, 1992. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
