Optimization Online


Linear Programming using Limited-Precision Oracles

Ambros Gleixner (gleixner***at***zib.de)
Daniel E. Steffy (steffy***at***oakland.edu)

Abstract: Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.

Keywords: Linear programming, oracle complexity, Diophantine approximation, exact solutions, symbolic computation, rational arithmetic, extended-precision arithmetic, iterative refinement

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Optimization Software and Modeling Systems (Other )

Citation: ZIB-Report 19-57, Zuse Institute Berlin, November 2019

Download: [PDF]

Entry Submitted: 12/03/2019
Entry Accepted: 12/03/2019
Entry Last Modified: 12/03/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society