# Integer solution of optimal transport

Let us consider two vectors $$\mathbf{a}=(a_1,...,a_n)$$ and $$\mathbf{b}=(b_1,...,b_m)$$ so that each quantity is an integer $$a_i,b_j \in \mathbb{N}$$. It represents for example supply and demand. Let $$\mathbf{C}=(c_{ij})_{ij} \in \mathbb{R}_{+}^{n \times m}$$ be a matrix representing the cost of transporting goods from $$i$$ to $$j$$.

My question is the following: can we guarantee that a solution of the Optimal transport problem between $$\mathbf{a}$$ and $$\mathbf{b}$$ is a matrix whose elements are integer?

More precisely I am interested in the solutions of the following Optimal Transport problem: $$$$\underset{\boldsymbol\pi \in \Pi(\mathbf{a},\mathbf{b})}{\min} \sum_{i=1,j=1}^{n,m}c_{ij}\pi_{ij}=\underset{\pi \in \Pi(\mathbf{a},\mathbf{b})}{\min} \langle \mathbf{C},\boldsymbol\pi \rangle$$$$

where $$\Pi(\mathbf{a},\mathbf{b})$$ is the "transport" polytope defined by: $$$$\Pi(\mathbf{a},\mathbf{b})=\{\boldsymbol\pi \in \mathbb{R}^{n \times m} \ | \pi_{ij}\geq 0; \ \forall j, \ \sum_{i=1}^{n} \pi_{ij}=b_j; \ \forall i, \ \sum_{j=1}^{m} \pi_{ij}=a_i\}$$$$ In this way $$\pi_{ij}$$ is the amount of goods transferred from $$i$$ to $$j$$ so that the overall amount is preserved. (Remark: usually this problem is considered with histograms but here I am not normalizing the quantities.)

We can solve this problem using the simplex algorithm for example.

More formally my question is: can we guarantee that there exists an optimal transport plan $$\boldsymbol\pi^{*}$$ of the previous problem such that $$\pi^{*}_{ij}$$ is an integer?

• My hint:

The problem is a standard linear program (LP) as it can be written: $$$$\underset{\begin{smallmatrix}\mathbf{p} \in \mathbb{R}_{+}^{nm} \\ \mathbf{A}\mathbf{p}=\begin{pmatrix} \mathbf{a} \\ \mathbf{b} \end{pmatrix} \end{smallmatrix}}{\min} \mathbf{c}^{\top} \mathbf{p}$$$$

by vectorizing all the quantities, i.e. $$\mathbf{c}$$ is $$nm$$ vectors equal to the stacked columns contains in $$\mathbf{C}$$ and same for $$\mathbf{p}$$ which corresponds to $$\boldsymbol\pi$$. In this form the constraint matrix writes: $$$$\mathbf{A}=\begin{pmatrix}\mathbf{1}_n^{\top} \otimes I_m \\ I_n \otimes \mathbf{1}_m^{\top} \end{pmatrix} \in \mathbb{R}^{(n+m)\times nm}$$$$

where $$\otimes$$ is the Kronecker product, $$I_n$$ the identity matrix of size $$n$$ and $$\mathbf{1}_n$$ is a vector of ones of size $$n$$. This problem is a relaxation of the Integer Linear Programming (ILP) problem where elements of $$\mathbf{p}$$ are constrained to be integers (which is want we want). Solving (ILP) is NP-hard in general and we can use the (LP) relaxation and round the entries but the solution may not be optimal, and even not feasible.

However as written in [1] (see also https://en.wikipedia.org/wiki/Integer_programming) elements of an optimal solution of the (LP) are integers when $$\mathbf{A}$$ is totally unimodular, that is every square submatrix of $$\mathbf{A}$$ has determinant $$0,+1$$ or $$-1$$. Is $$\mathbf{A}$$ totally unimodular in this case?

• More generally, network flow problems have totally unimodular constraint matrices. A sufficient condition is to have two nonzero entries in each column, with exactly one $1$ and exactly one $-1$. Oct 26 '20 at 14:20