  


Linear Programming using LimitedPrecision Oracles
Ambros Gleixner (gleixnerzib.de) 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 bitcomplexity analysis. Yet in practice, implementations typically use limitedprecision arithmetic. In this paper we introduce the idea of a limitedprecision 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, extendedprecision arithmetic, iterative refinement Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Optimization Software and Modeling Systems (Other ) Citation: ZIBReport 1957, Zuse Institute Berlin, November 2019 Download: [PDF] Entry Submitted: 12/03/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  