= Exact linear optimization from a feasibility oracle
A <polynomial-time algorithm> for integer linear feasibility gives exact rational <linear programming> optimization. Rational vertex bounds give a polynomial-bit bound on every finite optimal value and its denominator. An objective threshold below that bound detects unboundedness after feasibility is established. Binary search with the additional inequality $c^Tx\leq t$ localizes the finite optimum to an interval containing a unique rational of bounded denominator; <continued fractions> recover it exactly. A feasible optimizer can then be found by successive coordinate minimizations on a bounded optimal face. These produce faces of one fixed rational polytope, so one uniform vertex-denominator bound works throughout, avoiding exponential growth of precision requirements.
Back to article page
