Category: People

On the Shoulders of Giants

Yesterday I was messing around with The Mathematics Genealogy Project and I learned that Anna Nagurney, among others, is a not-so-distant cousin.  That inspired me to shoot off a couple of emails trying to trace my history farther back.

To recap, my advisors were Don Ratliff and John Bartholdi.  John was a student of Don, so Don is both my father and grandfather, a situation that would certainly raise eyebrows outside of academia.  Don’s advisor was Manny Bellmore who did a lot of fundamental work in the late 1960s and 70s on the traveling salesman problem and various other optimization problems.  Manny’s advisor was Frederick (Tom) Sparrow, who did extensive work in energy modeling and policy, among other things.  Bellmore also worked with George Nemhauser, but George was on leave in England when Manny graduated, so Sparrow was the advisor.  It is through Sparrow that I am related to Nagurney.

To continue earlier in history, I shot off an email to Tom, who is emeritus from Purdue.  Fortunately my email got through the spam filters (starting an email “Hello Great-Grandfather” does make it sound like a plea from a Nigerian prince), and he could tell me about his advisors.  He had two  The first was an economist named Kenneth Boulding.  This is a name I should know but do not.  He did some fundamental work in systems science and conflict analysis starting in the mid-1950s with some papers that are incredibly well cited.  When the wikipedia description begins with:

Kenneth Ewart Boulding (January 18, 1910 – March 18, 1993) was an economist, educator, peace activist, poet, religious mystic, devoted Quaker, systems scientist, and interdisciplinary philosopher

it is clear we are talking about someone unusually interesting.

Tom’s other advisor is, however, known to me (as it is to many in operations research):  Merrill Flood (1908-1991).  Flood was a founder of the field of operations research.  He worked on transportation problems in the 1930s and developed the “Northwest Corner” rule for finding a solution to such problems, before Dantzig developed a general method for optimizing these problems.  He also was an early researcher on the game-theory problem Prisoner’s Dilemma.  He was also an influential popularizer of the Traveling Salesman Problem.   He was the second President of TIMS, and he received the Kimball Medal for services to the field (a designation I have the honor to share with him).

Flood happens to be in the Mathematics Genealogy Project (though without listed advisees) and his advisor was Joseph Henry Maclagan Wedderburn (1882-1948), Scottish-born algebraist who taught at Princeton for most of his career.  Wedderburn’s advisor was George Chrystal (1851-1911),  whose advisor was James Clerk Maxwell (1831-1879), father of electromagnetic theory!  Checking out his wikipedia article leads to the immortal verse:

Gin a body meet a body
Flyin’ through the air.
Gin a body hit a body,
Will it fly? And where?

Going back from Maxwell, we get William Hopkins (1793-1866), who combined mathematics with geology.  I love the wikipedia entry on his private life:

Hopkins enjoyed music, poetry and landscape painting. He spent the end of his life in a lunatic asylum in Stoke Newington. He died there of chronic mania and exhaustion.

Perhaps not an unusual ending for mathematicians.

Back from there we get Adam Sedgwick (1785-1873), a founder of geology.  He had two advisors:  Thomas Jones (1756-1807) and John Dawson (1734–1820), a mathematician and surgeon.  Dawson leads to Edward Waring (1736-1798), a Lusasian Professor of Mathematics.

On the Jones side, we get two advisors: John Cranke (1746-1816) and Thomas Postlethwaite (1731-1798).  Fortunately Cranke was the student of Postlethwaite, so we don’t branch (making an already large lineage even bushier).  At this point we hit two Cambridge tutors:  Stephen Whisson (?-1783) and Walter Taylor (c1700-1743).  Taylor was trained by Robert Smith (1689-1768), known as Old Focus for his work in optics.  Smith leads to Roger Cotes (1682-1716), who worked closely with his advisor… Sir Isaac Newton!  That makes Sir Isaac my Great-Great-Great-Great-Great-Great-Great-Great-Great-Great-Great-Great-Great-Grandfather (academically speaking).

