O is for Optimal Transport
Oxford is home to many students who love coffee and to plenty of coffee shops. Consider then the following problem. Each coffee shop produces a certain number of coffees per day and each student must travel to a coffee shop to get their daily shot of coffee. To keep things simple, let us assume that all students travel by bike and that the number of coffees produced in all of Oxford is just enough to match the students’ demand. What is the optimal way to allocate students to coffee shops in order to minimize the total distance travelled? This is the basic form of an optimal transport problem, going back in essentially this form to Gaspard Monge’s 1781 Mémoire sur la théorie des déblais et des remblais, although there the problem was stated in a more mundane form involving mines and construction sites.
Although further applications of Monge’s problem were realised around the first half of the 20th century , theoretical progress was limited. The defining moment came in the 1940s when Leonid Kantorovich reformulated the problem in terms of linear programming. Since then, optimal transport has made huge progress in terms of theory and has found applications in mathematics, economics, statistics and more recently machine learning and artificial intelligence. It has deep connections with many branches of mathematics, especially with partial differential equations where it provides a natural geometric interpretation of many important equations, but also with optimisation and probability. The importance of the area is highlighted by two Fields medals.
Optimal transport can be used to compare different samples and datasets, so is crucial in statistics and machine learning. A typical machine learning application is in image processing where optimal transport is used for comparing, processing and interpolating images. Optimal transport has also been used to design efficient algorithms for computationally intensive tasks in Bayesian inference.
In my own research, I have used optimal transport to design algorithms that are used in robotics. I have also used it to optimise the allocation of summer projects to our graduate students, saving as a result an incredible amount of time compared to manual allocation!
The figure below shows an allocation of students to coffee shops that minimises the total distance travelled. You may be able to see that a few students have been allocated to two coffee shops; this means that the optimal plan involves a little randomness—in some cases you should let chance decide which of the two coffee shops you visit that day!
