On finding exact solutions of linear programs in the oracle model

We consider linear programming in the oracle model: mincT x s.t. x ∊ P, where the polyhedron P = {x ∊ ℝn: Ax ≤ b} is given by a separation oracle that returns violated inequalities from the system Ax ≤ b. We present an algorithm that finds exact primal and dual solutions using O(n2 log(n/δ)) oracle calls and O(n4 log(n/δ) + n6 log log(1/δ)) arithmetic operations, where δ is a geometric condition number associated with the system (A, b). These bounds do not depend on the cost vector c. The algorithm works in a black box manner, requiring a subroutine for approximate primal and dual solutions; the above running times are achieved when using the cutting plane method of Jiang, Lee, Song, and Wong (STOC 2020) for this subroutine. Whereas approximate solvers may return primal solutions only, we develop a general framework for extracting dual certificates based on the work of Burrell and Todd (Math. Oper. Res. 1985). Our algorithm works in the real model of computation, and extends results by Grötschel, Lovász, and Schrijver (Prog. Comb. Opt. 1984), and by Frank and Tardos (Combinatorica 1987) on solving LPs in the bit-complexity model. We show that under a natural assumption, simultaneous Diophantine approximation in these results can be avoided.

• View at Publisher

Free Full Text ( Final Version , 1mb )