Hoods Attest to Mastery of the Process of Advancing the Science of Operations Research
The 2016 ORIE Graduation Ceremony included a tradition dating back to medieval times at universities such as Cambridge, Oxford, Bologna and Paris. The academic regalia worn to the event by four Ph.D. candidates - Sin Shuen Cheung, Kenneth Chong, Daniel Fleischman, and Jialei Wang - was augmented by hoods placed by faculty members. These hoods are trimmed in dark blue to represent the degree of Doctor of Philosophy in any field – in this case the field of Operations Research. These new PhDs have demonstrated their mastery of the process of advancing science through contributions to different approaches to optimization, as applied to such problems as locating facilities, deploying ambulances, comparing bacterial chromosomes, planning delivery routes, finding peptides with desired properties, and designing aircraft wings and other airfoils.
Sin Shuen Cheung was born in Shandong, China. She received a B.S. in mathematics from the University of Science and Technology of China and an MPhil in Engineering Management from the Chinese University of Hong Kong before joining ORIE for her Ph.D., which she received in January, 2016. She returned to Ithaca for the 2016 Graduation Ceremony.
Her dissertation research, advised by David Williamson, deals with a classic problem in Operations Research- the facility location problem, in which the optimal set of locations to serve a set of customers is to be selected. This is not only an important problem in the real world, but has become an important area for computational and mathematical research. Research interest is partially due to the fact that facility location is in a class of intractable problems (called NP-hard), including the traveling salesman problem, for which it is not known whether an optimal solution can be found efficiently. Hence there is a focus on efficient algorithms to find approximately optimal solutions and to characterize how close in value these solutions can be guaranteed to be to the value of the (unknown) optimal solution. Cheung has developed such approximation algorithms for some important and practical variants of the facility location problem.
One of these variants takes into account possible economies of scale in constructing facilities, such as warehouses, to serve a set of customer locations. For example, if several facilities are to be constructed at the same time, there may be quantity discounts on the materials from which they would be built. Cheung has formulated a general model encompassing this situation, developed an approximation algorithm to solve it, characterized the quality of the result, and showed that there is a lower bound on how effective any efficient algorithm can be for this variant of the facility location problem.
In the classical facility location problem, all of the customers and their product demands are known in advance. Cheung has analyzed a variant in which customers arrive one-by-one, for example by placing orders online, and is either served by an existing open facility or is otherwise compensated or accommodated, at a cost. She developed an approximation algorithm that provides the best possible quality of solution relative to what would be possible if all of the customers were known in advance.
Cheung is also the winner of the 2015-16 Teaching Assistant of the Year award that is given by the undergraduate chapter of the Operations Research society, INFORMS. Because she was unable to attend the earlier award ceremony, she was presented with the award at the Graduate Ceremony, after being hooded by her advisor, Professor Williamson.
Cheung is now in the quantitative strategy group at Bank of America Merrill Lynch, supporting the pricing and analytical tools used for equity derivatives trading. She recalls really enjoying “the surroundings and the many things one can do in different seasons” at Cornell, where she learned rock climbing, sailing and skiing. “The people I met and worked with at Cornell were all very kind and helpful,” she says.
Kenneth Chong, who grew up in San Francisco, came to ORIE from the University of California, Berkeley, where he obtained a BS in Industrial Engineering and Operations Research. While at Berkeley he was a teaching assistant in a simulation course taught by Lee Schruben ‘68, former Andrew Schultz Jr. Professor in ORIE, who was “part of the reason I decided to go east for grad school,” Chong said.
In his dissertation research under the guidance of ORIE Professors Shane Henderson and Mark Lewis, Chong developed models for evaluating and benchmarking the performance of Emergency Medical Service (EMS) systems. EMS systems use both Advanced Life Support (ALS) and Basic Life Support (BLS) vehicles. ALS vehicles have more sophisticated equipment and more extensively trained staff, whereas more BLS vehicles can be deployed within a given budget, thereby improving overall response times.
Determining the best mix of vehicles entails a tradeoff between “decreasing the likelihood of inadequately treating high-priority calls, and improving the system’s overall responsiveness,” according to Chong. To quantify that tradeoff requires a measure of responsiveness, which in turn requires an understanding of where, for a particular mix of ALS and BLS vehicles, the vehicles will be deployed and how they will be dispatched. Chong formulated and analyzed deployment with a Markov Decision Process model and dispatch with an Integer Programming model. For both models, he combined theoretical results and the results of computations based on two years of Toronto dispatch data to provide insights into the effects of vehicle mix on system performance. In particular, he found that “there are rapidly diminishing marginal returns associated with biasing one’s fleet towards all-ALS vehicles.”
Many EMS systems also strategically relocate idle ambulances in real time so the system can better respond to new emergency calls that come in while other ambulances are away on earlier calls. Since “the problem of finding an optimal way to do so is computationally intractable,” Chong notes, he undertook to determine upper bounds on how well an optimal redeployment policy can possibly perform. The bounds he developed can serve as benchmarks against which heuristic (i.e., “rule of thumb”) methods can be measured, and can help determine whether redeployment can provide a sufficient increase in performance to warrant the added burden that such a policy places on medical personnel.
Since Chong’s advisors were unable to attend, ORIE Director David Shmoys placed his hood.
Chong is now a quantitative analyst at Google in San Francisco, where he is working on how Google’s fiber-optic infrastructure should be laid out to provide service to apartment buildings and condos. At Cornell “I liked the sense of community that the ORIE department has,” he says. “Everybody knows each other, professors are accessible, and we can be very casual when interacting with them and very casual with students.”
Daniel Fleischman came to Cornell from Rio de Janeiro, Brazil, where he received a Computer Engineering and Applied Mathematics B.SC. degree and an M.Sc. in Computer Science at the Pontifical Catholic University (PUC-Rio) there. He originally enrolled at PUC-Rio to begin a career as a game developer, but became involved in international algorithm design and programming competitions, advancing to World Finals as well as training hundreds of High School and College students to participate. In 2014 he coached six Cornell teams, and in 2015 he coached four Cornell teams, one of which won the Greater New York regional contest and traveled to the World Finals in Phuket, Thailand, where the only US teams finishing higher in the standings were from Harvard, MIT, and the University of Central Florida.
Fleischman joined Cornell as a Ph.D. student in 2010 in order to develop a deeper understanding of the mathematics behind algorithms. Most of his dissertation is devoted to algorithms that solve problems for which numerical solutions must have discrete (e.g., whole number) values in order to be meaningful. His algorithms produce solutions to these problems at speeds that are orders of magnitude faster than can be computed by the fastest previously known methods, without compromising solution quality.
Fleischman brings to his research a distinct philosophy: that the interchange between theory and practice can lead to algorithms that are both simple and implementable. “A simple algorithm requires more intuition about the problem being solved, and usually provides bigger insights on why the algorithm works,” he has written. He also believes that “you can gain a lot of intuition by looking at instances, formulating hypotheses and testing them. Let’s put science back in Computer Science,” he writes.
At the Graduation Ceremony, Professor David Shmoys placed Fleischman’s hood and congratulated him.
In his dissertation research, which was guided by Shmoys, Fleischman followed this philosophy in devising algorithms for three completely different problems. In the dissertation he advocates for his philosophy in describing how he came up with the algorithms.
- One of these problems deals with the analysis of strings of symbols, which occurs in, among other applications, computational biology- whether reconstructing long DNA sequences from fragments recorded in the laboratory, determining repeated subsequences, or finding the extent of similarity between two circular bacterial chromosomes.
- Another problem is a version of the well-known traveling salesman problem (find the shortest tour that serves a set of fixed destinations) in which there is a known chance some destinations may not require service and so can be skipped, while maintaining the original overall sequence for those that are served. His consideration of this version of the traveling salesman problem, which seeks the shortest expected tour, was motivated by a “Meals On Wheels” program in which the set of clients who should actually be served on a particular day is very volatile, since clients may die, get fed elsewhere, or resume the ability to prepare their own meals.
- The third problem deals with graphs – mathematical structures that consist of a set of points (nodes) connected in pairs by arcs (edges). Applications in areas as diverse as image processing, computer vision, integrated circuit layout, distributed computing, compiler optimization, workload balancing and route planning require evenly splitting the graph into two (and eventually more) equal-sized sets of nodes such that the edges between the sets have minimum total cost. To solve this general problem, which he worked on as a summer intern at Microsoft Research, Fleischman developed an algorithm that is practical for a wide range of applications. As a computational example he used his algorithm to optimally divide the US road network into two:
Fleischman’s algorithm solved this example, with 24 million nodes and 29 million edges, to optimality in a total of 12 days of processor time on a connected cluster of 100 powerful personal computers. The number of nodes in this example is several orders of magnitude greater than the largest instances solved by previous approaches. He notes that the Mississippi River provides an almost perfect bisection that deviates only slightly from this optimal solution.
Fleischman recently joined Amazon in Palo Alto, CA as an Operations Research Scientist.
Jialei Wang grew up in Qidong, in JiangSu Province, China. As a high school student, he won first prizes in two successive Chinese Physics Olympiads and one Chinese Math Olympiad in JiangSu, and enrolled for a B. Sc. in Physics at Nanyang Technological University. He transferred to the University of Illinois at Urbana-Champaign, from which he received a B.Sc. in Physics with highest honors in 2011, joining the Ph.D. program in Applied Physics at Cornell that same year.
In the summer of 2012, he began working with ORIE’s Professor Peter Frazier, and after doing research with Frazier for a year he transferred to ORIE, realizing that Operations Research was the right field for him. Professor Frazier supervised his dissertation, which advanced and applied a technique called Bayesian optimization to disparate problems in Biochemistry, Aerospace Engineering, and Machine Learning.
“Traditional” optimization methods work towards an objective whose attainment is measured using a readily evaluated algebraic formula. But for many real world problems, step-by-step progress towards an optimal solution entails a time-consuming and expensive process of determining the value of possible solutions, for example requiring running a computer simulation, building a prototype, or conducting a laboratory experiment for each candidate solution. Bayesian optimization makes use of a formula (due the 18th century minister Thomas Bayes) by which the statistical properties of solutions previously observed can be used to learn about properties to be expected of a new observation. Properties predicted in this way are then used to choose the best candidate solution (or solutions) to try next, in an approach that can be shown to require fewer steps in attaining the optimal solution, reducing overall computational or experimental cost.
Wang has significantly advanced the state of the art in this field through an algorithm that evaluates multiple candidates in parallel rather than sequentially, using a graphical processing unit to solve problems 100 times faster. The parallel approach he developed with Scott Clark Ph.D. ’12 (Co-Founder and CEO of SigOpt), Eric Liu of Yelp, and Frazier has been incorporated into Yelp’s open-source Metrics Optimization Engine (MOE) and has been used at Yelp and Netflix to solve optimization problems in their businesses. Wang also co-developed a rigorous approach to taking advantage of multiple ways (of varying complexity and reliability) by which to determine the value of possible solutions, a situation that arises in such engineering design problems as airfoil design.
A related situation entails solving very similar Bayesian optimization problems over and over again as circumstances change. Wang developed a way to “shortcut” the optimization process by building on all potential solutions that were evaluated previously, a “warm start” approach that is ubiquitous in mathematical programming but had not previously been used in Bayesian optimization.
Collaborating with scientists in departments of chemistry and biochemistry, pharmacy and pharmaceutical sciences, and industry, Wang also developed a method, based on Bayesian optimization, to find molecules, called peptides, with particular biological or chemical properties. Testing enough possible peptides to ensure a 50-50 chance of finding at least one that meets requirements would entail roughly four years of laboratory work. Using the method proposed by Wang and his collaborators, the laboratory effort for a particular peptide searching problem was reduced to a matter of months.
Because Professor Frazier was unable to attend the Graduation Ceremony, Professor Williamson placed Wang’s hood.
Wang will officially graduate in December 2016, and has recently begun his job search. He is looking for a quantitative research position in the financial industry.