Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

EVOLUTION OF LINEAR PROGRAMMING COMPUTING TECHNIQUES

IP.com Disclosure Number: IPCOM000128837D
Original Publication Date: 1956-Jul-18
Included in the Prior Art Database: 2005-Sep-19
Document File: 8 page(s) / 36K

Publishing Venue

Software Patent Institute

Related People

Orchard-Hays, Wm.: AUTHOR [+3]

Abstract

While the linear programming concept and the formulation of a specific model have value in themselves, the technique would fall short of its promise without efficient computing procedures. The simplex method has proved to be the most successful approach but it still leaves a wide range for detailed algorithms. At first, the method was applied by hand or with the aid of punched-card equipment. With the advent of internally-stored-program computers, automatic routines were designed. However, the early machines were adequate only for small problems and the original simplex method was not efficient for many LP models. A program of development was started at RAND to provide better computing techniques. Using first the IBM Model II CPC, then the 701 and now the 704, general LP routines of considerable power and flexibility have been developed. Future improvements will probably be possible only from higher level abstractions which take advantage of structure in the model matrix or which produce more efficient forms of the inverse of a sparse matrix.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

EVOLUTION OF LINEAR PROGRAMMING COMPUTING TECHNIQUES

Wm. Orchard-Hays

P-900 18 July 1956
The RAND Corporation 1700 MAIN ST. SANTA MONICA CALIFORNIA

SUMMARY

While the linear programming concept and the formulation of a specific model have value in themselves, the technique would fall short of its promise without efficient computing procedures. The simplex method has proved to be the most successful approach but it still leaves a wide range for detailed algorithms. At first, the method was applied by hand or with the aid of punched-card equipment. With the advent of internally-stored-program computers, automatic routines were designed. However, the early machines were adequate only for small problems and the original simplex method was not efficient for many LP models. A program of development was started at RAND to provide better computing techniques. Using first the IBM Model II CPC, then the 701 and now the 704, general LP routines of considerable power and flexibility have been developed. Future improvements will probably be possible only from higher level abstractions which take advantage of structure in the model matrix or which produce more efficient forms of the inverse of a sparse matrix.

EVOLUTION OF LINEAR PROGRAMMING COMPUTING TECHNIQUES [ title ]

Wm. Orchard-Hays

Linear programming is one of the modern mathematical tools which uses models. It might not be amiss to review briefly what we mean by a model and how they are used. Suppose one is concerned with production scheduling of an oil refinery. (This has practically become the classical LP example.) Now it is not the physical refinery, but flow diagrams, engineering data and other such abstraction which are, for the scheduler, the real world and contain his real problem. However, due to the bewildering complexity of even one facet of real life in detail, one needs a further concept of abstraction to bring order to his thinking. Linear programming is, or at least is based on, such a concept. It abstracts out of the real world those features of a system which are of importance to the questions being asked and organizes them into a simple scheme. Thus it has some value in itself regardless of any calculations which may subsequently be made.

Rand Corporation Page 1 Jul 18, 1956

Page 2 of 8

EVOLUTION OF LINEAR PROGRAMMING COMPUTING TECHNIQUES

The LP concept is simply to consider a system as composed of a number of elementary activities which consume and produce tangible items. It should be emphasized that these activities don't necessarily have physical counterparts, they are often composite abstractions. They are tied together in the LP model by linear material balance equations, one equation for each item. The unknowns are the levels at which the activities are to operate. Each activity is also assigned some value, giving another linear form to be optimized.

With this concept in mind, and with diagrams and da...