This article was originally published in the Oxford Scientist’s Print edition, Barriers, in Michaelmas Term 2022, under the title ‘From sandcastles to economics and artificial intelligence: optimal transport theory through the years’. You can read more of our Print articles here.
In 1781, the French mathematician Gaspard Monge presented the members of the Academy of Paris with a problem that had captured his attention for months. As a skilled engineer who once designed defensive naval fortifications for France, he had begun to wonder: is there a mathematical method to identify the least costly way of constructing a given structure from a pile of dirt?
Although originally developed in a seemingly niche context, Monge’s “sandcastle” problem arises in a wide array of fields. For instance, it can be applied in economics, where its solutions are used to minimise the cost of transporting goods, but also in computing, where it forms the basis of the field of linear programming. Even artificial intelligence can benefit from it, as the solutions of Monge’s problems are used to evaluate how well algorithms reproduce images. Consequently, the last century of research in optimal transport—the branch of mathematics that studies solutions to Monge’s problem—has enormously impacted modern science, allowing us to push the limits of our knowledge.
It was not until the 20th century that optimal transport theory fully developed into its own subject. This was because of the extreme difficulty of solving Monge’s problem outside of a few special circumstances. Solutions to Monge’s problem come in the form of transportation plans: maps that tell workers how much material to send from location x to a new place y. Until the 1940s, though, it was unclear to mathematicians if a transportation plan even existed that would describe the creation of any arbitrary complex structure. World War II changed the situation entirely, as demands for solutions to Monge’s problem increasingly captured international attention. This resulted from the potential application of optimal transport plans in military logistics and economics: in determining the “best” means of transporting resources, policymakers and businesses could speed up arms deliveries to soldiers and simultaneously minimise costs.
This goal, along with the previous difficulties in solving Monge’s problem, motivated the Soviet mathematician Leonid Kantorovich to address optimal transport in a novel way, using concepts and tools from probability theory. Kantorovich’s resulting mathematical reformulation slightly simplified Monge’s original problem by essentially allowing workers to divide resources during transport. For example, a worker could send half of their supply to location A and the other half to location B, rather than sending everything to the same place. This alteration allowed Kantorovich to increase the number of possible transport plans, which was key for him to establish the existence of optimal transport plans for any general structure. Moreover, he proved that optimal transport plans were unique—in other words, there was only one way to move goods from A to B with the least cost.
Although Kantorovich had determined that there was a solution to Monge’s problem, he went even further by designing some of the first computer algorithms to identify optimal transport plans. In doing so, he helped found linear programming, a major field within computer science that is devoted to the development and analysis of algorithms that aim to efficiently solve Monge’s problem. Kantorovich’s success in solving the optimal transport problem did not achieve much fanfare at the time, but became internationally recognised over the ensuing decades of the 20th century: by the 1970s, his ideas had even been adopted by the Soviet state to help manage their economy. Economists from the West also recognised his enormous achievements, and in 1975 Kantorovich was awarded the Nobel Prize in Economics for his work on “optimal allocation of resources” using linear programming and optimal transport theory.
Optimal transport continues to find use today in the fields of machine learning and artificial intelligence by supplying a notion of “distances” between two images. For example, one can compute an optimal transport plan between a picture of Pacman and a picture of a ghost; the optimal transport plan describes how much “work” is required to morph the first image to the second (and vice versa). The total “work” associated with this plan describes the “distance” between the two images, with smaller values indicating that the images are more similar.
These metrics, known as “Wasserstein distances”, have been used to evaluate certain machine learning algorithms known as generative artificial networks (GANs) that produce images from user-specified keywords or numbers. In measuring the Wasserstein distance between a given image and one produced by a GAN, researchers can evaluate the difference between AI algorithms, further enhance their capabilities, and smash past current barriers in the field. As we enter the middle of the 21st century, we can expect that optimal transport will play a role in new technological and scientific advancements.
