Everyone wants to know the future. Some wonder only about their personal fortunes—whom they will marry, where they will work, when they will find happiness. Others attempt to predict the future for more pragmatic reasons, hoping to increase profit margins or decrease defense vulnerabilities. Prof. Patrick Jaillet, who is the Dugald C. Jackson Professor in the Department of Electrical Engineering and Computer Science, the Co-Director of the MIT Operations Research Center, and a member of the Laboratory for Information and Decision Systems at MIT, has devoted much of his academic career to helping people make decisions without knowing the future.
The future is, of course, largely unknowable. Unfortunately, this uncertainty does not eliminate the need to make decisions in the present that take into account the likely impact of those decisions on the future. As a result, information that can flesh out the probabilities of these impacts and the likelihood that a scenario will bear out; information that can help give a theoretical shape to the unknowable, commands a high premium. But information collected without purpose or proper analysis is far less useful than information collected within the parameters of a well-designed dynamic research problem. Patrick frequently uses a small, hypothetical robot to help illustrate this principle.
In situations where it is important to determine the safest or quickest travel route, for instance, potential obstacles or hazards must be identified. When the terrain is unfamiliar or potentially dangerous, automated vehicles or robots can be sent out to collect data. If the robot only follows one predetermined path, it will take him a long time to collect useful data. More sophisticated programming, such as an algorithm that instructs the robot to turn right or left every time his path is blocked, allows for faster, more dynamic approaches. This leads to the development of data-driven algorithms and methodologies with provable properties and numerous practical applications.
With his collaborators from the Singapore-MIT Alliance for Research and Technology (SMART), Patrick has used real-time data from disparate sources to create novel algorithms that can predict paths in dynamic transportation networks and provide on-demand route guidance in uncertain or unpredictable situations. Such algorithms help military and government agencies position and employ emergency response vehicles and personnel, dispatchers improve the overall performance of taxi fleets, and on-demand guidance systems identify the quickest and safest way for drivers to reach their destinations.
Patrick's current research interests have evolved from classical combinatorial optimization problems like the Traveling Salesman Problem (TSP), which involves cities, any two of which are connected by a direct route (or straight line) on a map, and a salesman who wants or needs to visit every city while keeping his travel costs and time away from home as low as possible. In theory, finding the optimal itinerary requires the salesman to explore all possible routes, the number of which increases exponentially as the number of cities increases. The solution, while finite, remains impossibly large. As an alternative, researchers can develop algorithms designed to calculate a solution that comes extremely close to the optimal solution in a significantly shorter amount of time.
Patrick and some members of his research team, which includes Xin Lu and Swati Gupta, doctoral students at the MIT Operations Research Center, and Dawsen Huang and Shen Shen, graduate students in Electrical Engineering and Computer Science, apply the same principles used to solve this historical problem in an online context, driven by incomplete and unknown data sources and time sensitive revenue streams. Patrick uses a Federal Express driver in the middle of his delivery route as an example. If a new customer calls in an order located somewhere close to the current delivery path, what is the dispatcher's best course of action? The robust algorithms designed by Patrick and his researchers help determine if it is more efficient and cost effective to send out a second driver, have the first driver interrupt his current deliveries to pick up the new package, or have the first driver complete the deliveries already in progress before returning to the mail center to retrieve and deliver the new package.
A similar canonical problem involves bipartite matching, where a given set of nodes, or vertices, on a graph must be matched to other nodes with an edge (or straight line). This second group may also consist of a complete, visible set, or they may appear individually, at random and unpredictable intervals. An early model of this problem, sometimes referred to as the "marriage game," attempts to match a set of single males to a parallel set of single females. Edges, or lines, are drawn between men and women who like each other. If no two edges are adjacent, and each person is incident to an edge, the match is considered to be perfect. Perfect matches are not always possible, however, and thus many algorithms merely attempt to "marry" the maximum number of people and achieve the maximum amount of "marital bliss," or customer satisfaction.
In his research, Patrick applies this classic model to online resource allocation problems, the kind created when the distribution of content, bandwidth, advertising space, and the like depends on unpredictable user demands. Services like Netflix which offer on-demand streaming of movies and videos have difficulty predicting which movies will be requested by which users at which times. Although historical and real-time data can help mitigate this unpredictability problem, online vendors need tools to help them identify, interpret, and anticipate user request patterns. This, in turn, allows for an efficient and profitable allocation of resources. The algorithm solutions designed and analyzed to address online versions of bipartite matching problems can be used to streamline online auctions, maximize the benefit of the sponsored advertising used by services like Google AdWords and AdSense, and improve content delivery load balancing. In addition to Xin Lu, other members of Patrick's research team working on these problems include Vahideh Manshadi, a post-doc in the Department of Electrical Engineering and Computer Science and the Operations Research Center, Andrew Mastin, a doctoral student in Electrical Engineering and Computer Science, and Rico Zenklusen, a post-doc working in Math and Electrical Engineering and Computer Science.
Theoretical investigation of classical mathematical archetypes can even lead to medical miracles. A recent New York Times article by Kevin Sack, "60 Lives, 30 Kidneys, All Linked", describes how doctors at 17 different hospitals in 11 different states used an algorithm similar to the ones designed in LIDS, and inspired by the same classical matching problems Patrick uses in his research, to link 30 patients in desperate need of a kidney with 30 volunteer donors.
The United Network for Organ Sharing (UNOS), the government agency overseeing organ transplants in the United States, reports that there are more than 90,000 people currently waiting for new kidneys. Only about 17,000 people receive kidney transplants each year, while 4,500 on the waiting list die. Many patients who need kidney transplants have friends or relatives willing to donate a kidney. However, immunological incompatibilities often prevent these volunteers from donating to their loved ones.
Over the past seven years a number of hospitals, including Johns Hopkins and Massachusetts General, have participated in paired exchanges, sometimes called domino exchanges, where volunteers donate kidneys to strangers in order to secure another kidney for their friends or relatives. Such chains require complicated calculations and rely on algorithms similar to the ones used by online dating services, albeit with much higher stakes.
According to Sack's article, the algorithm used by the National Kidney Registry "assembles up to a million viable combinations at a rate of 8,000 per second" and then "ranks the possible combinations by the number of transplants they would enable, with weight given to chains that find kidneys for hard-to-match patients and those who have waited a long time". This data led to 175 successful transplants in 2011, including the 30 person paired exchange known as Chain 124, which is the largest paired exchanged performed to date.
An examination of Chain 124 revealed that donor chains and other forms of paired exchanges resulted in 429 kidney transplants in 2010. All of these transplants involved a live donor, which dramatically decreases the chances of organ rejection or early organ failure. In addition, donors in these chains have the opportunity to help two people—the person who receives their kidney and the loved one who receives a kidney from that recipient's friend or family member.
Like so many of Patrick's examples, this practical application of online matching saves both time and money. Patients can bypass the long, frustrating waiting period associated with traditional organ transplants and significantly reduce the annual cost of their medical treatment. Medicare statistics estimate that the average dialysis patient spends $500,000 to $1 million on medical care each year, while a kidney transplant operation only costs between $100,000 and $200,000.
Using bipartite matching algorithms to orchestrate organ donation and transplants is one of the most dramatic applications for the research conducted by Patrick and his team, in particular Vahideh Manshadi, in collaboration with Prof. Itai Ashlagi from the MIT Sloan School. Like so many of his colleagues in LIDS, Patrick looks into the future to find practical, economical solutions to complex, real-world problems. His investigations into online and data-driven optimization problems have allowed his research group to develop mathematical and theoretical tools with practical applications that appear to be as limitless as the future.