# Different linear programming versions of optimal transport

What is the difference between these two different versions of the linear programming optimization set-up for optimal transport (OT)? how to reconcile them mathematically to show that they are equivalent?

## OT Linear Programming #1

(Source) \begin{align*} \min_{\boldsymbol\Gamma} \quad & \langle\mathbf{C},\boldsymbol\Gamma \rangle = \sum_{ij}\mathbf{C}_{ij}\boldsymbol\Gamma_{ij} \\ \mathrm{s. t.} \quad & \boldsymbol\Gamma \mathbf{1} = \mathbf{\alpha} \\ &\boldsymbol\Gamma^{\top}\mathbf{1} = \mathbf{\beta} \end{align*}

• $$\boldsymbol C$$ is the distance matrix, which contains elements$$\Vert x - y \Vert$$,
• $$\boldsymbol \Gamma$$ is the transport matrix, which contains elements $$\gamma(x,y)$$,
• $$\alpha$$ and $$\beta$$ are the source and target probability distributions, respectively, of variables $$X$$ and $$Y$$.

## OT Linear Programming #2

(Source) $$\begin{array}{rrcl} \min_{\mathbf{x}} \ & \mathbf{c}^T \mathbf{x} & & \ \\ \mathrm{s.t.} \ & \mathbf{A} \mathbf{x} & = & \ \mathbf{b} \\ \ & \mathbf{x} & \geq &\ \mathbf{0} \end{array}$$

• $$\mathbf{c}$$ is a vectorization of the distance matrix $$\boldsymbol C$$,
• $$\mathbf{x}$$ is a vectorization of the transport matrix $$\boldsymbol\Gamma$$,
• while the source and target distributions are $$\mathbf{b} = \begin{bmatrix} \alpha \\ \beta\end{bmatrix}$$
• The first version is how you naturally think about it in mathematical terms and write in papers. The second version is how you have to reformulate it to actually fit it into canonical LP form (and possibly feed into a solver). – Michal Adamaszek Nov 13 '20 at 12:57
• about reconciling the two, how can it be shown that the constraints in version #1 are a rewording of the constraints in version #2? – develarist Nov 13 '20 at 13:00

To reconcile both, note that $$\bf x$$ is obtained by stacking the columns of $$\bf \Gamma$$. For the cost, $$\bf c$$ is obtained by stacking the columns of the cost matrix $$\bf C$$. Also, let $$\mathbb I_n$$ be an $$n\times n$$ identity matrix. Therefore, make: $${\bf A} = \begin{bmatrix} {\bf 1}_n^\top \otimes \mathbb I_m\\ \mathbb I_n \otimes {\bf 1}_m^\top \end{bmatrix}$$
Finally, the constraint $${\bf x}\geq 0$$ is the same as the constraint that the transport plan $$\bf \Gamma$$ must be positive. This can be found in page 38 in the book Computational Optimal Transport, by Peyré and Cuturi. The pdf of the book is freely avaiable.
• if $\boldsymbol c$ contains distances $| x - y|$, how can I reconcile the fact that $\mathbf{b} = \begin{bmatrix} \alpha \\ \beta\end{bmatrix}$ is just a figurative representation of $\bar{\boldsymbol{b}} = \begin{bmatrix} \boldsymbol x \\ \boldsymbol y \end{bmatrix}$, where $\alpha$ is by definition $\boldsymbol x$, the source distribution, and $\beta$ is by definition $\boldsymbol y$, the target distribution? – develarist Nov 30 '20 at 16:28