LSNNO, a FORTRAN subroutine for solving large-scale nonlinear network optimization problems

ABSTRACT

The implementation and testing of LSNNO, a new FORTRAN subroutine for solving large-scale nonlinear network optimization problems is described. The implemented algorithm applies the concepts of partial separability and partitioned quasi-Newton updating to high-dimensional nonlinear network optimization problems. Some numerical results on both academic and practical problems are reported.

REFERENCES

• 1: David P. Ahlfeld , John M. Mulvey , Ron S. Dembo , Stavros A. Zenios, Nonlinear programming on generalized networks, ACM Transactions on Mathematical Software (TOMS), v.13 n.4, p.350-367, Dec. 1987 [doi>10.1145/35078.42181]
• 2: P. Beck , L. Lasdon , M. Engquist, A Reduced Gradient Algorithm for Nonlinear Network Problems, ACM Transactions on Mathematical Software (TOMS), v.9 n.1, p.57-70, March 1983 [doi>10.1145/356022.356025]
• 3: BERTSEKAS, D. P. Projected Newton methods for optimization problems with simple constraints. SIAM J. Control Optim. 20 (1980), 221-246.
• 4: BRADLEY, G. H., BROWN, G. G., AND GRAVES, G.W. Design and implementation of large scale transshipement algorithms. Manage. ScL 24 (1977), 1-34.
• 5: CONN, A. R., GOULD, N. I. M., AND TOINT, PH. L. A proposal for a Standard Data Input Format for large-scale nonlinear programming problems. Rep. 89/18, Dept. of Mathematics, FUNDP Namur (B), 1989.
• 6: CONN, A. R., GOULD, N. I. M., AND TOINT, PH. L. An introduction to the structure of large scale nonlinear optimization problems and the LANCELOT project. In Proceedings of the Ninth International Conference on Computational Methods in Applied Sciences and Engineering (Paris, 1990), SIAM, Philadelphia, Pa., pp. 42-51.
• 7: DEMBO, R.S. A bending backtracking linesearch for constrained optimization. Tech. Rep., Yale School of Management, Yale Univ., New Haven, 1984.
• 8: DEMBO, R.S. A primal truncated Newton algorithm with application to large scale nonlinear network optimization. Math. Program. Stud. 31 (1987), 43 71.
• 9: DEXmO, R. S. The performance of NLPNET, a large scale nonlinear network optimizer. Math. Program. Stud. 26 (1986), 245-249.
• 10: DEMBO, R. S., AND KLINCEWICZ, J.G. A scaled reduced gradient algorithm for network flow problems with convex separable costs. Math. Program. Stud. 15 (1981), 125-147.
• 11: DEMBO, R. S., MULVEY, J. M., AND ZENIOS, S.A. Large-scale nonlinear network models and their application. Oper. Res. 37, 3 (1989), 353-372.
• 12: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 13: ESCUDERO, L F. A motivation for using the truncated Newton approach in a very large scale nonlinear network problem. Math. Program. Stud. 26 (1986), 240-245.
• 14: ESCUDERO, L. F. Performance evaluation of independent superbasic sets on nonlinear replicated networks. European J. Oper. Res. 23 (1986), 343 355.
• 15: GARC,, N K., AND TAPIA, R. A. QDN: A variable storage algorithm for unconstrained optimization. Rep. Dept. of Mathematical Scmnces, Rice Univ, Houston, Tex., 1980
• 16: GmOOmADIS, M. D. An efficient implementation of the network simplex method. Math. Program. Stud. 26 (1986), 83-111.
• 17: GmEWANK, A., AND TOINT, PH. L. Partitioned variable metric updates for large structured optimization problems. Numer. Math. 39 (1982), 119-137.
• 18: GRIEWANK, A., AND TOINT, PH. L. On the unconstrained optimization of partially separable functions. In Nonlznear Optzmzzation 1981, M. J. D. PowelL Ed., Academic Press, New York, 1982, 301-312.
• 19: GRIEWANK, A., AND TOINT, PH. L. Numerical experiments with partially separable optimization problems. In Numerical Analysis Procee&ngs Dundee 1983, D. F. Griffiths, Ed.. Lecture Notes in Mathematics 1066, Springer-Verlag, Berlin, 1984, 203 220.
• 20: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 21: Mm~R, R.R. Two segment separable programming. Manage. Sc~. 15 (1979), 385 395.
• 22: MURTAGH, B., AND SAUNDERS, M. Large scale linearly constrained optimization. Math. Program. 14 (1978), 41-72.
• 23: SHANNO, D. F., AND PHUA, K. H. Matrix conditioning and nonlinear optimization Math. Program. 14 (1978), 149 160.
• 24: P. L. Toint , D. Tuyttens, On large scale nonlinear network optimization, Mathematical Programming: Series A and B, v.48 n.1, p.125-159, Mar. 1990 [doi>10.1007/BF01582254]
• 25: ZENIOS, S. Numerical optimization benchmarks on advanced architecture computers. Rep. 88-04-03, Decision Sciences Dept., The Wharton School. Univ. of Pennsylvania, Phi}adelphm, 1988.
• 26: S. A. Zenios , J. M. Mulvey, Nonlinear network programming on vector supercomputers: A study on the CRAY X-MP, Operations Research, v.34 n.5, p.667-682, Sept.-Oct. 1986 [doi>10.1287/opre.34.5.667]
• 27: S. A. Zenios , J. M. Mulvey, Vectorization and multitasking of nonlinear network programming algorithms, Mathematical Programming: Series A and B, v.42 n.2, p.449-470, February 1, 1988 [doi>10.1007/BF01589416]
• 28: ZENIOS, S. A., AND PINAR, M. C. Parallel block-partitioning of truncated newton for nonlinear network optimization. Rep 89-09-08, Decision Science Dept., The Wharton School, Univ. of Pennsylvania, Philadelphm, Pa., 1989.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency; Certification and testing

General Terms:
Algorithms, Measurement, Performance

Keywords:
Fortran program units, independent superbasic arcs, large-scale problems, nonlinear network optimization, nonlinear optimization, truncated Newton methods