Browse Prior Art Database

Comments, Queries, and Debate: The Invention of Linear Programming

IP.com Disclosure Number: IPCOM000129603D
Original Publication Date: 1988-Mar-31
Included in the Prior Art Database: 2005-Oct-06
Document File: 4 page(s) / 21K

Publishing Venue

Software Patent Institute

Related People

Benjamin L. Schwartz: AUTHOR [+2]

Abstract

The Analytic Sciences Corporation Arlington, VA

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

Page 1 of 4

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Copyright ©; 1989 by the American Federation of Information Processing Societies, Inc. Used with permission.

Comments, Queries, and Debate: The Invention of Linear Programming

Benjamin L. Schwartz

The Analytic Sciences Corporation Arlington, VA

In his article "The Discovery of Linear Programming" in the Annals (Vol. 6, No. 3, 1984, 283295), Robert Dorfman presented a fascinating account of the very earliest days and years of linear programming. I reviewed that paper in Computing Reviews (Vol. 26, No. 9, 1985, pp. 531- 532), where I hinted at some points of disagreement with Dorfman's position. The present note expands on that hint with a full-fledged explanation. For completeness and continuity of presentation, I include some material from my review; permission by the ACM to use these extracts is herewith gratefully acknowledged.

Dorfman asks, "Who discovered linear programming and when?" His answer is that there were three independent codiscoverers: L. V. Kantorovich of the Soviet Union in 1939; T. C. Koopmans in 1942-1943; and G. B. Dantzig in 19471948. I respectfully differ. I submit that the very facts which Dorfman presents show that Kantorovich and Koopmans were prediscoverers, and Dantzig alone qualifies as the discoverer.

The disagreement stems (as so often it does) from differences in definition. Pay attention, dear reader, while I provide a definition of linear programming, sadly needed since even the standard and widely used texts skirt that formality. First, what is a linear program?

A linear program (LP) is three things, an ordered triple as mathematically oriented readers might put it:

1. A set of variables or unknowns, whose values are to be found. 2. A set of linear constraints (equalities or inequalities) in the variables that must be satisfied. 3. A linear objective function in the variables, whose value is to be maximized or minimized subject to the constraints.

The reader should scan this definition carefully, for, if he agrees with it, he too will be forced to dissent from Dorfman's conclusion.

Next we define: Solving a linear program means finding a set of values for the variables that satisfies the constraints and optimizes the objective function.

Notice again by way of caution that, in the normal usage of the simplex solution theory, one may have a solution to a linear program without having solved the linear program! The usual usage calls a set of values a "solution" merely if the constraints are satisfied. There is an important distinction between a feasible solution and an optimal solution. By my definition, only the latter "solves" the linear program.

Finally, we can define linear programming as the body of theory and methods to solve linear programs with computational efficiency.

In particular, I interpret "the body of theory" to include enough of a formulation of duality to express in some form the so- called fundamental theorem of linear...