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.

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...