What does Optimal Transport for Luxury Stock Transfers conclude, in numbers, about “Entropic Regularisation and Sinkhorn: Faster, but Blurred”?
Answer: Chapter 4 shows that entropic regularisation with the Sinkhorn iteration costs only 0.0033 more at a temperature of 10 yuan, but its blurred sheets cannot be shipped as they are.
Scope of the numbers: Chapter 5 applies optimal transport to client migration: in an illustrative matrix, gross movement is 13.43 times what the net change requires, so goods follow net flows and people follow gross flows. Chapter 7 examines equitable transport in the Treatise on the Balanced Standard of the Shiji (lateral transfers save 0.721 of freight in an illustrative model) and Monge's cuttings and fillings.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 0.0033, 10
| exact MODI cost 1281; 20 possible routes, optimum uses 8 | |||||
| eps | iters | <C,P> | excess | routes>0.05 | routes>0.5 |
| 100.0 | 11 | 1877.28 | 0.4655 | 20 | 14 |
| 50.0 | 19 | 1561.22 | 0.2187 | 20 | 10 |
| 20.0 | 59 | 1323.32 | 0.0330 | 12 | 8 |
| 10.0 | 106 | 1285.29 | 0.0033 | 9 | 8 |
| 5.0 | 134 | 1281.13 | 0.0001 | 8 | 8 |
| 2.0 | 190 | 1281.00 | 0.0000 | 8 | 8 |
| 1.0 | 282 | 1281.00 | 0.0000 | 8 | 8 |
Show the full program
# Chapter 4. p41: entropic regularisation and Sinkhorn on network A.
# Minimise <C, P> - eps * H(P) with the same margins as p21; the
# solution is P_ij = exp((f_i + g_j - c_ij) / eps), found by alternate
# scaling of rows and columns (Sinkhorn 1964; Cuturi 2013). Log-domain
# updates keep small eps stable. Stop when every row sum is within
# 1e-9 of its target. Compared with the exact MODI cost of network A.
import math
# 十一城经纬度(取整到 0.1 度);单位搬运费 = 30 + 0.1 * 公里,取整(示意:
# 含保价快递与门店交接,非任何承运商报价)
CITY = {"BJ": (116.4, 39.9), "TJ": (117.2, 39.1), "SH": (121.5, 31.2),
"HZ": (120.2, 30.3), "NJ": (118.8, 32.1), "GZ": (113.3, 23.1),
"SZ": (114.1, 22.5), "CD": (104.1, 30.7), "CQ": (106.5, 29.6),
"WH": (114.3, 30.6), "XA": (108.9, 34.3)}
def km(a, b):
(x1, y1), (x2, y2) = CITY[a], CITY[b]
dx = (x1 - x2) * 111.0 * math.cos(math.radians((y1 + y2) / 2.0))
return math.hypot(dx, (y1 - y2) * 111.0)
def unit_cost(a, b):
return 30 + round(0.1 * km(a, b))
def northwest(s, d):
# 西北角初解:阶梯形走 m + n - 1 步,保证基是一棵生成树
s, d = list(s), list(d)
m, n = len(s), len(d)
x = [[0] * n for _ in range(m)]
basis = []
i = j = 0
while True:
q = min(s[i], d[j])
x[i][j] = q
basis.append((i, j))
s[i] -= q
d[j] -= q
if i == m - 1 and j == n - 1:
break
if s[i] == 0 and i < m - 1:
i += 1
else:
j += 1
return x, basis
def potentials(c, basis, m, n):
# 位势:基格上 u_i + v_j = c_ij,取 u_0 = 0
u = [None] * m
v = [None] * n
u[0] = 0
while None in u or None in v:
for i, j in basis:
if u[i] is not None and v[j] is None:
v[j] = c[i][j] - u[i]
elif v[j] is not None and u[i] is None:
u[i] = c[i][j] - v[j]
return u, v
def tree_path(basis, i, j):
# 基树中从列 j 走回行 i 的格子序列(闭回路去掉入基格)
adj = {}
for a, b in basis:
adj.setdefault(("r", a), []).append(("c", b))
adj.setdefault(("c", b), []).append(("r", a))
prev = {("r", i): None}
todo = [("r", i)]
while todo:
node = todo.pop()
for nb in adj.get(node, []):
if nb not in prev:
prev[nb] = node
todo.append(nb)
path, node = [], ("c", j)
while prev[node] is not None:
p = prev[node]
cell = (p[1], node[1]) if p[0] == "r" else (node[1], p[1])
path.append(cell)
node = p
return path
def modi(c, s, d, x=None, basis=None, trace=None):
# 位势法(MODI):检验数 r_ij = c_ij - u_i - v_j 全部非负即最优
m, n = len(s), len(d)
if x is None:
x, basis = northwest(s, d)
x = [row[:] for row in x]
basis = list(basis)
steps = 0
while True:
u, v = potentials(c, basis, m, n)
best, cell = 0, None
for i in range(m):
for j in range(n):
r = c[i][j] - u[i] - v[j]
if r < best:
best, cell = r, (i, j)
if cell is None:
return x, basis, u, v, steps
i, j = cell
path = tree_path(basis, i, j)
minus, plus = path[0::2], path[1::2]
theta = min(x[a][b] for a, b in minus)
out = [e for e in minus if x[e[0]][e[1]] == theta][0]
x[i][j] += theta
for a, b in minus:
x[a][b] -= theta
for a, b in plus:
x[a][b] += theta
basis.remove(out)
basis.append(cell)
steps += 1
if trace is not None:
trace.append((cell, best, theta, out))
def total(c, x):
return math.fsum(c[i][j] * x[i][j]
for i in range(len(x)) for j in range(len(x[0])))
def lse(vals):
top = max(vals)
return top + math.log(math.fsum(math.exp(w - top) for w in vals))
def sinkhorn(c, s, d, eps, tol=1e-9, cap=200000):
# 对数域 Sinkhorn:f_i = eps*log s_i - eps*LSE_j((g_j - c_ij)/eps)
m, n = len(s), len(d)
f, g = [0.0] * m, [0.0] * n
for it in range(1, cap + 1):
f = [eps * math.log(s[i]) - eps * lse(
[(g[j] - c[i][j]) / eps for j in range(n)]) for i in range(m)]
g = [eps * math.log(d[j]) - eps * lse(
[(f[i] - c[i][j]) / eps for i in range(m)]) for j in range(n)]
p = [[math.exp((f[i] + g[j] - c[i][j]) / eps) for j in range(n)]
for i in range(m)]
err = max(abs(math.fsum(p[i]) - s[i]) for i in range(m))
if err < tol:
break
return p, f, g, it
SUP, S = ["SH", "SZ", "TJ", "CD"], [6, 5, 5, 2]
DEM, D = ["BJ", "CQ", "HZ", "WH", "GZ"], [3, 3, 5, 5, 2]
C = [[unit_cost(a, b) for b in DEM] for a in SUP]
exact = total(C, modi(C, S, D)[0])
print("exact MODI cost %d; 20 possible routes, optimum uses 8" % exact)
print(" eps iters <C,P> excess routes>0.05 routes>0.5")
for eps in (100.0, 50.0, 20.0, 10.0, 5.0, 2.0, 1.0):
p, f, g, it = sinkhorn(C, S, D, eps)
cost = math.fsum(C[i][j] * p[i][j] for i in range(4) for j in range(5))
r1 = len([1 for row in p for w in row if w > 0.05])
r2 = len([1 for row in p for w in row if w > 0.5])
ex = cost / exact - 1.0
ex = 0.0 if abs(ex) < 5e-5 else ex
print("%6.1f %7d %8.2f %8.4f %11d %11d" % (eps, it, cost, ex, r1, r2))Single source and citation
Fan, Y. (2026). Optimal Transport and Kantorovich Duality: Minimum-Cost Rebalancing of Luxury Stock across Regions and Client-Migration Matrices (Version 1.0.0), Chapter 4: Entropic Regularisation and Sinkhorn: Faster, but Blurred. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-233 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026233,
author = {Fan, Yafu},
title = {Optimal Transport and Kantorovich Duality: Minimum-Cost Rebalancing of Luxury Stock across Regions and Client-Migration Matrices},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Price of Serving the Emptiest Shelf First: Greedy Transfers against the Transportation Optimum
- Chapter 2 · The Potential Method: Northwest-Corner Starts, Closed Loops and an Exact MODI Solution
- Chapter 3 · Kantorovich Duality: Potentials Are the Shadow Prices of Stores
- Chapter 5 · Client-Migration Matrices: Measuring Real Movement by the Least Movement Required
- Chapter 6 · Whole Units, Fees per Shipment and Moving Rates: From a Linear Optimum to an Executable Transfer Sheet
- Chapter 7 · East and West in the Sources: Sang Hongyang's Equitable Transport and Monge's Cuttings and Fillings
- Chapter 8 · Closing the Loop: The Weekly Transfer Sheet, the Shadow Price Table and Human Release