# 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.