×

Advances in design and implementation of optimization software. (English) Zbl 1001.90004

Summary: Developing optimization software that is capable of solving large and complex real-life problems is a huge effort. It is based on a deep knowledge of four areas: theory of optimization algorithms, relevant results of computer science, principles of software engineering, and the state-of-the-art in computer technology. The paper highlights the diverse requirements of optimization software and discusses the ingredients needed to fulfil those requirements. In addition to reviewing the current hardware/software environment it hints al how recent hardware developments can influence future optimization software. After a survey of computationally successful techniques for continuous optimization, it also outlines the perspective offered by parallel computing, and stresses the importance of optimization modeling systems. Being a survey paper, it includes many references to both give due credit to results in the field of optimization software, and to help readers obtain more detailed information on issues of interest.

MSC:

90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C06 Large-scale problems in mathematical programming
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aberth, O.; Schaefer, M. J., Precise computation using range arithmetic, via C++, ACM Transactions on Mathematical Software, 18, 4, 481-491 (1992) · Zbl 0892.65028
[2] Abrash, M., Michael Abrash’s Graphics Programming Black Book (1997), The Coriolis Group Inc
[3] Adler, I.; Karmarkar, N.; Resende, M. G.C.; Veiga, G., Data structures and programming techniques for the implementation of Karmarkar’s algorithm, ORSA Journal in Computing, 1, 84-106 (1989) · Zbl 0752.90043
[4] AMD Athlon Processor Technical Brief, Publication #22054 Rev:D, December 1999; AMD Athlon Processor Technical Brief, Publication #22054 Rev:D, December 1999
[5] Andersen, E. D.; Gondzio, J.; Mészáros, Cs.; Xu, X., Implementation of interior point methods for large scale linear programs, (Terlaky, T., Interior Point Methods of Mathematical Programming. Interior Point Methods of Mathematical Programming, Applied Optimization, vol. 5 (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 189-252, (Chapter 6) · Zbl 0874.90127
[6] Anderson, E. D.; Anderson, K. D., Presolving in linear programming, Mathematical Programming, 71, 2, 221-245 (1995) · Zbl 0846.90068
[7] Benichou, M.; Gautier, J. M.; Hentges, G.; Ribiere, G., The efficient solution of large-scale linear programming problems, Mathematical Programming, 13, 280-322 (1977) · Zbl 0384.90084
[8] Binstock, A.; Rex, J., Practical Algorithms for Programmers (1995), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA · Zbl 0828.68003
[9] Bixby, R. E., Implementing the simplex method: The initial basis, ORSA Journal on Computing, 4, 3, 267-284 (1992) · Zbl 0759.90063
[10] Bixby, R. E.; Ceria, S.; McZeal, C. M.; Savelsbergh, M. W.P., An updated mixed integer programming library: MIPLIB 3.0, Optima, 54, 12-15 (1998)
[11] Bland, R. G., New finite pivot rule for the simplex method, Mathematics of Operations Research, 2, 103-107 (1977) · Zbl 0408.90050
[12] Bongartz, I.; Conn, A. R.; Gould, N. I.M.; Toint, Ph. L., CUTE: Constrained and unconstrained testing environment, ACM Transactions on Mathematical Software, 21, 1, 123-160 (1995) · Zbl 0886.65058
[13] Brearley, A. L.; Mitra, G.; Williams, H. P., Analysis of mathematical programming problems prior to applying the simplex method, Mathematical Programming, 8, 54-83 (1975) · Zbl 0317.90037
[14] Brooke, A.; Kendrick, D.; Meeraus, A.; Raman, R., GAMS (1998), GAMS Development Corp
[15] Bulka, D.; Mayhew, D., Efficient C++: Performance Programming Techniques (2000), Addison-Wesley/Longman Inc: Addison-Wesley/Longman Inc Reading, MA/New York
[16] Cosnard, M.; Trystram, D., Parallel Algorithms and Architectures (1995), International Thompson Computer Press
[17] Culler, D. E.; Singh, J. P.; Gupta, A., Parallel Computer Architecture: A Hardware/Software Approach (1999), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Los Altos, CA
[18] Curtis, A. R.; Reid, J. K., On the automatic scaling of matrices for Gaussian elimination, Journal of the Institute of Mathematics and its Applications, 10, 118-124 (1972) · Zbl 0249.65026
[19] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton · Zbl 0108.33103
[20] Dantzig, G. B., Impact of linear programming on computer development, OR/MS Today, August, 12-17 (1988)
[21] Dongarra, J. J.; Walker, D. W., Software libraries for linear algebra computations on high performance computers, SIAM Review, 37, 2, 151-180 (1995) · Zbl 0874.65014
[22] Duff, I. S.; Erisman, A. M.; Reid, J. K., Direct Methods for Sparse Matrices (1986), Oxford Science Publications, Clarendon Press: Oxford Science Publications, Clarendon Press Oxford · Zbl 0604.65011
[23] Forrest, J. J.; Tomlin, J. A., Vector processing in simplex and interior point methods, Annals of Operations Research, 22, 71-100 (1990) · Zbl 0714.90064
[24] Forrest, J. J.H.; Goldfarb, D., Steepest edge simplex algorithms for linear programming, Mathematical Programming, 57, 3, 341-374 (1992) · Zbl 0787.90047
[25] Forrest, J. J.H.; Tomlin, J. A., Implementing interior point linear programming methods in the optimization subroutine library, IBM Systems Journal, 31, 26-38 (1992) · Zbl 0814.90076
[26] Forrest, J. J.H.; Tomlin, J. A., Implementing the simplex method in the optimization subroutine library, IBM Systems Journal, 31, 11-25 (1992) · Zbl 0814.90075
[27] Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL: A Modeling Language for Mathematical Programming (1993), Duxbury Press
[28] Gay, D. M., Electronic mail distribution of linear programming test problems, COAL Newsletter, 13, 10-12 (1985)
[29] Gill, P. E.; Murray, W.; Saunders, M. A.; Wright, M. H., A practical anti-cycling procedure for linearly constrained optimization, Mathematical Programming, 45, 437-474 (1989) · Zbl 0688.90038
[30] Goldfarb, D.; Reid, J., A practicable steepest-edge simplex algorithm, Mathematical Programming, 12, 361-371 (1977) · Zbl 0443.90058
[31] Gondzio, J., Presolve analysis of linear programs prior to applying an interior point method, INFORMS Journal on Computing, 9, 1, 73-91 (1997) · Zbl 0890.90143
[32] Gondzio, J.; Terlaky, T., A computational view of interior point methods, (Advances in Linear and Integer Programming. Advances in Linear and Integer Programming, Oxford Lecture Series in Mathematics and its Applications (1996), Clarendon Press: Clarendon Press Oxford), 103-144, (Chapter 3) · Zbl 1010.90524
[33] Gould, N. I.M.; Reid, J. K., New crash procedures for large systems of linear constraints, Mathematical Programming, 45, 475-501 (1989) · Zbl 0692.90089
[34] H.J. Greenberg, Pivot selection tactics, in: [36], pp. 143-174; H.J. Greenberg, Pivot selection tactics, in: [36], pp. 143-174
[35] H.J. Greenberg, A tutorial on matricial packing, in: [36], pp. 109-142; H.J. Greenberg, A tutorial on matricial packing, in: [36], pp. 109-142
[36] (Greenberg, H. J., Design and Implementation of Optimization Software (1978), Sijtho and Nordhoff: Sijtho and Nordhoff Alphen a/d Rijn)
[37] Greenberg, H. J., A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User’s Guide for ANALYZE (1993), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 0819.68025
[38] Harris, P. M.J., Pivot selection method of the Devex LP code, Mathematical Programming, 5, 1-28 (1973) · Zbl 0261.90031
[39] Hayes, J. P., Computer Architecture and Organization (1998), The McGraw-Hill Companies: The McGraw-Hill Companies New York · Zbl 0384.68001
[40] Hennessy, J. L.; Patterson, D. A., Computer Architecture: A Quantitative Approach (1996), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Los Altos, CA · Zbl 0752.68014
[41] Kalan, J. E., Aspects of large-scale in-core linear programming, (Proceedings of the 1971 Annual Conference of the ACM (1971), ACM: ACM New York), 304-313
[42] Kernighan, B. W.; Ritchie, D. M., The C Programming Language. The C Programming Language, Prentice-Hall Software Series (1988), Prentice-Hall PTR: Prentice-Hall PTR Englewood Cliffs, NJ
[43] A. Klaiber, The Technology Behind Crusoe Processors, Transmeta Corporation, January 2000; A. Klaiber, The Technology Behind Crusoe Processors, Transmeta Corporation, January 2000
[44] U. Kulisch, The fifth floating-point operation for top-performance computers, Technical report, Institut für Angewandte Mathematik, Universität Karlsruhe, 1997; U. Kulisch, The fifth floating-point operation for top-performance computers, Technical report, Institut für Angewandte Mathematik, Universität Karlsruhe, 1997
[45] Lustig, I. J.; Rothberg, E., Gigaflops in linear programming, Operations Research Letters, 18, 4, 157-165 (1996) · Zbl 0855.90083
[46] Lustig, I. J.; Marsten, R. E.; Shanno, D. F., Computational experience with a primal dual interior point method for linear programming, Linear Algebra and its Applications, 152, 191-222 (1991) · Zbl 0731.65049
[47] Lustig, I. J.; Marsten, R. E.; Shanno, D. F., On implementing Mehrotra’s predictor-corrector interior point method for linear programming, SIAM Journal on Optimization, 2, 435-449 (1992) · Zbl 0771.90066
[48] Lustig, I. J.; Marsten, R. E.; Shanno, D. F., Interior point methods for linear programming: Computational state of the art, ORSA Journal on Computing, 6, 1, 1-14 (1994) · Zbl 0798.90100
[49] Karels, M. J.; McCusick, M. K.; Bostic, K.; Quarterman, J. S., The Design and Implementation of the 4.4BSD Operating System (1996), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA
[50] Maros, I., A general Phase-I method in linear programming, European Journal of Operational Research, 23, 64-77 (1986) · Zbl 0583.90060
[51] Maros, I., A multicriteria decision problem within the simplex method, (Mitra, G., Mathematical Models for Decision Support (1988), Springer Verlag: Springer Verlag Berlin), 263-272
[52] I. Maros, A structure exploiting pricing procedure for network linear programming, Research Report 18-91, RUTCOR, Rutgers University, NJ, USA, May 1991, 15 p; I. Maros, A structure exploiting pricing procedure for network linear programming, Research Report 18-91, RUTCOR, Rutgers University, NJ, USA, May 1991, 15 p
[53] Maros, I., A piecewise linear dual procedure in mixed integer programming, (Schaible, R.; Giannesi, F.; Komlosi, S., New Trends in Mathematical Programming (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 159-170 · Zbl 0909.90217
[54] Maros, I.; Mészáros, Cs., A numerically exact implementation of the simplex method, Annals of Operations Research, 58, 3-17 (1995) · Zbl 0836.90118
[55] Maros, I.; Mészáros, C.s., A repository of convex quadratic programming problems, Optimization Methods and Software, 11&12, December, 671-681 (1999) · Zbl 0973.90520
[56] Maros, I.; Mitra, G., Investigating the sparse simplex algorithm on a distributed memory multiprocessor, Parallel Computing, 26, 151-170 (2000) · Zbl 1046.68981
[57] Maros, I.; Mitra, G., Strategies for creating advanced bases for large-scale linear programming problems, INFORMS Journal on Computing, 10, 2, 248-260 (1998) · Zbl 1034.90515
[58] Marsten, R. E., XMP: A structured library of subroutines for experimental mathematical programming, ACM Transactions on Mathematical Software, 7, 487-497 (1981)
[59] MPL Modeling system, Maximal Software. Available from http://www.maximal-usa.com/mpl/; MPL Modeling system, Maximal Software. Available from http://www.maximal-usa.com/mpl/
[60] McShane, K. A.; Monma, C. L.; Shanno, D. F., An implementation of a primal-dual interior point method for linear programming, ORSA Journal on Computing, 1, 70-89 (1989) · Zbl 0752.90047
[61] Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM Journal on Optimization, 2, 575-601 (1992) · Zbl 0773.90047
[62] H.D. Mittelmann, P. Spellucci, Decision tree for optimization software. Available from <http://plato.la.asu.edu/guide.html>; H.D. Mittelmann, P. Spellucci, Decision tree for optimization software. Available from <http://plato.la.asu.edu/guide.html>
[63] B.A. Murtagh, M.A. Saunders, MINOS 5. 1 User’s Guide, Technical Report SOL 83-20R, Stanford University, 1987; B.A. Murtagh, M.A. Saunders, MINOS 5. 1 User’s Guide, Technical Report SOL 83-20R, Stanford University, 1987
[64] Orchard-Hays, W., Advanced Linear-Programming Computing Techniques (1968), McGraw-Hill: McGraw-Hill New York
[65] Pacheco, P. S., Parallel Programming With MPI (1997), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Los Altos, CA · Zbl 0877.68013
[66] AIMMS, Paragon decision technology. Available from <http://www.aimms.com/index.html>; AIMMS, Paragon decision technology. Available from <http://www.aimms.com/index.html>
[67] Patterson, D. A.; Hennessy, J. L., Computer Organization and Design: The Hardware-Software Interface (1998), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers Los Altos, CA
[68] Ris, F.; Barkmeyer, C.; Farkas, P., When floating-point addition isn’t commutative, SIGNUM Newsletter, 28, 1, 8-13 (1993)
[69] Robertazzi, T. G.; Schwartz, S. C., Best ordering for floating-point addition, ACM Transactions on Mathematical Software, 14, 1, 101-110 (1988) · Zbl 0647.65033
[70] Roos, C.; Terlaky, T.; Vial, J.-Ph., Theory and Algorithms for Linear Optimization. Theory and Algorithms for Linear Optimization, Discrete Mathematics and Optimization (1997), Wiley: Wiley New York
[71] Rothberg, E.; Gupta, A., Efficient sparse matrix factorization on high performance workstations exploiting the memory hierarchy, ACM Transactions on Mathematical Software, 17, 3, 313-334 (1991) · Zbl 0900.65066
[72] Savelsbergh, M. W.P., Preprocessing and probing for mixed integer programming problems, ORSA Journal on Computing, 6, 445-454 (1994) · Zbl 0814.90093
[73] Smith, B. F., The transition of numerical software: From nuts-and-bolts to abstraction, SIGNUM Newsletter, 33, 1, 7-15 (1998)
[74] Snir, M.; Otto, S.; Huss-Lederman, S.; Walker, D.; Dongarra, J., MPI - The Complete Reference, Volume 1, The MPI Core. MPI - The Complete Reference, Volume 1, The MPI Core, Scientific and Engineering Computation Series (1999), The MIT Press: The MIT Press Cambridge, MA
[75] Solanki, R. S.; Gorti, J. K., Implementation of an integer optimization platform using object-oriented programming, Computers and Operations Research, 24, 6, 549-557 (1997) · Zbl 0882.90101
[76] Suhl, U. H.; Suhl, L. M., Computing sparse LU factorizations for large-scale linear programming bases, ORSA Journal on Computing, 2, 4, 325-335 (1990) · Zbl 0755.90059
[77] Swietanowski, A., A new steepest edge approximation for the simplex method for linear programming, Computational Optimization and Applications, 10, 3, 271-281 (1998) · Zbl 0912.90220
[78] Tabak, D., Advanced Microprocessors (1995), McGraw-Hill: McGraw-Hill New York
[79] Toledo, S., Improving the memory-system performance of sparse-matrix vector multiplication, IBM Journal of Research and Development, 41, 6, 711-725 (1997)
[80] Trippi, R. R.; Turban, E., Parallel processing and OR/MS, Computers and Operations Research, 18, 2, 199-210 (1991)
[81] Van Henteryck, P., The OPL Optimization Programming Language (1999), MIT Press: MIT Press Cambridge, MA
[82] Wallis, P. J.L., Improving Floating-Point Programming (1990), John Wiley & Sons Ltd: John Wiley & Sons Ltd New York
[83] Wolfe, Ph., The composite simplex algorithm, SIAM Review, 7, 1, 42-54 (1965) · Zbl 0133.42703
[84] Wright, S. J., Primal-Dual Interior Point Methods (1996), SIAM: SIAM Philadelphia, PA
[85] Yamashita, H.; Yabe, H., Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization, Mathematical Programming, 75, 377-397 (1996) · Zbl 0874.90175
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.