From Philosophiæ Naturalis Principia Mathematica to A Dynamical Theory of the Electromagnetic Field to trying to schedule 8 team sports leagues in a mere 15 generations. On the shoulders of giants indeed!

I suspect that if the system was completely filled in, we would all be descendants of Newton.  But I am walking a little taller today, and feeling a bit more pressure in my research, knowing of my illustrious ancestors.

IBM, Ralph Gomory and Business Analytics

Had a post at the INFORMS Conference site on Ralph Gomory:

For those of us taking a break from the INFORMS conference, the Master’s golf tournament holds special attention. Not for the golf (though the golf is wonderful), but for the commercials. Practically every commercial break has an IBM commercial featuring some of its luminaries from the past. Prominent among them is Ralph Gomory. Everyone in operations research knows of Ralph. For the optimization-oriented types, he is the Gomory of Gomory cuts, a fundamental structure in integer programming. For the application-oriented types, he was the long-time head of research for IBM. For the funding and policy-oriented types, he was the long-time head of the Alfred P. Sloan Foundation supporting analysis on globalization, technology, and education. Great career, when you can be highly influential three different ways (so far)!

During his time at IBM, Ralph stressed the need for research and development to work together. This view that research should be grounded in real business needs is one that I think has greatly strengthened areas such as operations research and business analytics. While there is no dearth of theoretical underpinnings in these areas, the fundamental research is better by being guided by practical need. This has led to the insights that give us fast optimization codes, stronger approaches to risk and uncertainty, and the ability to handle huge amounts of data.

There is a full version of the IBM video that lasts about 30 minutes (currently on the front of their Smarter Planet page). Ralph shows up in the introduction, then around 24:43 in an extended discussion of the relationship between research and business need, and again near the end (30:08).

This conference would have been a lot different (and less interesting) without the career of Ralph as a researcher, executive and foundation leader. We are lucky he began in operations research.

Another Operations Research Dean

Sunil Kumar, currently at Stanford, has been named Dean of the University of Chicago Booth School of Business.  Sunil’s research has been in manufacturing, stochastic control, queueing networks, and related areas, making him clearly an operations research person (and of course he is a member of INFORMS).  He is an area editor of Operations Research, a position I suspect he will be giving up shortly.

It is amazing how often the field of operations research leads to academic administration.  Congrats Sunil!

A Kiwi on the Move

I spent 2007 visiting the University of Auckland, living on the wonderful (and strange) island of Waiheke, and I have about a thousand pictures online to prove it.  We had a wonderful year, and loved the university, the island, the city, and the country.  So it is with some jealousy that I note that Tava Olsen, formerly of Washington University, St. Louis, has taken up a position at the University of Auckland as the Ports of Auckland Chair in Logistics and Supply Chain Management.

Tava’s family also lived on Waiheke and we visited with her on the island a couple times during the year we were there.  David Ryan, who has done great work in airline scheduling and branch-and-price, has a place on the island.  Garrett van Ryzin lived on the island during his sabbatical year.  With just under 8,000 people, Waiheke has to have one of the larger “output of operations research per capita” values in the world!

I think to celebrate her new Chair, Tava should invite all of us to Waiheke for a nice glass of wine.  Congratulations, Tava!

David Johnson to Receive Knuth Prize

AT&T Labs researcher David Johnson will receive this year’s Knuth Prize from the ACM “for his contributions to theoretical and experimental analysis of algorithms”.  While Johnson is best known for his NP-Completeness book with Michael Garey, he has had an extraordinarily influential career in both the theory of approximation algorithms and in research on experimental evaluation of algorithms.  From the announcement:

