Implementation aids for optimization algorithms that solve sequences of linear programs

ABSTRACT

We describe a collection of modules designed to facilitate the implementation of optimization (LP) algorithms that must solve one or more linear programs in a suitably coordinated sequence. Our collection also provides a basis for discussing some of the broader issues of LP software development and serves as a tutorial on state-of-the-art techniques that may be used to implement LP algorithms in a practical manner.

REFERENCES

• 1: BENICHOU, M., GAUTHIER, J. M., HENTGES, G., AND RIBIERE, G. The efficient solution of large-scale linear programming problems--Sorae algorithmic techniques and computational results. Math. Program. 13 (1977), 280-322.
• 2: Richard P. Brent, Reducing the retrieval time of scatter storage techniques, Communications of the ACM, v.16 n.2, p.105-109, Feb. 1973 [doi>10.1145/361952.361964]
• 3: A. K. Cline, Two Subroutine Packages for the Efficient Updating of Matrix Factorizations, University of Texas at Austin, Austin, TX, 1977
• 4: COHEN, S., AND PIEPER, S.C. The Speakeasy-3 reference manual, level lambda. Rep. ANL- 8000, Argonne National Laboratory, Argonne, II}., 1976.
• 5: DANTZIG, G.B. Linear Progromming and Extensions. Princeton Univ. Press, Princeton, N. J., 1963.
• 6: DANTZIG, G. B., AND WOLFE, P. The decompo;~ition principle for linear programming. Econometrica 29 (1961), 767-778.
• 7: Stanley C. Eisenstat , Thomas L. Magnanti , Steven F. Maier , Michael B. McGrath , Vincent J. Nicholson , Christiane Riedl , George B. Dantzig, MPL, Mathematical Programming Language: specification manual for Committee review, Stanford University, Stanford, CA, 1970
• 8: Leonard Gilman , Allen J. Rose, APL: An Interactive Approach, John Wiley & Sons, Inc., New York, NY, 1976
• 9: GREENBERG, H. A tutorial on matricial packing. In Design and Implementation of Optimization Software, H. Greenberg, Ed. Sijthoff and Noordhoff, Leyden, The Netherlands, 1978, pp. 109-142.
• 10: GREENBERG, H. Pivot selection tactics. In Design and Implementation of Optimization Software, H. Greenberg, Ed. Sijthoff and Noordhoff, Leyden, The Netherlands, 1978, pp. 143-174.
• 11: HARRIS, P. M.J. Pivot selection methods in the Devex LP code. Math. Program. Stud. 4 (1975), 30-57.
• 12: Ho, J. K., AND MANSE, A.S. Nested decomposition for dynamic models. Math. Program. 6 (1974), 121-140.
• 13: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 14: Ailsa H. Land , S. Powell, FORTRAN Codes for Mathematical Programming: Linear, Quadratic and Discrete, John Wiley & Sons, Inc., New York, NY, 1973
• 15: LEWANDOWSKI, A., AND GRAUER, M. The reference point optimization approach--Methods of efficient implementation. IIASA Collaborative Proceedings Series: Multiobjective and Stochastic Optimization, CP-12-S12, IIASA, Laxenburg, Austria, 1982.
• 16: Roy E. Marsten, The Design of the XMP Linear Programming Library, ACM Transactions on Mathematical Software (TOMS), v.7 n.4, p.481-497, Dec. 1981 [doi>10.1145/355972.355976]
• 17: MOLER, C.B. Design of an interactive matrix calculator. In AFIPS Conference Proceedings of the 1980 National Computer Conference, vol. 49. AFIPS Press, Arlington, Va., 1980.
• 18: MURTAGH, B. A., AND SAUNDERS, M. A. Large-scale linearly constrained optimization. Math. Program. 14 (1978), 41-72.
• 19: MURTACH, B. A., AND SAUNDERS, M.A. Minos 5.0 user's guide. Tech. Rep. SOL 83-20, Systems Optimization Laboratory, Dept. of Operations Research, Stanford Univ., Calif., 1983.
• 20: NAZARETH, J. L. Hierarchical implementation of optimization methods. In Numerical Optimization, 1984, P. Boggs, R. Byrd, and R. Schnabel, Eds. SIAM, Philadelphia, Pa., 1985, pp. 199-210.
• 21: NAZARETH, J.L. Pricing criteria in linear programming. Unpublished manuscript.
• 22: NAZARETH, J.L. Algorithms based upon generalized linear programming for stochastic programs with recourse. In Proceedings of IFIP International Workshop on Stochastic Programming: Algorithms and Applications, F. Archetti, Ed., Lecture Notes on Control and Information Science 76. Springer-Verlag, New York, 1986.
• 23: NAZARETH, J. L. Design and implementation of a stochastic programming optimizer with recourse and tenders, in Numerical Techniques for Stochastic Optimization Problems, Y. Ermoliev and R. J.-B. Wets, Eds. Springer-Verlag, New York. To be published.
• 24: NAZARETH, J. L., AND WETS, R.J.-B. Algorithms for stochastic programs: The case of nonstochastic tenders. Math. Program. Stud. 28 (1986), 1-28.
• 25: ORCHARD-HAYS, W. Advanced Linear Programming Computing Techniques. McGraw-Hill, New York, 1968.
• 26: PALACIOS-GOMEZ, F., LASDON, L., AND ENQUIST, M. Nonlinear optimization by successive linear programming. Manage. Sci. 28 (1982), 1106-1120.
• 27: REID, J.K. Fortran subroutines for handling sparse linear programming bases. Rep. R8269, Atomic Energy Research Establishment, Harwell, England, 1976.
• 28: SMITH, B. W., BOYLE, J. M., AND CODY, W.J. The NATS approach to quality software. In Proceedings of IMA Conference on Software/or Numerical Mathematics, J. Evans, Ed. Academic Press, New York, 1974, pp. 393-405.
• 29: TOMLIN, J.A. LPM1--User's manual. Systems Optimization Laboratory, Dept. of Operations Research, Stanford Univ., Calif., 1975.
• 30: WETS, R.J.-B. Stochastic programming: Solution techniques and approximation schemes. In Mathematical Programming: The State-of-the-Art, A. Bachem, M. Groetschel, and B. Korte, Eds. Springer-Verlag, New York, 1983, pp. 566-603.

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Software libraries; Modules and interfaces
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Modules, packages

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization; Linear programming; Nonlinear programming

General Terms:
Algorithms, Experimentation, Languages