Trustees elect Professor David Shmoys the Laibe/Acheson Professor of Business Management and Leadership Studies

At its recent meeting, the Cornell University Board of Trustees elected David B. Shmoys the Laibe/Acheson Professor of Business Management and Leadership Studies.

"David is an absolute lynchpin of ORIE," said former ORIE Director Adrian Lewis, "devoting his extraordinary energy and insight to the full spectrum of our enterprise - scholarship, undergraduate and M.Eng. and Ph.D. teaching, mentoring of junior faculty, administration, leadership and collegiality."

In 1989 Shmoys joined ORIE from MIT, where he had been an assistant and associate professor.  He received his Ph.D. in computer science from the University of California at Berkeley, and his B.S.E. in electrical engineering and computer science from Princeton University.

Research

Shmoys has achieved worldwide recognition for his contributions to the theory, design and analysis of efficient algorithms for discrete optimization problems. Such problems arise in many practical applications, such as scheduling interdependent operations, design of transportation and telecommunications networks, and land management for wildlife. For one of these applications, that of scheduling exams to minimize the number of students who have three final exams in a 24-hour period, Shmoys, ORIE Professor Robert Bland, and OR Ph.D. student Dmitriy Levchenko developed a solution approach that is now routinely employed at Cornell.

Although much of his work relates to devising approximation algorithms for discrete deterministic optimization problems, Shmoys describes his research interest as "eclectic," covering a wide range of optimization models, both discrete and continuous, deterministic and stochastic, and ranging from directly applicable to deeply theoretical.

• As an example of work on directly applicable discrete deterministic models, Shmoys (jointly with ORIE Professor Shane Henderson, OR Ph.D. student Tim Carnes, and collaborators on the staff of the client organization) devised an approach to optimizing the provision of non-urgent air ambulance transport service among medical facilities in the province of Ontario, Canada. They developed a tool that combines an Excel spreadsheet user interface, specialized code, and commercial optimization software, to find – in real-time -- the best combination of aircraft, patients and routes to satisfy each day’s service demand.  

The tool takes into account daily service requests, available aircraft, a complex route-based cost structure and “a number of complicating side constraints.” It is a discrete (integer) optimization problem, since each possible route is either used or not used, i.e., fractional solutions cannot be implemented. The researchers project that the tool will yield a cost savings of more than 16% over the previous manual approach and are working to refine the approach to come closer to this projected improvement in practice. 

• Another example concerns settings in which (worst-case) performance guarantees can be obtained for problems in which randomness is a central element, in particular uncertainty about future demand.  This research example brings new theoretical insights to bear on the classic operations research problem of coordinating a sequence of orders for a single commodity, aiming to satisfy demand that varies statistically, so as to minimize average (expected) total cost over time. In his work on this problem Shmoys collaborated with ORIE Professor Emeritus Robin Roundy and two Cornell Ph.D. graduates: Retsef Levi, who is now at MIT, and Martin Pál, who is now at Google.

When the probability distribution of demands does not change over time and demands are not correlated across time periods, computational approaches based on dynamic programming can readily produce optimal policies specifying how much to order and when.   But in many real-world cases, forecasts of demand evolve over time, subjecting dynamic programming approaches to “the curse of dimensionality” under which the task of computing the optimal policy grows beyond the capability of even today’s fastest computers. Hence planners must settle for approaches that yield approximations of the optimal value, i.e., heuristics. Unfortunately it is usually not known how close heuristic solutions come to the optimal expected value. 

Shmoys and his coauthors have devised a new algorithmic approach to these problems, employing an innovative cost-accounting scheme and a novel way to balance holding and backlog costs so that the resulting objective function value is proven to be at most twice the optimum value. A follow-up paper shows that refinements of this balancing scheme not only have the same theoretical properties, but find solutions superior to those found by ad hoc heuristics commonly used by practitioners.

• A third example provides new theoretical results for the iconic traveling salesman problem, in the form of finding the shortest route for a salesperson to go from one point to another while visiting every point along the route exactly once. This is a discrete optimization problem that typically does not incorporate uncertainty. 

For this problem, Shmoys, OR Field member Robert Kleinberg, and their joint Ph.D. student Hyung-Chan An developed an approximation algorithm that is an improvement on the algorithm that had stood for twenty years as having the best ratio between the value of the approximate solution and the value of the (unknown) optimal solution. Their new algorithm in fact achieves the so-called Golden Ratio that arises in nature and in art.  While the improvement brought about by the new algorithm is not dramatic, the approach provides insights into a wide class of discrete optimization problems.

With ORIE Professor David Williamson, Shmoys has written the definitive work, The Design of Approximation Algorithms, on efficient algorithms that find provably near-optimal solutions and provide among the best approximations known. He has published between one and four papers each year for more than 25 years. His work has been cited more than 13,000 times. Shmoys believes that there is important interplay between theory and practice for Operations Research: “I like to study stylized models for which one can prove theorems about the performance of algorithms, either as a means to explain the performance of known approaches, or even better, to be led to new algorithmic paradigms that can be applied much more generally for real-world problems, to obtain improved results in practice,” he said.

Service

While maintaining a full teaching load, Shmoys is a founding co-Director of the Undergraduate Program in Information Science, Systems, & Technology, and Associate Director of the NSF-funded Cornell Institute for Computational Sustainability. He was an organizer for the first international conference for the Institute, uniting researchers in ecology in ecology, geology, wildlife, economics, physics, engineering, mathematics and computer science in a way that introduced practitioners to a range of mathematical and computational tools, and theorists to fascinating new problems.

He is co-Chair of the Academic Planning Committee for Cornell NYC Tech. In this role, he guides program strategy, coordinates workshops, provides liaison with the leadership of the Technion, and guides degree programs proposed for the new campus towards approval.

Shmoys and his wife, OR Field Member and Jacob Gould Schurman Professor Éva Tardos, have two daughters, Rebecca, who just graduated from college, and Amy, a rising junior at Ithaca High School.

Laibe and Acheson

John W. Laibe '50 is the former chairman of Acheson Industries, a manufacturer of electronic chemicals that later became a subsidiary of Imperial Chemical Industries (ICI), which is now in turn a subsidiary of Dutch conglomerate AkzoNobel.  In memory of his classmate Howard A. Acheson Jr. '50, Laibe and Acheson Industries endowed the Laibe/Acheson Professor of Business Management and Leadership Studies.

This chair (with a slightly different name) was previously held by Jack Muckstadt, who upon his retirement earlier this year became the Acheson/Laibe Professor Emeritus of Business Management and Leadership Studies.