The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2009 Knuth Prize to David S. Johnson of AT&T Labs for his contributions to theoretical and experimental analysis of algorithms.  Johnson’s innovations helped lay the foundation for algorithms used to address optimization problems, which involve the process of finding the best solution from all feasible solutions.  In addition, Johnson made many contributions to the early development of NP-completeness theory, which helps identify those problems that are hard to solve efficiently. The Knuth Prize, named in honor of Donald Knuth of Stanford University who has been called the “father” of the analysis of algorithms, will be presented at the ACM Symposium on Theory of Computing (STOC) June 6-8, 2010, in Cambridge, MA, where Johnson will present the Knuth Prize Lecture.

I got to know David almost 20 years ago when I agreed to coordinate one of his DIMACS Implementation Challenges.  This cooperation resulted in a book and, a decade later, a special issue of Discrete Applied Mathematics (with Anuj Mehortra). These Challenges are one of the ways David has explored issues in the evaluation of algorithms.  I had the chance recently to give a presentation on the effect of those Challenges.  David has had an enormous influence on me as I think about how to provide a firmer underpinning to the experimental analysis of algorithms and the way individuals and a field report on results.  This Prize makes me wish I had more time to spend on completing a planned system for reporting and confirming computational results.

I guess I am only surprised that David hadn’t already won this prize!  Very well deserved.

Operations Rules the National Academy of Engineering!

I see from Anna Nagurney’s blog that three operations research people have been elected to the National Academy of Engineering:

This group includes INFORMS (Institute for Operations Research and the Management Sciences) members: Dr. Cynthia Barnhart, the Associate Dean of Engineering at MIT, Dr. Hau Lee, of the Stanford Graduate School of Business, and the former editor of the journal Management Science, and Dr. William Pulleyblank, a Vice President of IBM.

This is a very well deserved honor for the three of them.

The Magical Places Operations Research Can Take You

Art Benjamin of Harvey Mudd College has an article in this week’s Education Life section of the New York Times where he gives ten mathematical tricks.

I first met Art in the late 80s at, I believe, a doctoral colloquium sponsored by ORSA/TIMS (now INFORMS). Art was clearly a star: he won the Nicholson Prize (Best Student Paper) in 1988. If he had stuck with the “normal path” of being an academic researcher, I have no doubt that he would now be well known in operations research academia.

But his real passion was lightning calculation and other forms of mathematical magic and in keeping with that path, he has made himself even better known to a much broader audience. He has published three books aimed at the general audience, including one that was a Book-of-the-Month Club selection (is this unique in operations research?). He has an amazing act that he performs for a wide range of audiences.

His research has moved out of operations research  into combinatorics and combinatorial games (though these areas have a lot of overlap with OR), where he publishes prolifically and has two books aimed at professionals. His book “Proofs that Really Count” (along with Jennifer Quinn) is a great introduction to combinatorial proofs.

Art is another example of the variety of paths you can take after an operations research degree.

Congratulations to Tom Magnanti

magnantiTom Magnanti has been appointed President of the Singapore University of Technology and Design, Singapore’s so-called “fourth university”.  Tom, of course, is one of the preeminent researchers and administrators in operations research.  He has written lots of influential papers and books.  His book with Bradly and Hax on Applied Mathematical Programming had a huge effect on me (take that Russ Ackoff) and is the sort of book the field badly needs now.

Tom was President of INFORMS while I was on the Board (he was President two before me, so we had some pretty in-depth interactions) and he was President of IFORS when I joined that board.  I know him well and he is a heck of a nice (and effective!) guy.

The new university is an exciting operation:  what would you do if you were given free reign to create a top-notch engineering and design school from scratch?  Tom, with his experience as Dean of Engineering at MIT, is a fantastic choice to lead this endeavor.  It is great to have an operations researcher in charge, and Tom is another example of operations research as a path to administrative success.

Operations Research is Taking Over the World

I often have postings that so-and-so from the world of operations research has become a dean or a provost or even a university president. Somewhat more rarely, I can talk about an operations researcher as a baseball player. Operations Research can lead to lots of jobs.

