Transportation theory (mathematics)

1

In mathematics and economics, transportation theory or transport theory is a name given to the study of optimal transportation and allocation of resources. The problem was formalized by the French mathematician Gaspard Monge in 1781. In the 1920s A.N. Tolstoi was one of the first to study the transportation problem mathematically. In 1930, in the collection Transportation Planning Volume I for the National Commissariat of Transportation of the Soviet Union, he published a paper "Methods of Finding the Minimal Kilometrage in Cargo-transportation in space". Major advances were made in the field during World War II by the Soviet mathematician and economist Leonid Kantorovich. Consequently, the problem as it is stated is sometimes known as the Monge–Kantorovich transportation problem. The linear programming formulation of the transportation problem is also known as the HitchcockKoopmans transportation problem.

Motivation

Mines and factories

Suppose that we have a collection of m mines mining iron ore, and a collection of n factories which use the iron ore that the mines produce. Suppose for the sake of argument that these mines and factories form two disjoint subsets M and F of the Euclidean plane. Suppose also that we have a cost function, so that c(x, y) is the cost of transporting one shipment of iron from x to y. For simplicity, we ignore the time taken to do the transporting. We also assume that each mine can supply only one factory (no splitting of shipments) and that each factory requires precisely one shipment to be in operation (factories cannot work at half- or double-capacity). Having made the above assumptions, a transport plan is a bijection T: M \to F. In other words, each mine m \in M supplies precisely one target factory T(m) \in F and each factory is supplied by precisely one mine. We wish to find the optimal transport plan, the plan T whose total cost is the least of all possible transport plans from M to F. This motivating special case of the transportation problem is an instance of the assignment problem. More specifically, it is equivalent to finding a minimum weight matching in a bipartite graph.

Moving books: the importance of the cost function

The following simple example illustrates the importance of the cost function in determining the optimal transport plan. Suppose that we have n books of equal width on a shelf (the real line), arranged in a single contiguous block. We wish to rearrange them into another contiguous block, but shifted one book-width to the right. Two obvious candidates for the optimal transport plan present themselves: If the cost function is proportional to Euclidean distance ( for some \alpha > 0) then these two candidates are both optimal. If, on the other hand, we choose the strictly convex cost function proportional to the square of Euclidean distance ( for some \alpha > 0), then the "many small moves" option becomes the unique minimizer. Note that the above cost functions consider only the horizontal distance traveled by the books, not the horizontal distance traveled by a device used to pick each book up and move the book into position. If the latter is considered instead, then, of the two transport plans, the second is always optimal for the Euclidean distance, while, provided there are at least 3 books, the first transport plan is optimal for the squared Euclidean distance.

Hitchcock problem

The following transportation problem formulation is credited to F. L. Hitchcock: Tjalling Koopmans is also credited with formulations of transport economics and allocation of resources.

Abstract formulation of the problem

Monge and Kantorovich formulations

The transportation problem as it is stated in modern or more technical literature looks somewhat different because of the development of Riemannian geometry and measure theory. The mines-factories example, simple as it is, is a useful reference point when thinking of the abstract case. In this setting, we allow the possibility that we may not wish to keep all mines and factories open for business, and allow mines to supply more than one factory, and factories to accept iron from more than one mine. Let X and Y be two separable metric spaces such that any probability measure on X (or Y) is a Radon measure (i.e. they are Radon spaces). Let be a Borel-measurable function. Given probability measures \mu on X and \nu on Y, Monge's formulation of the optimal transportation problem is to find a transport map T : X \to Y that realizes the infimum where T_*(\mu) denotes the push forward of \mu by T. A map T that attains this infimum (i.e. makes it a minimum instead of an infimum) is called an "optimal transport map". Monge's formulation of the optimal transportation problem can be ill-posed, because sometimes there is no T satisfying : this happens, for example, when \mu is a Dirac measure but \nu is not. We can improve on this by adopting Kantorovich's formulation of the optimal transportation problem, which is to find a probability measure \gamma on X \times Y that attains the infimum where denotes the collection of all probability measures on X \times Y with marginals \mu on X and \nu on Y. It can be shown that a minimizer for this problem always exists when the cost function c is lower semi-continuous and is a tight collection of measures (which is guaranteed for Radon spaces X and Y). (Compare this formulation with the definition of the Wasserstein metric W_p on the space of probability measures.) A gradient descent formulation for the solution of the Monge–Kantorovich problem was given by Sigurd Angenent, Steven Haker, and Allen Tannenbaum.

