Documenta Mathematica

Extra Volume: Optimization Stories, 2012

Preface  1

Introduction  3

Stories about the Old Masters of Optimization  7

Ya-xiang Yuan Jiu Zhang Suan Shu and

the Gauss Algorithm for Linear Equations  9–14

Eberhard Knobloch

Leibniz and the Brachistochrone  15–18

Eberhard Knobloch

Leibniz and the Infinite  19–23

Peter Deuflhard

A Short History of Newton’s Method  25–30

Eberhard Knobloch

Euler and Infinite Speed  31–35

Eberhard Knobloch

Euler and Variations  37–42

Martin Grötschel and Ya-xiang Yuan Euler, Mei-Ko Kwan, Königsberg,

and a Chinese Postman  43–50

Linear Programming Stories  51

David Shanno

Who Invented the Interior-Point Method?  55–64

George L. Nemhauser

Column Generation for Linear and Integer Programming 65–73

Günter M. Ziegler

Who Solved the Hirsch Conjecture?  75–85

Friedrich Eisenbrand Pope Gregory, the Calendar,

and Continued Fractions  87–93

Martin Henk

Löwner–John Ellipsoids  95–106

Robert E. Bixby A Brief History of Linear and

Mixed-Integer Programming Computation  107–121

Discrete Optimization Stories  123

Jaroslav Nešetřil and Helena Nešetřilová The Origins of Minimal Spanning Tree Algorithms –

Borůvka and Jarník  127–141

William H. Cunningham

The Coming of the Matroids  143–153

Alexander Schrijver

On the History of the Shortest Path Problem  155–167

Alexander Schrijver On the History of the Transportation

and Maximum Flow Problems  169–180

William R. Pulleyblank Edmonds, Matching

and the Birth of Polyhedral Combinatorics  181–197

Thomas L. Gertzen and Martin Grötschel Flinders Petrie, the Travelling Salesman Problem, and the Beginning of Mathematical Modeling

in Archaeology  199–210

Rolf H. Möhring

D. Ray Fulkerson and Project Scheduling  211–219

Gérard Cornuéjols

The Ongoing Story of Gomory Cuts  221–226

William Cook Markowitz and Manne + Eastman + Land and Doig

= Branch and Bound  227–238

Susanne Albers Ronald Graham:

Laying the Foundations of Online Optimization  239–245

Continuous Optimization Stories  247

Claude Lemaréchal

Cauchy and the Gradient Method  251–254

Richard W. Cottle

William Karush and the KKT Theorem  255–269

Margaret H. Wright

Nelder, Mead, and the Other Simplex Method  271–276

Jean-Louis Goffin Subgradient Optimization in Nonsmooth Optimization

(including the Soviet Revolution)  277–290

Robert Mifflin and Claudia Sagastizábal A Science Fiction Story in Nonsmooth Optimization

Originating at IIASA  291–300

Andreas Griewank

Broyden Updating, the Good and the Bad!  301–315

Hans Josef Pesch

Carathéodory on the Road to the Maximum Principle 317–329

Hans Josef Pesch and Michael Plail The Cold War and

the Maximum Principle of Optimal Control  331–343

Hans Josef Pesch

The Princess and Infinite-Dimensional Optimization  345–356
Computing Stories  357

David S. Johnson

A Brief History of NP-Completeness, 1954–2012  359–376

Robert Fourer

On the Evolution of Optimization Modeling Systems  377–388

Andreas Griewank

Who Invented the Reverse Mode of Differentiation?  389–400

Raúl Rojas Gordon Moore and His Law:

Numerical Methods to the Rescue  401–415
More Optimization Stories  417

Thomas M. Liebling and Lionel Pournin Voronoi Diagrams and Delaunay Triangulations:

Ubiquitous Siamese Twins  419–431

Konrad Schmüdgen

Around Hilbert’s 17th Problem  433–438

Michael Joswig

From Kepler to Hales, and Back to Hilbert  439–446

Matthias Ehrgott

Vilfredo Pareto and Multi-objective Optimization  447–453

Walter Schachermayer

Optimisation and Utility Functions  455–460