mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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.G. Monge. ''Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année'', pages 666–704, 1781. In the 1920s A.N. Tolstoi was one of the first to study the transportation problem

mathematically Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

. 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.L. Kantorovich. ''On the translocation of masses.'' C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942. Consequently, the problem as it is stated is sometimes known as the Monge–Kantorovich transportation problem. The

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...

formulation of the transportation problem is also known as the

Hitchcock Sir Alfred Joseph Hitchcock (13 August 1899 – 29 April 1980) was an English filmmaker. He is widely regarded as one of the most influential figures in the history of cinema. In a career spanning six decades, he directed over 50 featur ...

–

Koopmans Koopmans is a Dutch occupational surname meaning " merchant's".

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

subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...

s ''M'' and ''F'' of the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...

R². Suppose also that we have a ''cost function'' ''c'' : R² × R² → [0, ∞), 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'' → ''F''. In other words, each mine ''m'' ∈ ''M'' supplies precisely one target factory ''T''(''m'') ∈ ''F'' and each factory is supplied by precisely one mine. We wish to find the ''optimal transport plan'', the plan ''T'' whose ''total cost'' :

c(T) := \sum_ c(m, T(m))

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 The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: :The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any ta ...

. More specifically, it is equivalent to finding a minimum weight matching in a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

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 In elementary mathematics, a number line is a picture of a graduated straight line (geometry), line that serves as visual representation of the real numbers. Every point of a number line is assumed to correspond to a real number, and every real ...

), 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: # move all ''n'' books one book-width to the right ("many small moves"); # move the left-most book ''n'' book-widths to the right and leave all other books fixed ("one big move"). If the cost function is proportional to Euclidean distance (''c''(''x'', ''y'') = α, ''x'' − ''y'', ) 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 (''c''(''x'', ''y'') = ''α'', ''x'' − ''y'', ²), 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 Frank Lauren Hitchcock (March 6, 1875 – May 31, 1957) was an American mathematician and physicist known for his formulation of the transportation problem in 1941. Academic life Frank did his preparatory study at Phillips Andover Academy. He ...

: :Suppose there are ''m'' sources

x_1, \ldots, x_m

for a commodity, with

a(x_i)

units of supply at ''x''_''i'' and ''n'' sinks

y_1, \ldots, y_n

for the commodity, with the demand

b(y_j)

at ''y''_''j''. If

a(x_i,\ y_j)

is the unit cost of shipment from ''x''_''i'' to ''y''_''j'', find a flow that satisfies demand from supplies and minimizes the flow cost. This challenge in logistics was taken up by

D. R. Fulkerson Delbert Ray Fulkerson (; August 14, 1924 – January 10, 1976) was an American mathematician who co-developed the FordFulkerson algorithm, one of the most well-known algorithms to solve the maximum flow problem in Flow network, networks. Early l ...

and in the book ''Flows in Networks'' (1962) written with

L. R. Ford Jr. Lester Randolph Ford Jr. (September 23, 1927 – February 26, 2017) was an American mathematician specializing in network flow problems. He was the son of mathematician Lester R. Ford Sr. Ford's paper with D. R. Fulkerson on the maximum flow p ...

Tjalling Koopmans is also credited with formulations of

transport economics Transport economics is a branch of economics founded in 1959 by American economist John R. Meyer that deals with the allocation of resources within the transport sector. It has strong links to civil engineering. Transport economics differs from ...

and allocation of resources.

Numerical solution in Excel

