Verified Linear Programming through Tolerance-Aware Precision Boosting

DOI10.48550/arXiv.2609.11721MaRDI QIDQ7345620zbMATH OpenarXivFDO

Authors Paolo Zuliani, Sadegh Soudjani, Ernesto Casablanca, Martin Sidaway

Publication date 10 September 2026

Published in arXiv

Tldr We propose a tolerance-aware, precision-boosting simplex algorithm for verified linear programming with formal correctness guarantees and a novel delta-complete termination criterion, allowing users to control the trade-off between numerical stability, computational efficiency, and soundness via adjustable tolerances.

Full work available at URL https://doi.org/10.48550/arXiv.2609.11721

arXiv classification

math.NAmath.OC

Cites work

• -decidability over the reals
• A linear programming bound for orthogonal arrays with mixed levels
• A stabilization of the simplex method
• Algorithms and certificates for exact mixed integer programming
• An overview on the simplex algorithm
• Benchmarking optimization software with performance profiles
• Combining precision boosting with LP iterative refinement for exact linear optimization
• Computational techniques of the simplex method
• Exact solutions to linear programming problems
• Iterative refinement for linear programming
• Linear Programming
• Linear programming using limited-precision oracles
• New Finite Pivoting Rules for the Simplex Method
• On error growth in the Bartels-Golub and Fletcher-Matthews algorithms for updating matrix factorizations
• Parallelizing the dual revised simplex method
• The interior-point revolution in optimization: History, recent developments, and lasting consequences
• The Product Form for the Inverse in the Simplex Method
• Understanding and using linear programming
• Updated triangular factors of the basis to maintain sparsity in the product form simplex method

This page was built for publication: Verified Linear Programming through Tolerance-Aware Precision Boosting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7345620)