hatoyamaIt can even lead to becoming Prime Minister of the country with the world’s second largest economy. Yukio Hatoyama, Prime Minister designate for Japan, is not just trained in operations research but has a Ph.D. from Stanford in the subject. A search at google scholar suggests that his work was in the area of stochastic models in reliability, though it appears that his academic career was cut short (the google scholar counts suggest fairly … limited interest in his academic work). From an article in the Telegraph (UK):

Yet although Hatoyama refers jokingly to high office as “the family business”, he originally sought to avoid political life. After graduating from Tokyo University he completed an engineering PhD at Stanford University, and was set for an academic career in the US. However, his time in America coincided with the nation’s bicentenary, in 1976, and the presidential election that saw Gerald Ford replaced by Jimmy Carter. For the impressionable 29 year-old, it was an astonishing experience: such changes of government simply didn’t happen in Japan, where, despite political and monetary scandals, his grandfather’s party had remained in power since 1955.

The AP article has a nice one line definition of operations research:

Hatoyama knows the U.S. well, having obtained three postgraduate degrees from Stanford, including a doctorate in operations research, which consists of using mathematical and scientific models to make decisions within organizations.

Congratulations, Dr. Hatoyama! Now show the world how operations research training can be translated into political and economic leadership.

IFORS Distinguished Lecturer Christos Papadimitriou

bonn09 034Christos Papadimitriou of UC Berkeley was the IFORS Distinguished Lecturer at the EURO Meeting yesterday (in the fuzzy picture, he is getting his award from IFORS President Elise del Rosario), and gave a very fine lecture on “Computing Equilibria” (and Sex, though that was not in the formal title).   The starting point for his lecture was to note that the internet has greatly increased interest in multi-player games.   Christos described the Internet as the first computational artifact that was never truly designed:  it was formed by the selfish behavior of millions of agents.  To quote Scott Shenker:

The Internet is an equilibrium, we just need to identify the game

But how do players in a game find an equilibrium?  For simple zero-sum games, linear programming can find an equilibrium.  For non-zero sum games, John Nash in 1950 proved an equilibrium exists, but his proof is nonconstructive (and is essentially equivalent to Brouwer’s fixed point theorem).

This issue of finding equilibria often comes up in coffee conversations with my colleagues.  Economists love the beauty of their theorems, but I get frustrated when they claim what they do has real-world relevance when their actors have super-real capabilities.  As Christos quoted:

if your laptop can’t find it, then neither can the market

But, they complain, it is really a bunch of different actors, so perhaps the quote should be “if a million laptops can’t find it, then neither can the market”, but that doesn’t affect things very much.  Given the lack of computational methods for finding equilibrium in any but the simplest games and markets, it seems reasonable to worry about the advisability of relying on the assumption that people in real markets can magically find equilibria.   In fact, Christos has a theorem on price adjustment mechanisms that shows that sometimes these cannot clear markets in anything less than exponential time.

After the romp through computational methods for finding equlibria, Christos moved on to Sex (that should increase my google visibility!).  Why do creatures have sex?  What is the advantage?  Biologists have looked at this problem but don’t have a really satisfactory solution to it.  Christos was motivated by his experience with computational methods for optimization:

Why do Simulated Annealing algorithms work, while Genetic Algorithms don’t?

Audible gasps came from the sizable group of GA researchers in the audience.  I’ll remind readers this is Christos’ view not mine (though I certainly believe that anyone doing work on GAs for the traveling salesman problem, as an example, who believes they are helping solve TSPs is misguided, but I have seen applications where GAs seem the right approach).

bonn09 032Christos’ fundamental point is that perhaps selection under recombination does not maximize fitness.  Instead, it favors “mixability” (or genetic tolerance).  And this mixability accelerates speciation, and accelerates evolution.   There is a paper in the Proceedings of the National Academy of Science that explains this all in more detail.

Christos’ home page has lots of the papers that underlie the talk (see, particularly, the “computing equilibria” and “biology” subsections).  Highly recommended!