With large numbers of routes, the problem is solved numerically. Inputs: The Transportation cells are T . The Supply data cells are S .The Demand data cells are D . Think of each unit of supply as a large box (a shipping container). Outputs: The shipment plan is X. The current shipping cost is K. Objective: Maximize the cost reduction MAX R(X)=K-T·X The shipment plan, X, must satisfy three types of constraint (1) Non-negativity constraints X >= 0 (2) Supply constraints S-1•X >= 0 (3) Demand constraints X•1-D >= 0 One way to set up the problem in Excel is depicted in the table below. The total shipping costs T·X are the product of terms in the array 2:H3 R-V solution method (an update of the simplex method): For a small number of routes, the problem can be solved rather like a beginner's cross word puzzle or Sudoku. The R-V Solution Method introduces Virtual unit Costs ''c'', Virtual Prices ''p'' and a Virtual Trader. The VIrtual Trader provides Real implications. Crucially, the V-trader is a price taker. Then there will be excess demand on any strictly profitable route and demand will be zero on any strictly unprofitable route. VIRTUAL PROFIT MAXIMIZATION VPM The unit profit on each route is p_j - t_ij -c_i These are calculated in the V-PROFIT Box at the bottom right of the Table. (If you are working with Excel, enter these formulas and then use SOLVER if for the numerically computed maximum.) The profit must be zero on all utilized routs and no route is strictly profitable. STEP 1: Build a table like the one below. in the table small numbers are data points. Large bold numbers are variables. In each column the V-PRICE must at least be the minimum cost to satisfy VPM. STEP 2: Make the lowest cost supplier the #1 supplier (top row). STEP 3; Fill the orders sequentially. The first route to be filled should be in the top row 1:D1 Then fill sequentially by cost so 2;D1is filled next STEP 3: The last order to be filled is in ''Italics''. The source in this row is the less valuable source. Then C2 is zero. Fill in the cell to the left of C2 STEP 4: Solve for the V-Prices and V-costs. On each route select V-COSTS and V-PRICES so that the V-Trader breaks even on all the active routes. Start with the column that has the fewest entries (Column 2) V-SUDOKU The V-Costs are initially left blank 2 (zero). To break even in Column 2, P2 = C2 +T22 =0 + 5 =5 In Column 1 both routes are used. Since C2 is zero, C1 =1. Then P1=C1 + T21 =5 V-CHECK If you set this V-PUZZLE up on a spreadsheet, the profit BOX will already be filled in. The real value of the V-prices Supply: If you add a unit of supply at S1 you can lower the transportation cost by adding 1 to cell 1:C2 and subtracting 1 from cell 2;C2 This lowers shipping costs by 1, This is the meaning of C1. If the firm can rent an additional container at less than 1 (think "one thousand") there are additional cost savings. If you try this at S2, the additional container doe not lower shipping costs. This is the meaning of C1. Demand: What would be the reduction in shipping costs if another unit of the product could be obtained locally (at the Destination). Try reducing D1 by one unit. The shipping cost falls by...? Yes, by the V-PRICE Using the V-virtual trader method therefore yields Virtual price and costs of Real importance. Programming note: If you use a canned maximizing program like Excels Add-In Solver, it will get to the correct answer in a flash. If you look at the "Lagrange Multipliers" or "shadow prices" that may appear in a sensitivity report, they can be confusing. Since Solver provides the solution, all you have to do is Sudoku your way to the V-Costs and V-prices. Here is the set-up for 3 suppliers and 3 destinations. I suggest that you set S3=0 initially and Sudoku your way to the solution..

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 In mathematics, the concept of a measure is a generalization and formalization of geometrical measures ( length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simil ...

. 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 In mathematics, a probability measure is a real-valued function defined on a set of events in a probability space that satisfies measure properties such as ''countable additivity''. The difference between a probability measure and the more gener ...

X

(or

Y

) is a Radon measure (i.e. they are

Radon space In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named beca ...

s). Let

c : X \times Y \to, \infty /math> be a Borel-

measurable function In mathematics and in particular measure theory, a measurable function is a function between the underlying sets of two measurable spaces that preserves the structure of the spaces: the preimage of any measurable set is measurable. This is in di ...

. Given probability measures

\mu

X

and

\nu

Y

, Monge's formulation of the optimal transportation problem is to find a transport map

T : X \to Y

that realizes the infimum :

\inf \left\,

where

T_*(\mu)

denotes the push forward of

\mu

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

T_*(\mu) = \nu

: 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

X \times Y

that attains the infimum :

\inf \left\,

where

\Gamma (\mu, \nu)

denotes the collection of all probability measures on

X \times Y

with marginals

\mu

X

and

\nu

Y

. It can be shownL. Ambrosio, N. Gigli & G. Savaré.
Gradient Flows in Metric Spaces and in the Space of Probability Measures
'' Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel. (2005) that a minimizer for this problem always exists when the cost function

c

is lower semi-continuous and

\Gamma(\mu, \nu)

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_1

on the space of probability measures.) A gradient descent formulation for the solution of the Monge–Kantorovich problem was given by

