Linear programming using limited-precision oracles

DOI10.1007/s10107-019-01444-6zbMath1450.90006arXiv1912.12820OpenAlexW3011671470WikidataQ126783486 ScholiaQ126783486MaRDI QIDQ5918922

Ambros M. Gleixner, Daniel E. Steffy

Publication date: 28 August 2020

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.12820

zbMATH Keywords

linear programmingsymbolic computationDiophantine approximationexact solutionsiterative refinementrational arithmeticoracle complexityextended-precision arithmetic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Interval and finite arithmetic (65G30) Diophantine approximation in probabilistic number theory (11K60)

Related Items

A note on the Tuza constant \(c_k\) for small \(k\), Safe and Verified Gomory Mixed-Integer Cuts in a Rational Mixed-Integer Program Framework, A computational status update for exact rational mixed integer programming, A computational status update for exact rational mixed integer programming

Uses Software

• IML - Integer Matrix Library
• SoPlex
• MIPLIB
• QSopt_ex
• QSopt-Exact

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Factoring polynomials with rational coefficients
• Geometric algorithms and combinatorial optimization
• The final NETLIB-LP results
• Exact arithmetic at low cost. -- A case study in linear programming
• Exact solutions to linear programming problems
• Solving linear programs with finite precision. II: Algorithms
• How Tight is Hadamard's Bound?
• Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations
• Iterative Refinement for Linear Programming
• Solving Very Sparse Rational Systems of Equations
• An LLL Algorithm with Quadratic Complexity
• Polynomial algorithms in linear programming
• Note sur les $Q$-matrices d’Edmonds
• Acceleration of Euclidean Algorithm and Rational Number Reconstruction
• Exact solutions to linear systems of equations using output sensitive lifting
• A BLAS based C library for exact linear algebra on integer matrices
• Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates
• Systems of distinct representatives and linear algebra