  Motivated by the statistical analysis of the discrete optimal transport
problem, we prove distributional limits for the solutions of linear programs
with random constraints. Such limits were first obtained by Klatt, Munk, &
Zemel (2022), but their expressions for the limits involve a computationally
intractable decomposition of $\mathbb{R}^m$ into a possibly exponential number
of convex cones. We give a new expression for the limit in terms of auxiliary
linear programs, which can be solved in polynomial time. We also leverage tools
from random convex geometry to give distributional limits for the entire set of
random optimal solutions, when the optimum is not unique. Finally, we describe
a simple, data-driven method to construct asymptotically valid confidence sets
in polynomial time.
