Aspects of large-scale in-core linear programming

ABSTRACT

Unconventional methods for matricial compression indicate that large linear programming constraint matrices may comfortably remain core-resident during optimization. Minor changes in the computational aspects of the simplex algorithm coupled with efficient inverse matrix representation show that the major portion of the inverse in product form of a basis may be embedded in the constraint matrix. A method for generating a sparse inverse matrix is presented.

REFERENCES

• 1: PDP-10 Reference Handbook, p. 484, 1969, Program Library, DEC, Maynard. Mass.
• 2: OPHELIE Preliminary User Manual, pub. no.D0001507002. p. D-4, Control Data Corporation, Minneapolis, Minn.
• 3: Orchard-Hays, W., Advanced Linear-Programming Computing Techniques, pp. 330-331, 1968, McGraw-Hill Book Co., Inc., New York.
• 4: Kalan, J. E., "Naive Linear Programming", Computer Science/Operations Research Center, Southern Methodist University, Tech. Report No. CP-71009, May, 1971.
• 5: Beale, E. M. L., Non-Linear Programming, ed. J. Abadie, p. 169. 1967, John Wiley and Sons, New York.
• 6: Markowitz, H. M., "The Elimination Form of the Inverse and Its Application to Linear Programming", Management Science, vol. 3, pp. 255-269, April, 1957.
• 7: Hellerman, E., and Rarick, D., "The Pre-assigned Pivot Procedure", presented at the 7th International Symposium on Mathematical Programming, The Hague, Holland, September, 1970.
• 8: Kalan, J. E., and Korfhage, R. R., "Systems of Distinct Representatives and Optimal Matrix Permutations", Computer Science/Operations Research Center, Southern Methodist University, Tech. Report No. CP-71011, July, 1971.
• 9: Korfhage, R. R., "On Systems of Distinct Representatives for Several Collections of Sets", doctoral dissertation, University of Michigan, 1961.

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.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods); Matrix inversion

General Terms:
Theory

Keywords:
Linear programming, Matrix compression, Matrix inversion, Simplex algorithm, Sparse matrices