extension: .md

format_name: myst

format_version: 0.13

jupytext_version: 1.10.3

jupytext_version: 1.14.4

kernelspec:

display_name: Python 3

display_name: Python 3 (ipykernel)

language: python

name: python3

---

2. the [linprog_simplex](https://quanteconpy.readthedocs.io/en/latest/optimize/linprog_simplex.html) solver from QuantEcon and

3. the simplex-based solvers included in the [Python Optimal Transport](https://pythonot.github.io/) package.

```{code-cell} ipython3

:tags: [hide-output]

!pip install --upgrade quantecon

!pip install --upgrade POT jax jaxlib

!pip install --upgrade POT

```

Let's start with some imports.

import networkx as nx

```

## The Optimal Transport Problem

Suppose that $m$ factories produce goods that must be sent to $n$ locations.

b = np.hstack([p, q])

# Solve the primal problem

res = linprog(C_vec, A_eq=A, b_eq=b, method='Revised simplex')

res = linprog(C_vec, A_eq=A, b_eq=b)

# Print results

print("message:", res.message)

Though it is a different plan, it attains the same cost!

```{code-cell} ipython3

linprog(C_vec, A_eq=A[:-1], b_eq=b[:-1], method='Revised simplex')

linprog(C_vec, A_eq=A[:-1], b_eq=b[:-1])

```

```{code-cell} ipython3

%time linprog(C_vec, A_eq=A[:-1], b_eq=b[:-1], method='Revised simplex')

%time linprog(C_vec, A_eq=A[:-1], b_eq=b[:-1])

```

```{code-cell} ipython3

%time linprog(C_vec, A_eq=A, b_eq=b, method='Revised simplex')

%time linprog(C_vec, A_eq=A, b_eq=b)

```

Evidently, it is slightly quicker to work with the system that removed a redundant constraint.

for i in range(1000):

np.random.shuffle(arr)

res_shuffle = linprog(C_vec, A_eq=A[arr], b_eq=b[arr], method='Revised simplex')

res_shuffle = linprog(C_vec, A_eq=A[arr], b_eq=b[arr])

# if find a new solution

sol = tuple(res_shuffle.x)

Next, we show that leaving out the first constraint "accidentally" leads to the initial plan that we computed.

```{code-cell} ipython3

linprog(C_vec, A_eq=A[1:], b_eq=b[1:], method='Revised simplex')

linprog(C_vec, A_eq=A[1:], b_eq=b[1:])

```

Let's compare this transport plan with

### Using a Just-in-Time Compiler

We can also solve optimal transportation problems using a powerful tool from

QuantEcon, namely,`quantecon.optimize.linprog_simplex`.

QuantEcon, namely, `quantecon.optimize.linprog_simplex`.

While this routine uses the same simplex algorithm as

`scipy.optimize.linprog`, the code is accelerated by using a just-in-time

```{code-cell} ipython3

# scipy.optimize.linprog

%time res = linprog(C_vec, A_eq=A[:-1, :], b_eq=b[:-1], method='Revised simplex')

%time res = linprog(C_vec, A_eq=A[:-1, :], b_eq=b[:-1])

```

```{code-cell} ipython3

```{code-cell} ipython3

# Solve the dual problem

res_dual = linprog(-b, A_ub=A.T, b_ub=C_vec,

bounds=[(None, None)]*(m+n), method='Revised simplex')

bounds=[(None, None)]*(m+n))

#Print results

print("message:", res_dual.message)

We can compare computational times from using our two tools.

```{code-cell} ipython3

%time linprog(-b, A_ub=A.T, b_ub=C_vec, bounds=[(None, None)]*(m+n), method='Revised simplex')

%time linprog(-b, A_ub=A.T, b_ub=C_vec, bounds=[(None, None)]*(m+n))

```

```{code-cell} ipython3

```{code-cell} ipython3

linprog(-b[1:], A_ub=A[1:].T, b_ub=C_vec,

bounds=[(None, None)]*(m+n-1), method='Revised simplex')

bounds=[(None, None)]*(m+n-1))

```

Not let's instead leave out the last constraint:

```{code-cell} ipython3

linprog(-b[:-1], A_ub=A[:-1].T, b_ub=C_vec,

bounds=[(None, None)]*(m+n-1), method='Revised simplex')

bounds=[(None, None)]*(m+n-1))

```

### Interpretation of dual problem

Sure enough, we have the same solution and the same cost

```{code-cell} ipython3

total_cost = np.sum(X * C)

total_cost

Locations are assigned randomly.

```{code-cell} ipython3

def build_nodes_of_one_type(group='p', n=100, seed=123):

Now we build two lists of nodes, each one containing one type (factories or

locations)

```{code-cell} ipython3

n_p = 32

n_q = 32

connectionstyle='arc3,rad=0.1',

alpha=0.6)

plt.show()

```

```{code-cell} ipython3

```