An improved primal simplex variant for pure processing networks

ABSTRACT

In processing networks, ordinary network constraints are supplemented by proportional flow restrictions on arcs entering or leaving some nodes. This paper describes a new primal partitioning algorithm for solving pure processing networks using a working basis of variable dimension. In testing against MPSX/370 on a class of randomly generated problems, a FORTRAN implementation of this algorithm was found to be an order-of-magnitude faster. Besides indicating the use of our methods in stand-alone fashion, the computational results also demonstrate the desirability of using these methods as a high-level module in a mathematical programming system.

REFERENCES

• 1: Richard H. Bartels , Gene H. Golub, The simplex method of linear programming using LU decomposition, Communications of the ACM, v.12 n.5, p.266-268, May 1969 [doi>10.1145/362946.362974]
• 2: BRADLEY, G., BROWN, G., AND GRAVES, G. Design and implementation of large scale primal transshipment algorithms. Manage. Sci. 24, 1 (Sept. 1977), 1-34.
• 3: CHARNES, A., COOPER, W., DIVINE, D., HINKEL, W., KONING, J., AND LOVEGREN, V. A seashore rotation goal programming model for Navy use. Res. Rep. CCS 429, Center for Cybernetic Studies, Univ. of Texas, Austin, 1982.
• 4: CHEN, C.-H., AND ENGQUIST, M. Computational comparison of two solution procedures for allocation processing networks. Math. Program. Stud. 26 (1986), 218-220.
• 5: J Chou-Hong Chen , Michael Engquist, A primal simplex approach to pure processing networks, Management Science, v.32 n.12, p.1582-1598, Dec. 1986 [doi>10.1287/mnsc.32.12.1582]
• 6: GLOVER, F., GLOVER, R., AND MARTINSON, F. A netform system for resource planning in the U.S. Bureau of Land Management. J. Oper. Res. Soc. 35, 7 (July 1984), 605-616.
• 7: GLOVER, F., KARNEY, D., AND KLINGMAN, D. Implementation and computational comparisons of primal, dual, and primal-dual computer codes for minimum cost network flow problems. Networks 4, 3 (1974), 191-212.
• 8: 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 (Jan. 1974), 793-813.
• 9: GLOVER, F., AND KLINGMAN, D. Capsule view of future developments of large-scale network and network-related problems. Res. Rep. CCS 238, Center for Cybernetic Studies, Univ. of Texas, Austin, 1975.
• 10: GLOVER, F., AND KLINGMAN, D. The simplex SON algorithm for LP/embedded network problems. Math. Program.. Stud. 15 (1981), 148-176.
• 11: GLOVER, F., AND KLINGMAN, D. Basis change characterizations for the simplex SON algorithm for LP/embedded networks. Math. Program. Stud. 24 (1985), 141-157.
• 12: GLOVER, F., KLINGMAN, D., PHILLIPS, N., AND ROSS, G. Integrating modeling, algorithm design, and computational implementation to solve a large-scale nonlinear mixed integer programming problem. Ann. Oper. Res. 5 (1985/6), 395-411.
• 13: GLOVER, F., KLINGMAN, D., AND STUTZ, J. Augmented threaded index method for network optimization. INFOR 12, 3 (Oct. 1974), 293-298.
• 14: IBM Mathematical Programming System Extended/370 (MPSX/370) Program Reference Manual, 4th Edition. IBM Corp., Technical Publications Dept., White Plains, N.Y., 1979.
• 15: Jeff L. Kennington , Richard V. Helgason, Algorithms for Network Programming, John Wiley & Sons, Inc., New York, NY, 1980
• 16: KOENE, J. Minimal cost flow in processing networks: A primal approach. Ph.D. dissertation, Eindhoven Univ. of Technology, Eindhoven, The Netherlands, 1982.
• 17: 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]
• 18: MCBRIDE, R. Solving embedded generalized network problems. European J. Oper. Res. 21, 1 (July 1985), 82-92.
• 19: John M. Mulvey, Pivot Strategies for Primal-Simplex Network Codes, Journal of the ACM (JACM), v.25 n.2, p.266-270, April 1978 [doi>10.1145/322063.322070]
• 20: MURTAGH, B. Advanced Linear Programming: Computation and Practice. McGraw-Hill, New York, 1981.
• 21: MURTAGH, B., AND SAUNDERS, M. Large scale linearly constrained optimization. Math. Program. 14, 1 (Jan. 1978), 41-72.
• 22: ORCHARD-HAYS, W. Advanced Linear Programming Computing Techniques. McGraw-Hill, New York, 1968.
• 23: REID, J. FORTRAN subroutines for handling sparse linear programming bases. Rep. AERE- R8269, Computer Science and Systems Div., AERE Harwell, Oxfordshire, England, 1976.
• 24: REID, J. A sparsity-exploiting variant of the Bartels-Golub decomposition for linear programming bases. Math. Program 24, 1 (Sept. 1982), 55-69.
• 25: J. A. Tomlin , J. S. Welch, Integration of a primal simplex network algorithm with a large-scale mathematical programming system, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.1-11, March 1985 [doi>10.1145/3147.3163]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Algorithms, Design, Performance, Theory