D. Ray Fulkerson

August 14, 1924 – January 10, 1976

Brief Biography

Delbert Ray Fulkerson was a pioneer in large-scale linear programming and combinatorial optimization who helped lay the foundation for the study of network flows. Born and raised in southern Illinois, Fulkerson was brought up in a family of educators. Both of his brothers received doctorates and his father was a celebrated teacher in the area. Fulkerson graduated high school at sixteen years old and enrolled at Southern Illinois University. He left after one year to serve in the U.S. Army Air Corps, during which time he attended a program at the University of Wisconsin and studied meteorology. Fulkerson returned to school full-time in 1946, earning a bachelors the following year at SIU and choosing to pursue graduate study at Wisconsin. He earned a PhD in algebra under the supervision of Cyrus MacDuffee in 1951.

Shortly after, Fulkerson joined the Mathematics Department of the RAND Corporation in Santa Monica, California. His RAND colleagues included George B. Dantzig, Merrill M. Flood, Philip Wolfe, and Lloyd Shapley. Fulkerson was introduced to linear programming by Flood, Dantzig, and Albert W. Tucker. In 1954, he, Dantzig, and Selmer M. Johnson demonstrated the efficacy of cutting planes for the traveling salesman problem. Their article on the subject is one of the major milestones in the history of combinatorial optimization. At RAND, Fulkerson fostered a long, collaborative relationship with Lester R. Ford, Jr. He and Ford demonstrated how to determine the maximum flow with their max-flow min-cut theorem that states: for any capacitated network with a single source and sink the maximal amount that can flow from the source node to the sink node is equal to capacity of the minimum cut.  This laid the foundation for their seminal book, Flows in Networks (1962), the first unified treatment of network flows.

Much of Fulkerson’s work was inspired by real world problems that required OR solutions. In the natural gas industry, for instance, there were a number of computational challenges that motivated him to develop the out-of-kilter algorithm. Always searching for interesting applications of network theory, Fulkerson used network flows to obtain constructive proofs of known results in combinatorics.

Fulkerson enjoyed his time at RAND and found the community of friends and collaborators ideal for conducting exciting research. For example in the 1950s there were often contests to test whose algorithms were the fastest by sitting down and hand-calculating solutions. As the RAND budget tightened in the late 1960s, however, research support significantly declined. Fulkerson fought for the preservation of the Department’s culture and integrity, but ultimately left frustrated in 1971, joining the faculty at Cornell University.

Fulkerson enjoyed getting to know and spend time with his students, frequently dining and openly discussing a number of subjects with them. Fulkerson was unfortunately diagnosed with Crohn’s disease shortly after his arrival at Cornell and was only able to teach for five years before his untimely passing.

For his seminal contributions, Fulkerson was awarded the Lester R. Ford Award (named after the father of his close friend and frequent collaborator) by the Mathematical Association of America (MAA). MAA and the Mathematical Programming Society jointly established the D. R. Fulkerson Prize in Discrete Mathematics in his Honor. In 2005, Fulkerson was elected into the International Federation of Operational Research Societies’ Operational Research Hall of Fame.

Other Biographies

Profiles in Operations Research: D. Ray Fulkerson
INFORMS Members may access this book for free by logging in.
For more information about this title and many other Springer publications in Operations Research, please click here.

Wikipedia Entry for D. R. Fulkerson

Bland R. G. & Orlin J. B. (2005) IFORS' Operational Research Hall of Fame Delbert Ray Fulkerson. International Transactions in Operational Research, 12(3): 367-372. (link

Cornell University Operations Research and Information Engineering. Colloquia, Lectures, and Seminars: D. R. Fulkerson. Accessed April 8, 2015. (link)

Chvatal V. (1976) D. Ray Fulkerson's Contributions to Operations Research. Mathematics of Operations Research, 1(4): 311-320. (link)

Education

Southern Illinois University, BS 1947

University of Wisconsin, MS 1948 

University of Wisconsin, PhD 1951 (Mathematics Genealogy)

Affiliations

Academic Affiliations
Non-Academic Affiliations

Key Interests in OR/MS

Methodologies
Application Areas

Obituaries

Bechhofer R. E., Billera L. J., & Lucas W. F. (1976) Delbert Ray Fulkerson. Cornell University Faculty Memorial Statement. Economics Library, Cornell University: Ithaca, NY. (link)

Awards and Honors

Lester R. Ford Award 1976

IFORS' Operational Research Hall of Fame 2005

Selected Publications

Dantzig G. B., Fulkerson D. R., & Johnson S. M. (1954) The solution of a large-scale traveling salesman problem. Operation Research, 2(4): 393-410.

Ford Jr. L. R. & Fulkerson D. R. (1956) Maximal flow through a network. Canadian Journal of Mathematics, 8(3): 399-404.

Ford Jr. L. R. & Fulkerson D. R. (1957) A simple algorithm for finding maximal network flows and an application to the Hitchcock problem.Canadian Journal of Mathematics, 9(2): 210-218.

Dantzig G. B., Fulkerson D. R., & Johnson S. M. (1959) On a linear-programming, combinatorial approach to the traveling salesman problem. Operations Research, 7(1): 58-66. 

Fulkerson D. R. (1961) An out-of-kilter method for minimum cost flow problems. Journal of the Society for Industrial and Applied Mathematics, 9: 18-27.

Ford Jr. L. R. & Fulkerson D. R. (1962) Flows in Networks. Princeton University Press: Princeton, NJ. 

Fulkerson D. R. (1966) Flow networks and combinatorial operations research. American Mathematical Monthly, 73(2): 115-138.

Edmonds J. & Fulkerson D. R. (1970) Bottleneck extrema. Journal of Combinatorial Theory, 8: 30-44.

Fulkerson D. R. & Weinberger D. (1975) Blocking parts of polyhedra arising from network flows. Journal of Combinatorial Theory, Series B, 18: 265-283.

Fulkerson D. R. & Harding G. (1977) Maximizing the minimum source-sink path subject to a budget constraint.Mathematical Programming, 13(1): 116-118.

Additional Resources

American Mathematical Society. Prizes and Awards: Delbert Ray Fulkerson Prize. Accessed April 8, 2015. (link)

Chvatal V. (1976) D. Ray Fulkerson's contributions to operations research. Mathematics of Operations Research, 1(4): 311-320. (link)