David Shmoys
Embracing complexity to solve difficult problems
The first time David Shmoys set foot on the Cornell campus, he had just completed his third year of high school and he was in Ithaca to take two full semesters of college calculus in one short summer. “I loved it. It made me see that mathematics was certain to play a part in my future,” says Shmoys, (now almost 40 years into the future he was then just starting to think about.) “I made friends that summer that I have had for life. In addition, I felt truly challenged for the first time.”
In a way, that summer tells you all you need to know about David Shmoys in order to have a good sense of the man. He loves math, (the more challenging the better), and connections with people are essential. “As a teenager there was a real tension in me between wanting to immerse myself in math, on the one hand, and wanting to have a direct impact on the world, on the other,” says Shmoys. In Shmoys’ long academic career at Cornell’s School of Operations Research and Information Engineering (ORIE), he has struck an excellent balance between these two wishes.
And in striking that balance, he has managed to create algorithms to solve problems in some surprising domains. Shmoys has had a direct impact on the final exam schedule at Cornell, on land purchases made by a conservation group in North Carolina, on the routing of air ambulances in Ontario, and on the proper distribution of bicycles in New York’s Citibike program, just to name a few areas where Shmoys has had an impact.
“There is a clear moment I can recall that set me on this course,” says Shmoys during a recent conversation in his Rhodes Hall office. “It was the fall of 1978 and I was in Professor Harold Kuhn’s class at Princeton. Professor Kuhn proposed a hypothetical situation about President Jimmy Carter’s political future. The situation was based in the real world and brought mathematics and an algorithmic sensibility to bear. I was hooked.”
Computers have been getting more powerful and algorithms have improved since that day in 1978. Optimization problems that were viewed at that time as far beyond what could potentially be solved, can now be solved routinely in hours, minutes, or even fractions of a second. As technologies and algorithms improve, the kinds of problems that can be addressed expand. To explain some of the complexities involved, Shmoys talks about what is called the Travelling Salesman Problem. It sounds pretty basic when you first hear it, but then the complexity becomes clear. In the scenario, a sales representative has a roster of cities to visit. The challenge is to find the optimal route for the salesperson to take. Easy if there are just three cities; but what if there are 300, or 300,000?
It turns out that the sort of algorithm necessary to solve a problem like that confronting the traveling salesperson is the same sort of algorithm that underlies the success of the Human Genome Project, in which millions of overlapping fragments of an individual’s genome need to be reassembled in the most likely way. In many cases, clever heuristics can be designed that produce solutions that, while not the best, are almost as good. Even more remarkable, sophisticated algorithms can sort through the exponentially large number of combinations, quickly ruling out less promising ones, so that with well-engineered computer code, it is possible to find the optimal solution in a reasonable amount of time.
The traveling salesman problem is a so-called deterministic problem; there is an input that is known in advance, and then you want to compute the best solution. But this is not always the case – often one is computing a solution with only a partial view of the situation at hand, which will evolve over time in an unpredictable way. One approach to modeling this uncertainty is through the mathematical language of probability, and this gives rise to the concept of a stochastic optimization problem. But both finding good models for practical decision-making, and then computing good solutions to these sorts of models presents further challenges. These types of challenges are the very problems David Shmoys likes best.
New York’s Citibike bicycle sharing program is a perfect example of this sort of scenario. There are a finite number of stations where bikes are available, but there are many factors that go into how many of these bikes are used, when they are used, where they are dropped off, and where to place them for the next morning. Weather plays a role, special events in the city play a role, traffic plays a role. For the program to be a long-term success, managers need to have bikes where they are needed, without fail. And for this to happen, they need a good model to base their decisions on.
This is where David Shmoys and his fellow researchers come in. “I was involved in designing Cornell’s Big Red Bike bicycle sharing program, so I had an inkling that there are some interesting OR aspects to ventures of this sort. Just as the Citibike program was going to launch on Memorial Day weekend in 2013 we were in touch with them, and this led to an immediate collaboration.” Right away, Shmoys and other Cornell ORIE faculty and students were able to help them sort out some of the short-term logistical problems. It was the start of a beautiful friendship.
“Any OR professional who wants their work to have impact dreams of a set up like the one I have with Citibike,” says Shmoys. “It is a real collaboration. They tell us their actual problems, they share their data freely, and they listen to the solutions we come up with—both traditional and out-of –the-box suggestions. Over the next month or two, they will be establishing more docks in Brooklyn and Queens and they are using our models to help guide the decision of how many docks to place at each station.” As Shmoys discusses the Citibike program and his work with them, his smile makes it clear that his high school wish has come true.