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 COMPUTER CODES FOR LINEAR PROGRAMMING

IP.com Disclosure Number: IPCOM000128838D
Original Publication Date: 1956-Mar-14
Included in the Prior Art Database: 2005-Sep-19

Publishing Venue

Software Patent Institute

Related People

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

Abstract

The growing literature on the subject of linear programming falls roughly into three categories: [ Footnote ] In lieu of references in the text, a catalogued bibliography is given at the end of the paper. (i) applications of the linear programming technique to problems of the military, industry and business, and occasionally to problems simply of academic interest; (ii) methods for solving the central mathematical problem posed by the resulting models; and (iii) computing techniques for implementing these methods. Our concern is mainly with the last although it is impossible to completely separate these three aspects, A concept of analysis has value only if it shows promise of being applicable to real-life problems. Where calculations are involved, they must at least be tractable in the abstract and feasible within current computational capabilities. It is not our purpose to attempt either a definition of linear programming and its uses or a comparison of the basically different methods of calculation. It is now pretty generally agreed that the simplex method of Dr. George Dantzig provides the best known approach. We must insist, however, that it is the fundamental theorems of this method which are of importance and not the particular algorithm and tableau which were set down in the original exposition. The calculations can be carried out in different ways and adaptations and extensions are easy to devise, at least in theory. One of the earliest and most widely used special cases - the transportation problem - was sufficiently important to warrant development of efficient computer codes for this one purpose, but it is difficult to find other sub-problems as well defined or as easily simplified. Consequently, a general algorithm has been applied in nearly all other cases but both theory and experience indicate that there is an upper bound well below 500 to the number of restraints that can be handled efficiently in this manner with foreseeable machines. Though this figure is approximate, it is probably already too high for some problems. This has been the cause of much concern. There has been a continuous effort at RAND for three years to develop general codes for larger and larger problems. Being now able to handle some 250 restraint equations in any number of variables and not yet having satisfied the demands of many realistic problems, we conclude that further attempts in this direction will be fruitless. We feel, however, that the present codes are of considerable value and, more importantly, that their evolution has shown the direction which future developments must take. In this regard, perhaps the most important result is the mutual realization by those who formulate problems and methods and those who devise computer programs that, for better or worse, they are joined together. Our aim is to discuss the growth of these codes, from the standpoint of both mathematical and coding techniques, and then to give a brief resume of current and proposed developments in this field at RAND. The presentation will be in three main parts which will bear, more or less respectively, on the following three theses. A. In order to handle efficiently a large number of problems of one type, codes must be designed with an eye to the two sides of computational problems (1) the method must be adapted to the characteristics of the machine, and (2) provision must be made for handling easily any reasonable special requirements, for making a variety of decisions automatically and for easy operation. B. In order to attain the required efficiency and flexibility, the codes must themselves be organized in a manner analogous to the method and not based on standard routines or universal methods. C. For solving very large problems at reasonable cost, it will be necessary to develop special techniques for special classes.

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

Page 1 of 25

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

EVOLUTION OF COMPUTER CODES FOR LINEAR PROGRAMMING

Wm. Orchard-Hays

P-810

14 March 1956

The RAND Corporation 1700 MAIN ST. SANTA MONICA California

FOREWORD

In late fall of 1952, Dr. George B. Dantzig at The RAND corporation requested that a programmer be assigned to work with him in developing machine computing procedures for the simplex method. The writer was given the assignment, which has since grown into a full-time job, and has been assisted, since late 1953, by Miss Leola Cutler and others of RAND's programming staff in both developing codes and running problems. The machine used in the beginning was the Model II CPC with five 941 units. The limitations of this equipment forced changes in methodology which later proved applicable to codes for the IBM 701. The relative power of the final 701 set-up aroused the interest of IBM's Data Processing Center and, with the advent of the 704, RAND and IBM decided to develop a linear programming system for this machine jointly. Mr. Hal Judd of IBM has worked with Miss Cutler and the writer on this project and much of the material below was originally prepared to describe the 704 system. The ideas here presented are not original to the 704 codes, however, and the methods are not tied to any one machine, except as noted. Applications to other machines are discussed briefly in Part C.

INTRODUCTION

The growing literature on the subject of linear programming falls roughly into three categories:1

(i) applications of the linear programming technique to problems of the military, industry and business, and occasionally to problems simply of academic interest; (ii) methods for solving the central mathematical problem posed by the resulting models; and (iii) computing techniques for implementing these methods. Our concern is mainly with the last although it is impossible to completely separate these three aspects, A concept of analysis has value only if it shows promise of being applicable to real-life problems. Where calculations are involved, they must at least be tractable in the abstract and feasible within current computational capabilities.

It is not our purpose to attempt either a definition of linear programming and its uses or a comparison of the basically different methods of calculation. It is now pretty generally agreed

1 In lieu of references in the text, a catalogued bibliography is given at the end of the paper.

Rand Corporation Page 1 Mar 14, 1956

Page 2 of 25

EVOLUTION OF COMPUTER CODES FOR LINEAR PROGRAMMING

that the simplex method of Dr. George Dantzig provides the best known approach. We must insist, however, that it is the fundamental theorems of this method which are of importance and not the particular algorithm and tableau which were set down in the original exposition. The calculations can be carried out in different ways and adaptations and extensions are easy to devise, at least in theory. One of the earlie...