Sigurd Angenent Sigurd Bernardus Angenent (born 1960) is a Dutch-born mathematician and professor at the University of Wisconsin–Madison. Angenent works on partial differential equations and dynamical systems, with his recent research focusing on heat equation a ...

, Steven Haker, and

Allen Tannenbaum Allen Robert Tannenbaum (born January 25, 1953) is an American/Israeli applied mathematician and presently Distinguished Professor of Computer Science and Applied Mathematics & Statistics at the State University of New York at Stony Brook. He is ...

Duality formula

The minimum of the Kantorovich problem is equal to :

\sup \left( \int_X \varphi (x) \, \mathrm \mu (x) + \int_Y \psi (y) \, \mathrm \nu (y) \right),

where the

supremum In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...

runs over all pairs of

bounded Boundedness or bounded may refer to: Economics * Bounded rationality, the idea that human rationality in decision-making is bounded by the available information, the cognitive limitations, and the time available to make the decision * Bounded e ...

and

continuous function In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in value ...

\varphi : X \rightarrow \mathbf

and

\psi : Y \rightarrow \mathbf

such that :

\varphi (x) + \psi (y) \leq c(x, y).

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

\Phi(x,y) =-c(x,y)

for the economic output generated by worker

x

matched with firm

y

. Setting

u(x) = -\varphi(x)

and

v(y) =-\psi(y)

, the Monge–Kantorovich problem rewrites:

\sup \left\

which has

