Nonlinear programming on generalized networks

ABSTRACT

We describe a specialization of the primal truncated Newton algorithm for solving nonlinear optimization problems on networks with gains. The algorithm and its implementation are able to capitalize on the special structure of the constraints. Extensive computational tests show that the algorithm is capable of solving very large problems. Testing of numerous tactical issues are described, including maximal basis, projected line search, and pivot strategies. Comparisons with NLPNET, a nonlinear network code, and MINOS, a general-purpose nonlinear programming code, are also included.

REFERENCES

• 1: BALBERG, 1., AND BINENBAUM, IN. (~omputer study of the percolation threshold in a two dimensional anisotropic system of conducting sticks. Phys. Rev. B 28, 7 (Oct. 1983).
• 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. On the Goldstein-Levitin-Polyak gradient projection method. IEEE Trans. Automat. Contr. AC-21 (1976), 174-181.
• 4: BRADLEY, G., BROWN, G., AND GRAVES, G. Design and implementation of large scale primal transshipment algorithms. Manage. Sci. 24, 1 (1977), 1-34.
• 5: BROWN, G. G., AND MCBRIDE, R.D. Solving generalized networks. Manage. Sci. 30, 12 (1984), 1497-1523.
• 6: COLLINS, U., COOPER, L., HELGASON, R., KENNINGTON, J., AND LEBLANC, L. Solving the pipe network analysis problem using optimization techniques. Manage. Sci. 24, 7 (1978), 747- 760.
• 7: COOPER, L., AND KENNINGTON, J. Steady state analysis of nonlinear resistive electrical networks using optimization techniques. Tech. Rep. IEOR 77-12, Southern Methodist Univ., Dallas, Tex., 1977.
• 8: COOPER, L., AND LEBLANC, L.J. Stochastic transportation problems and other network related convex problems. Nay. Res. Logist. Q. (1977).
• 9: DEMBO, R. S., CHIARRI, A., GOMEZ, J., PARADINAS, L., AND GUERRA, J. Integrated system for electric power system operation planning. Hidroelectrica Espanola Tech. Rep., Madrid, 1985.
• 10: DEMBO, R. S., AND KLINCEWICZ, J.G. A scales reduced gradient algorithm for network flow problems with convex separable costs. Math. Program. Stud. 15 (1981), 125-147.
• 11: DEMBO, R. S., AND KLINCEWICZ, J.G. Resolving degeneracy using a maximal basis. School of Organization and Management Working Paper Series B 63, July 1983.
• 12: DEMBO, R. S., MULVEY, Z. M., AND ZENIOS, S.A. Large scale nonlinear network models and their applications. Rep. EES-86-18, Dept. of Civil Engineering and Operations Research, Princeton Univ., Princeton, N.J., 1986.
• 13: DEMBO, R. S., AND STEIHAUG, T. Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26, (1983), 190-212.
• 14: DEMBO, R.S. The performance of NLPNET, A nonlinear network optimizer. Math. Program. Stud. 26 (1986), 245.
• 15: DEMBO, R. S. A primal truncated Newton algorithm with application to nonlinear network optimization. Math. Program. Stud. 31 (1987), 43-72.
• 16: FLORIAN, M., AND NGUYEN, S. A method for computing network equilibrium with elastic demands. Transport. Sci. 8 (1974), 321-332.
• 17: GILL, P. E., MURRAY, W., AND WRIGHT, i.H. Practical Optimization. Academic Press, London and New York, 1981.
• 18: GLOVER, F., HULTZ, J., KLINGMAN, D., AND STUTZ, J. Generalized networks: A fundamental computer-based planning tool. Manage. Sci. 24, 12 (1978), 1209-1220.
• 19: GLOVER, F., JONES, G., KARNEY, D., KLINGMAN, D., AND MOTE, J. An integrated production, distribution and inventory planning system. Interfaces 9, 5 (Nov. 1979).
• 20: GLOVER, F., KARNEY, D., KLINGMAN, D., AND NAPIER, A. A computational study on start procedures, basis change criteria and solution algorithms for transportation problems. Manage. Sci. 20, 5 (1974), 793-813.
• 21: HEARN, D. W., LAWPHONGPANICH, S., AND VENTURA, J.A. Restricted simplicial decomposition: Computation and extensions. Math. Program. Stud. 31 (1987), 99-118.
• 22: HELGASON, R. V., AND KENNINGTON, J.L. An efficient specialization of the convex simplex method for nonlinear network flow problems. Tech. Rep. IEOR 77017, Southern Methodist Univ., Dallas, Tex., 1978.
• 23: KAMESAM, P. V., AND MEYER, R.R. Multipoint methods for nonlinear networks. In Mathematical Programming at Oberwolfach H, K. Ritter, Ed. North-Holland, Amsterdam, 1984.
• 24: Jeff L. Kennington , Richard V. Helgason, Algorithms for Network Programming, John Wiley & Sons, Inc., New York, NY, 1980
• 25: KLINCEWlCZ, J.G. A Newton method for convex separable network flow problems. Presented at the ORSA/TIMS National Meeting, Chicago, ill. Apr. 1983.
• 26: LASDON, L. S., AND WAREN, A.D. A survey of nonlinear programming applications. Oper. Res. 28, 5 (1980), 34-50.
• 27: L. S. Lasdon , A. D. Waren , A. Jain , M. Ratner, Design and Testing of a Generalized Reduced Gradient Code for Nonlinear Programming, ACM Transactions on Mathematical Software (TOMS), v.4 n.1, p.34-50, March 1978 [doi>10.1145/355769.355773]
• 28: LEBLANC, L., MORLOK, E., AND PIERSKELLA, W. An efficient approach to solving the road network equilibrium traffic assignment problem. Trans. Res. 9 (1975), 309-318.
• 29: MEYER, R.R. Algorithms for a class of 'convex' nonlinear integer programs. Computers and Mathematical Programming, National Bureau of Standards Special Publication, 502, 1978.
• 30: MCCORMICK, G. Anti-zigzagging by bending. Manage. Sci. 15, (1969), 315-320.
• 31: MULVEY, J. M. Testing of a large-scale network optimization program. Math. Program. 15, (1978), 291-315.
• 32: MULVEY, J.M. Nonlinear network models in finance. Advances in Mathermal Programming and Financial Planning. JAI Press, Greenwich, Conn., 1987.
• 33: MULVEY, J. M. Estimating joint strata weights for poststratification. Eur. J. Oper. Res. 27 (1986), 201-206.
• 34: MULVEY, J. M., AND ZENIOS, S.A. Solving large scale generalized networks. J. Inf. Optimiz. Sci. 6, 1 (1985), 95-112.
• 35: 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]
• 36: MULVEY, J.M. Anticipatory personnel management: An application of multi-criteria networks. In Management of R & D Engineering. Elsevier North-Holland, New York, 1985.
• 37: J. M. Mulvey , S. A. Zenios, Real-time operational planning for the U. S. air traffic system, Applied Numerical Mathematics, v.3 n.5, p.427-441, Oct. 1987 [doi>10.1016/0168-9274(87)90031-6]
• 38: MURTAGH, B., AND SAUNDERS, M. Large scale linearly constrained optimization. Math. Program. 14 (1978), 41-72.
• 39: ROSENTHAL, R. E. A nonlinear network flow algorithm for maximization of benefits in a hydroelectric power system. Oper. Res. 29 (1981), 763-786.
• 40: ZENIOS, S. A., DRUD, A., AND MULVEY, J.M. Balancing large social accounting matrices with nonlinear network programming. Rep. EES-86-1, Dept. of Civil Engineering and Operations Research, Princeton Univ., Princeton, N.J., 1986.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming; Gradient methods
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory