17
$\begingroup$

I see from here and many other sources that Dantzig invented the Simplex method in 1947. After much searching, I found that the earliest publication is this in 1956. Does anyone know where the original 1947 paper is?

$\endgroup$

4 Answers 4

19
$\begingroup$

Introduction

When Dantzig devised the algorithm, he was working at the Pentagon and thus many things would have been designated as classified in the military. There are a few more details provided in the book "How Reason Almost Lost Its Mind: The Strange Career of Cold War Rationality" by Erickson et al. (2013) but I need permission from the second author before I can quote any part of that.

A number of Dantzig's documents published a few years after 1947 concerning the simplex method are publicly available; for instance, Dantzig, Orden and Wolfe published the generalized simplex method in 1954, but it is unclear whether the original paper has since been declassified and published publicly.

Most Important Finding

In "Dantzig, George B. (1914–2005)" by Cottle, Eaves and Thapa (2016), there is this curious reference in the following biography.

Selected Works

1947. Prospectus for the AAF electronic computer. Unpublished manuscript.

AAF = United States Army Air Force.

I am not certain if this really was Dantzig's publication, but if so, then it suggests it won't be publicly available. However, there is a strong hint to this in the paragraphs I quote below.

Dantzig nonetheless turned down a position in mathematics at UC Berkeley for the greater financial security of a position at the Pentagon. There he undertook the challenge to "mechanize" the planning process. War planning required the coordination of an entire nation and yet was executed with desk calculators; the need for mechanization was clear. To this end, a group in the Air Force was organized under the name Project SCOOP (Scientific Computation of Optimum Programs) and headed by M.K. Wood. Dantzig was a principal.

Two movements suggested that progress was possible: Leontief's (1936) work and the emergence of the computer; indeed, Project SCOOP arranged for Pentagon support of computer development (see Dantzig 1947). In early 1947, Dantzig formulated the general statement of a linear program. In June of that year, he learned from T.C. Koopmans, who had been studying transportation problems (Koopmans 1947) that economists had no algorithm for solving a linear program. By July Dantzig had designed the simplex method.

History

There are several journal articles that describe Dantzig's invention and discovery of the method, some including his own; for instance, this unclassified technical report titled "Impact of Linear Programming on Computer Development" by Dantzig (1985).

Origins of the Simplex Method, Summer 1947

The first idea that would occur to anyone as a technique for solving a linear program, aside from the obvious one of moving through the interior of the convex set, is that of moving from one vertex to the next along the edges of the polyhedral set. I discarded this idea immediately as impractical in higher dimensional spaces. It seemed intuitively obvious that there would be far too many vertices and edges to wander over in the general case for such a method to be efficient.

When Hurwicz came to visit me at the Pentagon in the summer of 1947, I told him how I had discarded this vertex-edge approach as Intuitively inefficient for solving LP. I suggested Instead that we study the problem in the geometry of columns rather than the usual one of the rows -- column geometry incidentally was the one I had used in my Ph.D. thesis on the Neyman-Pearson Lemma. We dubbed the new method "climbing the bean pole." It looked to me efficient. [...] Apparently, in one geometry the simplex method looks efficient while in another it appeared to be very inefficient! Thus the simplex method was born in August 1947.

Other potential avenues to track the paper

I also found a comprehensive list of Dantzig's publications, talks and correspondences, where of interest are

box 10, folder 19 Letters to Laderman Simplex Algorithm Dec 1947/Sept. 1947

box 10, folder 21 First Simplex Method Computations Summer 1947

box 10, folder 22 AMC SCOOP Supply Procedure October 1947

box 10, folder 23 Outline of Talk Given BLS (Cornfield) 6/26/1947

box 16, folder 29 Copies of correspondence with Von Neumman 10/1/1947

box 16, folder 34 Discussion of a Max problem Von Neumman 11/15/1947.

The first two items in particular may be of greatest relevance. Unfortunately, these are all physically archived within Stanford University Library so I am not able to access them.

$\endgroup$
6
  • $\begingroup$ This is a great answer @TheSimpliFire. I really enjoyed reading that. Thank for putting all these valuable information together. $\endgroup$ Jun 9, 2022 at 19:20
  • 1
    $\begingroup$ This makes me curious about the "geometry of rows" hinted at... what would a row-based simplex method look like? Even if inefficient, it seems interesting to learn about. $\endgroup$
    – Max
    Jun 10, 2022 at 7:15
  • $\begingroup$ Nice. But apparently inconsistent quotes from different sources. "By July Dantzig had designed the simplex method.". "Thus the simplex method was born in August 1947." $\endgroup$ Jun 10, 2022 at 12:43
  • $\begingroup$ @MarkL.Stone The vast majority of literature cite August 1947, including Dantzig himself (see this interview). Perhaps July 1947 was meant to be his initial design/conception, which was then fully developed in August, but I haven't found any more documents to explain this. $\endgroup$
    – TheSimpliFire
    Jun 10, 2022 at 12:49
  • 2
    $\begingroup$ @Max the row-based simplex is implemented in SoPlex (soplex.zib.de). You can read about it here: nbn-resolving.org/urn:nbn:de:0297-zib-16349 $\endgroup$
    – mattmilten
    Jun 10, 2022 at 13:36
4
$\begingroup$

Another paper you may want to look at is the Project SCOOP (Scientific Computation of Optimum Programs) report, circa 1951. SCOOP was the project under which Dantzig did his first LP work. This report is accessible here: https://www.informs.org/Explore/History-of-O.R.-Excellence/O.R.-Methodologies/Optimization-Mathematical-Programming

$\endgroup$
3
$\begingroup$

The earliest Dantzig reference I know for the simplex method is:

George B. Dantzig, "Maximization of a Linear Function of Variables Subject to Linear Inequalities." In Activity Analysis of Production and Allocation, Tjalling C. Koopmans, ed., Wiley (1951) 339-347.

Although this volume was published in 1951, it is based on presentations given at a conference in 1949, and Dantzig's footnotes on the title page make it clear that his investigations of the simplex method dated to 1947.

This and other early references from Dantzig's work at the RAND Corporation are given in The Origins of a Practical Simplex Method, a talk I contributed to a celebration of Dantzig's "100th birthday" at the INFORMS Annual Meeting in 2014.

$\endgroup$
2
$\begingroup$

Just to supplement a great answer by @TheSimpliFire, the chapter "Origins of the Simplex Method" by Dantzig in "A history of scientific computing" (June 1990), also gives some idea of what work was being done in the field around the time he developed his approach.

A reference provided in that chapter is to:

G. B. Dantzig, "Linear Programming," in Problems for the Numerical Analysis of the Future, Proceedings of the Symposium on Modern Calculating Machinery and Numerical Methods, UCLA (July 29-31,1948); Appl. Math. 15, National Bureau of Standards (1951): 18-21.

The National Technical Reports Library in 1951 mentions that it includes four papers presented at the Symposium on Modern Calculating Machinery and Numerical Methods, held in July 1948 one of which is titled Linear Programing by George B. Dantzig. That report can be found here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.