On finding exact solutions of linear programs in the oracle model

Daniel Dadush, László A. Végh, Giacomo Zambelli

We consider linear programming in the oracle model: $\max \{c^{\top }x:x\in P\}$, where the polyhedron $P=\{x\in {\mathbb{R}}^n:Ax\le b\}$ is given by a separation oracle. We…