↑ arvau

Wikipedia / Transportation theory (mathematics)

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 Hitchcock–Koopmans transportation problem.

Motivation

Mines and factories

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 of the Euclidean plane. Suppose also that we have a cost function. 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 and each factory is supplied by precisely one mine. We wish to find the optimal transport plan whose total cost

. 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.

This can be generalized to the continuous case, where there are infinitely many mines and factories distributed on the real line, or generally in any metric space. This case is usually pictured as "changing the shape of a pile of dirt", and thus called the earth mover's problem.

Moving books: the importance of the cost function

The following simple example illustrates the importance of the cost function 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:

  1. books one book-width to the right ("many small moves");

  2. book-widths to the right and leave all other books fixed ("one big move").

If the cost function is proportional to Euclidean distance) then these two candidates are both optimal. If, on the other hand, we choose the strictly convex), 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:

  1. , find a flow that satisfies demand from supplies and minimizes the flow cost. This challenge in logistics was taken up by D. R. Fulkerson and in the book Flows in Networks (1962) written with L. R. Ford Jr.

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.

be two separable metric spaces such that any probability measure) is a Radon measure (i.e. they are Radon spaces be a Borel-measurable function that realizes the infimum

denotes the push forward that attains this infimum (i.e. makes it a minimum instead of an infimum) is called an "optimal transport map".

is a Dirac measure is not.

that attains the infimum

with marginals.

Cost duality

This generalizes Legendre transformation with a sign flip. .

is c-convex is c-convex. The c-convexification. Equivalently, it is the smallest c pointwise. is c.

is c-convex, then the set of c-subdifferential.

. We obtain a whole set of such graphs. Their lower-edge envelope.

to be c-convex. It is c-convex iff its entire graph can be "touched" by a "tipped tool. The graph of the c.

is c-convex iff it is 1-Lipschitz. This is used in the definition of 1-Wasserstein distance is c-convex iff its graph could be touched from above by a tipped tool with the shape of a paraboloid.

Existence and uniqueness

Under fairly permissive assumptions, optimal transport plan exists.If

then an optimal transport plan such that it reaches the infimum. is the Cauchy distribution.If

  • are Polish probability spaces,

  • is lower semicontinuous,

  • ,

  • there exists a finite-cost transport plan,

  • and for any c has a unique c

then an optimal transport map exists. is an optimal transport plan between its own marginals..

Kantorovich duality

The Kantorovich duality states that: are Polish probability spaces is lower semicontinuous, and vice versa.

,

  • is an optimal plan;

  • .

More succinctly, a transport plan is optimal iff it is supported on the set of c.

Stability

The optimal transportation is stable in the following sense: are Polish probability spaces.

.Similarly, the optimal transport map is also stable. are Polish probability spaces weakly,

Economic interpretation

The optimal transport problem has an economic interpretation. Cédric Villani recounts the following interpretation from Luis Caffarelli:.

. The Kantorovich duality states that the shipper can make a price schedule that makes you pay almost as much as you would ship yourself.The Kantorovich duality states that it is in fact an equality, i.e. the shipper can make you pay as much as you would pay yourself, though the shipper might never exactly reach the bound (thus the use of infimum and supremum, instead of minimum and maximum).

as their pricing chart. Then the shipper must use an optimal plan, at which point the shipper just breaks even with no profit. Conversely, any shipping plan that allows the shipper to exactly break even must be optimal.

Solution of the problem

Optimal transportation on the real line

denote the collection of probability measures-th moment is a convex function.

  1. has no atom, i.e., if the cumulative distribution function is a continuous function is strictly convex.

  2. We have

The proof of this solution appears in Rachev & Rüschendorf (1998).

Discrete version and linear programming formulation

assignment. The objective function in the primal Kantorovich problem is then

expresses as

and

In order to input this in a linear programming problem, we need to vectorize by either stacking its columns or its rows this operation. In the column-major order, the constraints above rewrite as

is the Kronecker product is the identity matrix, 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

is a discrete distribution. In this case, we can see that the primal and dual Kantorovich problems respectively boil down to:

, 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.

is a convex polyhedron. The resulting configuration is called a power diagram.

Quadratic normal case

is invertible. One then has

The proof of this solution appears in Galichon (2016).

Separable Hilbert spaces

be a separable Hilbert space that are Gaussian regular is any strictly positive Gaussian measure also.

such that

has bounded support, then

for some locally Lipschitz denotes the Gateaux derivative.)

By minimizing flows

A gradient descent formulation for the solution of the Monge–Kantorovich problem was given by Sigurd Angenent, Steven Haker, and Allen Tannenbaum.

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

terms). The optimality conditions in the dual problem can be expressed as

. The existence of such matrices generalizes Sinkhorn's theorem and the matrices can be computed using the Sinkhorn–Knopp algorithm, to solve 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:

See also

References

Further reading