All Linear and Integer Programs Are Slim 3‐Way Transportation Programs
Jesús A. De Loera, Shmuel Onn · SIAM Journal on Optimization · 2006
We show that any rational convex polytope is polynomial‐time representable as a 3‐way line‐sum transportation polytope of “slim” $(r,c,3)$ format. This universality theorem has important consequences for linear and integer programming and for confidential statistical data disclosure. We provide a polynomial‐time embedding of arbitrary linear programs and integer programs in such slim transportation programs and in bitransportation programs. Our construction resolves several standing problems on 3‐way transportation polytopes. For example, it demonstrates that, unlike the case of 2‐way contingency tables, the range of values an entry can attain in any slim 3‐way contingency table with specified 2‐margins can contain arbitrary gaps. Our smallest such example has format $(6,4,3)$. Our construction provides a powerful automatic tool for studying concrete questions about transportation polytopes and contingency tables. For example, it automatically provides new proofs for some classical results, including a well‐known “real‐feasible but integer‐infeasible” $(6,4,3)$‐transportation polytope of M. Vlach, and bitransportation programs where any feasible bitransportation must have an arbitrarily large prescribed denominator.