Duality formula

The minimum of the Kantorovich problem is equal to where the supremum runs over all pairs of bounded and continuous functions and such that

Economic interpretation

The economic interpretation is clearer if signs are flipped. Let x \in X stand for the vector of characteristics of a worker, y \in Y for the vector of characteristics of a firm, and for the economic output generated by worker x matched with firm y. Setting and, the Monge–Kantorovich problem rewrites: which has dual : where the infimum runs over bounded and continuous function and. If the dual problem has a solution, one can see that: so that u(x) interprets as the equilibrium wage of a worker of type x, and v(y) interprets as the equilibrium profit of a firm of type y.

Solution of the problem

Optimal transportation on the real line

For, let denote the collection of probability measures on \mathbb{R} that have finite p-th moment. Let and let, where is a convex function. The proof of this solution appears in Rachev & Rüschendorf (1998).

Discrete version and linear programming formulation

In the case where the margins \mu and \nu are discrete, let \mu_x and \nu_y be the probability masses respectively assigned to and, and let be the probability of an xy assignment. The objective function in the primal Kantorovich problem is then and the constraint expresses as and In order to input this in a linear programming problem, we need to vectorize the matrix \gamma_{xy} by either stacking its columns or its rows, we call this operation. In the column-major order, the constraints above rewrite as where \otimes is the Kronecker product, is a matrix of size n\times m with all entries of ones, and I_{n} is the identity matrix of size n. As a result, setting, the linear programming formulation of the problem is which can be readily inputted in a large-scale linear programming solver (see chapter 3.4 of Galichon (2016) ).

Semi-discrete case

In the semi-discrete case, and \mu is a continuous distribution over, while is a discrete distribution which assigns probability mass \nu _{j} to site. In this case, we can see that the primal and dual Kantorovich problems respectively boil down to: for the primal, where means that and, and: for the dual, which can be rewritten as: which is a finite-dimensional convex optimization problem that can be solved by standard techniques, such as gradient descent. In the case when, one can show that the set of assigned to a particular site j is a convex polyhedron. The resulting configuration is called a power diagram.

Quadratic normal case

Assume the particular case, , and where A is invertible. One then has The proof of this solution appears in Galichon (2016).

Separable Hilbert spaces

Let X be a separable Hilbert space. Let denote the collection of probability measures on X that have finite p-th moment; let denote those elements that are Gaussian regular: if g is any strictly positive Gaussian measure on X and g(N) = 0, then \mu(N) = 0 also. Let, , for. Then the Kantorovich problem has a unique solution \kappa, and this solution is induced by an optimal transport map: i.e., there exists a Borel map such that Moreover, if \nu has bounded support, then for \mu-almost all x\in X for some locally Lipschitz, c-concave and maximal Kantorovich potential \varphi. (Here denotes the Gateaux derivative of \varphi.)

Entropic regularization

Consider a variant of the discrete problem above, where we have added an entropic regularization term to the objective function of the primal problem One can show that the dual regularized problem is where, compared with the unregularized version, the "hard" constraint in the former dual has been replaced by a "soft" penalization of that constraint (the sum of the terms ). The optimality conditions in the dual problem can be expressed as Denoting A as the matrix of term, solving the dual is therefore equivalent to looking for two diagonal positive matrices D_{1} and D_{2} of respective sizes and , such that and. The existence of such matrices generalizes Sinkhorn's theorem and the matrices can be computed using the Sinkhorn–Knopp algorithm, which simply consists of iteratively looking for to solve, and \psi _{y} to solve. Sinkhorn–Knopp's algorithm is therefore a coordinate descent algorithm on the dual regularized problem.

Applications

The Monge–Kantorovich optimal transport has found applications in wide range in different fields. Among them are:

This article is derived from Wikipedia and licensed under CC BY-SA 4.0. View the original article.

Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.
Bliptext is not affiliated with or endorsed by Wikipedia or the Wikimedia Foundation.

Edit article