I heard the sad news via a tweet by Professor Laura McLay @lauramclay - Professor Harold Kuhn of Princeton University passed away on July 2, 2014 at the age of 88. The Nobel laureate Al Roth of Stanford wrote this tribute to this co-founder of nonlinear programming and brilliant game theorist, who, interestingly, was a mathematician but had an appointment in Princeton's Economics Department.
Anyone working, on, researching, or learning about our nonlinear world is aware of the powerful tool of nonlinear programming and the renowned Kuhn-Tucker optimality conditions, now commonly referred to as the Karush-Kuhn-Tucker or KKT Theorem. Dick Cottle of Stanford wrote a wonderful history of these scientific discoveries which can be read here.
Although I never met Karush, Kuhn or Tucker, my first academic interview when I was finishing my PhD in Applied Math at Brown with a specialization in Operations Research, was at SUNY Stony Brook, and I was interviewed by Al Tucker's son, Al Tucker, Jr., so, of course, we talked about his father. Al Tucker passed away in 1995.
This very same week, on July 5, 2014 we celebrated the 90th birthday of Professor Martin Beckmann, the only surviving author of the classic 1956 book, Studies in the Economics of Transportation, who was on my doctoral dissertation committee at Brown University.
I wrote about Beckmann's milestone birthday on this blog and sent his a special card. More information on this classic, including a special festchrift I organized at a previous INFORMS conference in San Francisco can be viewed here.
The massive impact of this book, which formalized what we now commonly refer to as user-optimization and system-optimization to capture different behaviors on congested network systems, with a focus on urban transportation networks, was summarized in our paper, A Retrospective on Beckmann, McGuire and Winsten’s Studies in the Economics of Transportation David E. Boyce, Hani S. Mahmassani, and Anna Nagurney, Papers in Regional Science 84: (2005) pp 85-103.
In their book, on page 59, they stated: “Demand refers to trips and capacity refers to flows on roads. The connecting link is found in the distribution of trips over the network according to the principle that traffic follows shortest routes in terms of average cost. The idea of equilibrium in a network can then be described as follows: ... the existing traffic conditions are such as to call forth the demand that will sustain the flows that create these conditions.” And, as we noted in the paper, That these authors succeeded to formulate and extensively analyze a nonlinear optimization problem whose optimality conditions correspond to this statement (and related behavioral assumptions) was an enormous advance in the rigorous modeling of network traffic, a result never before achieved for urban traffic, and most unlikely for any complex system involving interactions of human behavior with technology. Moreover, they provided a parallel model and analysis for the case of cost-minimizing (now called system optimum) flows in a congested traffic network.
Below I depict congestion on a link where the travel time or cost is an increasing function of the flow.
Congestion is a huge problem in the US an beyond. As I noted in my TEDX talk at UMass last November: Congestion costs continue to rise: the cost of congestion has risen from $24 billion in 1982 to $121 billion in 2011 in the United States. The average commuter spent an extra 38 hours traveling in 2011, up from 16 hours in 1982. In areas with over 3 million persons, commuters experienced an average of 52 hours of delay in 2011. In 2011, 2.9 billion gallons of wasted fuel -- enough to fill 4 New Orleans Superdomes.
Congestion is neither a new phenomenon - it even occurred in ancient Roman times during which time of day chariot policies were used to ameliorate congestion.
Information on some of the most congested roads in the US is available here.
More data can be found in the always fascinating Texas Transportation Institute's Urban Mobility report.
Neither is congestion, and associated nonlinearities, limited to urban transportation systems, but they also arise in freight systems, electric power generation and distribution networks, and the Internet!
Many, many thanks to Kuhn, Tucker, Karush, and, of course, to Martin Beckmann for providing us with some of the tools to model and better understand our nonlinear world!
Posts
