Integration of a primal simplex network algorithm with a large-scale mathematical programming system

ABSTRACT

In this paper we discuss the implementation of a primal simplex algorithm for network problems in the MPSIII mathematical programming system. Because of the need to interface with the rest of the MPS this implementation is unorthodox, but computationally effective, and has a number of advantages over “stand alone” network optimizers. It is argued that a similar approach is appropriate for other general-purpose mathematical programming systems, and has applications beyond pure network optimization.

REFERENCES

• 1: BEALE, E. M.L. Advanced algorithmic features for general mathematical programming systems. In Integer and Nonlinear Programming, J. Abadie, Ed. North-Holland, Amsterdam, 1970, pp. 119-138.
• 2: BRADLEY, G. H., BROWN, G. G., AND GRAVES, G.W. Design and implementation of large scale transshipment algorithms. Manage. Sci. 24 (1977); 1-34.
• 3: BRADLEY, G. H., BROWN, G. G., AND GRAVES, G.W. Structural redundancy in large-scale optimization models. In Redundancy in Mathematical Programming, M. H. Karwan et al., Eels. Springer-Verlag, Heidelberg, Berlin, New York, 1983, pp. 145-169.
• 4: CREEGAN, J. B. Successive linear programming with MPSIII SLEUTH. In Proceedings of SHARE 56 (Houston, Tex., Mar. 1981).
• 5: FORREST, J. J. H., AND TOMLIN, J.A. Updating triangular factors of the basis to maintain sparsity in the product form simplex method. Math. Prog. 2 (1972), 263-278.
• 6: GLOVER, F., KLINGMAN, D., AND STUTZ, J. Augmented threaded index method for network optimization. INFOR 12 (1974), 293-298.
• 7: GRAVES, G. W., AND MCBRIDE, R.D. The factorization approach to large-scale linear programming. Math. Prog. 10 (1976), 91-110.
• 8: GREENBERG, H.J. A tutorial on matricial packing. In Design and Implementation of Optimization Software, H. J. Greenberg, Ed. Sijthoff and Noordhoff, The Netherlands, 1978, pp. 109-142.
• 9: GREENBERG, H. J., AND KALAN, J. E. Representations of networks. In Proceedings of the National Computer Conference (1976), pp. 939-943.
• 10: HELLERMAN, E., AND RARICK, D. C. The partitioned pre-assigned pivot procedure (P~). In Sparse Matrices and Their Applications, D. J. Rose and R. Willoughby, Eds. Plenum, New York, 1972, pp. 67-76.
• 11: James E. Kalan, Aspects of large-scale in-core linear programming, Proceedings of the 1971 26th annual conference, p.304-313, January 1971 [doi>10.1145/800184.810500]
• 12: Jeff L. Kennington , Richard V. Helgason, Algorithms for Network Programming, John Wiley & Sons, Inc., New York, NY, 1980
• 13: KLINGMAN, D., NAPIER, A., AND STUTZ, J. NETGEN: A program for generating large scale capacitated assignment, transportation and minimum cost flow network problems. Man. Sci. 20 (1974), 814-821.
• 14: KLINGMAN, D., MOTE, J., AND WHITMAN, D. Using networks to improve MPSX performance. ORSA/TIMS Joint National Meeting, Chicago, Ill., Apr. 1983.
• 15: ORCHARD-HAYS, W. Advanced Linear Programming Computing Techniques. McGraw-Hill, New York, 1968.
• 16: TOMLIN, J.A. On pricing and backward transformation in linear programming. Math. Prog. 6 (1974), 42-47.
• 17: TOML|N, J. A., AND WELCH, J. S. "MIPIII--A SLEUTH based mixed integer programming System. In Proceedings of SHARE 57 (Chicago, Ill., Aug. 1981).
• 18: TOMLIN, J. A., AND WELCH, J.S. Formal optimization of some reduced linear programming problems. Math Prog. 27 (1983), 232-240.
• 19: TOMLIN, J. A., AND WELCH, J.S. Implementation of a primal simplex network algorithm in MPSIII. In Proceedings of SHARE 60 (San Francisco, Calif., Feb. 1983).

INDEX TERMS

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

General Terms:
Algorithms, Measurement, Performance