dual Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual (grammatical ...

\inf \left\

where the infimum runs over bounded and continuous function

u:X\rightarrow \mathbf

and

v:Y\rightarrow \mathbf

. If the dual problem has a solution, one can see that:

v(y) =\sup_x \left\

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

1 \leq p < \infty

, let

\mathcal_p(\mathbf)

denote the collection of

s on

\mathbf

that have finite

p

-th

moment Moment or Moments may refer to: * Present time Music * The Moments, American R&B vocal group Albums * ''Moment'' (Dark Tranquillity album), 2020 * ''Moment'' (Speed album), 1998 * ''Moments'' (Darude album) * ''Moments'' (Christine Guldbrand ...

. Let

\mu, \nu \in \mathcal_p(\mathbf)

and let

c(x, y) = h(x-y)

, where

h:\mathbf \rightarrow,\infty)

is a convex function. # If

\mu

has no atom (measure theory)">atom, i.e., if the cumulative distribution function">convex function">,\infty) is a convex function. # If

\mu

has no atom (measure theory)">atom, i.e., if the cumulative distribution function

F_\mu = \mathbf\rightarrow[0,1]

\mu

is a

, then

F_^ \circ F_ : \mathbf \to \mathbf

is an optimal transport map. It is the unique optimal transport map if

h

is strictly convex. # We have ::

\min_ \int_ c(x, y) \, \mathrm \gamma (x, y) = \int_0^1 c \left( F_^ (s), F_^ (s) \right) \, \mathrm s.

The proof of this solution appears in Rachev & Rüschendorf (1998).Rachev, Svetlozar T., and Ludger Rüschendorf. ''Mass Transportation Problems: Volume I: Theory''. Vol. 1. Springer, 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

x\in \mathbf

and

y\in \mathbf

, and let

\gamma _

be the probability of an

xy

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

\sum_ \gamma_c_

and the constraint

\gamma \in \Gamma \left( \mu ,\nu \right)

expresses as :

\sum_\gamma_=\mu_x,\forall x\in \mathbf

and :

\sum_ \gamma_=\nu_y,\forall y\in \mathbf.

In order to input this in a

problem, we need to vectorize the matrix

\gamma_

by either stacking its columns or its rows, we call

\operatorname

this operation. In the

column-major order In computing, row-major order and column-major order are methods for storing multidimensional arrays in linear storage such as random access memory. The difference between the orders lies in which elements of an array are contiguous in memory. In ...

, the constraints above rewrite as :

\left( 1_\otimes I_\right) \operatorname\left( \gamma \right) =\mu

and

\left( I_\otimes 1_\right) \operatorname\left( \gamma \right) =\nu

where

\otimes

is the

Kronecker product In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a generalization of the outer product (which is denoted by the same symbol) from vectors to ...

1_

is a matrix of size

n\times m

with all entries of ones, and

I_

is the identity matrix of size

n

. As a result, setting

z=\operatorname\left( \gamma \right)

, the linear programming formulation of the problem is :

& z=\binom \end

which can be readily inputted in a large-scale linear programming solver (see chapter 3.4 of Galichon (2016) Galichon, Alfred. ''Optimal Transport Methods in Economics''. Princeton University Press, 2016.).

Semi-discrete case

In the semi-discrete case,

X=Y=\mathbf^d

and

\mu

is a continuous distribution over

\mathbf^d

, while

\nu =\sum_^\nu _\delta_

is a discrete distribution which assigns probability mass

\nu _

to site

y_j \in \mathbf^d

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

\inf \left\

for the primal, where

\gamma \in \Gamma \left( \mu ,\nu \right)

means that

\int_ d\gamma _\left( x\right) =\nu _

and

\sum_d\gamma_\left( x\right) =d\mu \left( x\right)

, and:

\sup \left\

for the dual, which can be rewritten as:

\sup_\left\

which is a finite-dimensional convex optimization problem that can be solved by standard techniques, such as gradient descent. In the case when

c\left( x,y\right) =\left\vert x-y\right\vert ^/2

, one can show that the set of

x\in \mathbf

assigned to a particular site

j

is a convex polyhedron. The resulting configuration is called a

power diagram In computational geometry, a power diagram, also called a Laguerre–Voronoi diagram, Dirichlet cell complex, radical Voronoi tesselation or a sectional Dirichlet tesselation, is a partition of the Euclidean plane into polygonal cells defined from ...

Quadratic normal case

Assume the particular case

\mu =\mathcal\left( 0,\Sigma_X\right)

\nu =\mathcal \left( 0,\Sigma _\right)

, and

c(x,y) =\left\vert y-Ax\right\vert^2/2

where

A

is invertible. One then has :

\varphi(x) =-x^\top \Sigma_X^\left( \Sigma_X^A^\top \Sigma_Y A\Sigma_X^\right) ^\Sigma_^x/2

\psi(y) =-y^\top A\Sigma_X^\left( \Sigma_X^A^\top \Sigma_Y A\Sigma_^\right)^ \Sigma_X^Ay/2

T(x) = (A^\top)^\Sigma_X^ \left(\Sigma_X^A^\top \Sigma_Y A\Sigma_X^ \right)^ \Sigma_X^

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

Separable Hilbert spaces

Let

X

be a separable

Hilbert space In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...

. Let

\mathcal_p(X)

denote the collection of probability measures on

X

that have finite

p

-th moment; let

\mathcal_p^r(X)

denote those elements

\mu \in \mathcal_p(X)

that are Gaussian regular: if

g

is any strictly positive

Gaussian measure In mathematics, Gaussian measure is a Borel measure on finite-dimensional Euclidean space R''n'', closely related to the normal distribution in statistics. There is also a generalization to infinite-dimensional spaces. Gaussian measures are named ...

X

and

g(N) = 0

, then

\mu(N) = 0

also. Let

\mu \in \mathcal_p^r (X)

\nu \in \mathcal_p(X)

c (x, y) = ,  x - y , ^p/p

for

p\in(1,\infty), p^ + q^ = 1

. 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

r\in L^p(X, \mu; X)

such that :

\kappa = (\mathrm_X \times r)_ (\mu) \in \Gamma (\mu, \nu).

Moreover, if

\nu

has

support Support may refer to: Arts, entertainment, and media * Supporting character Business and finance * Support (technical analysis) * Child support * Customer support * Income Support Construction * Support (structure), or lateral support, a ...

, then :

r(x) = x -  ,  \nabla \varphi (x) , ^ \, \nabla \varphi (x)

for

\mu

-almost all

x\in X

for some

locally Lipschitz In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there exis ...

, ''c''-concave and maximal Kantorovich potential

\varphi

. (Here

\nabla \varphi

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 :

& \sum_\gamma_ = \nu_y, \forall y\in \mathbf \end

One can show that the dual regularized problem is :

\max_ \sum_ \varphi_x \mu_x + \sum_ \psi_y v_y - \varepsilon \sum_ \exp \left( \frac\right)

where, compared with the unregularized version, the "hard" constraint in the former dual (

\varphi_x + \psi_y - c_\geq 0

) has been replaced by a "soft" penalization of that constraint (the sum of the

\varepsilon \exp \left( (\varphi _x + \psi_y - c_)/\varepsilon \right)

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

\mu_x = \sum_ \exp \left( \frac \right) ~\forall x\in \mathbf

\nu_y = \sum_ \exp \left( \frac\right) ~\forall y\in \mathbf

Denoting

A

as the

\left\vert \mathbf\right\vert \times \left\vert \mathbf\right\vert

matrix of term

A_=\exp \left(-c_ / \varepsilon \right)

, solving the dual is therefore equivalent to looking for two diagonal positive matrices

D_

and

D_

of respective sizes

\left\vert \mathbf\right\vert

and

\left\vert \mathbf\right\vert

, such that

D_AD_1_=\mu

and

\left( D_AD_\right) ^1_=\nu

. 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

\varphi _

to solve , and

\psi _

to solve . Sinkhorn–Knopp's algorithm is therefore a

coordinate descent Coordinate descent is an optimization algorithm that successively minimizes along coordinate directions to find the minimum of a function. At each iteration, the algorithm determines a coordinate or coordinate block via a coordinate selection rule, ...

algorithm on the dual regularized problem.

Applications

The Monge–Kantorovich optimal transport has found applications in wide range in different fields. Among them are: * Image registration and warping * Reflector design * Retrieving information from shadowgraphy and proton radiography *

Seismic tomography Seismic tomography or seismotomography is a technique for imaging the subsurface of the Earth with seismic waves produced by earthquakes or explosions. P-, S-, and surface waves can be used for tomographic models of different resolutions based on ...

and

reflection seismology Reflection seismology (or seismic reflection) is a method of exploration geophysics that uses the principles of seismology to estimate the properties of the Earth's subsurface from reflected seismic waves. The method requires a controlled seismi ...

* The broad class of economic modelling that involves gross substitutes property (among others, models of matching and discrete choice).

Motivation

Mines and factories

Moving books: the importance of the cost function

Hitchcock problem

Numerical solution in Excel

Abstract formulation of the problem

Monge and Kantorovich formulations

Duality formula

Economic interpretation

Solution of the problem

Optimal transportation on the real line

Discrete version and linear programming formulation

Semi-discrete case

Quadratic normal case

Separable Hilbert spaces

Entropic regularization

Applications

See also

References

Further reading