Metraipolis › archive › dc_0a32eb65e88a
Verified Linear Programming through Tolerance-Aware Precision Boosting — arXiv:2609.11721
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.11721
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T06:01:07.226Z
- SHA-256 of the archived text
fabd38314e5698a7b6b7ba7f937e155f35e6b85822c5de1439e077b67d731da8- Stable URL of this page
https://metraipolis.com/documento/dc_0a32eb65e88a
How to cite
Verified Linear Programming through Tolerance-Aware Precision Boosting — arXiv:2609.11721 — arXiv (en), https://arxiv.org/abs/2609.11721 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0a32eb65e88a (Metraipolis archive dc_0a32eb65e88a, sha256 fabd38314e5698a7b6b7ba7f937e155f35e6b85822c5de1439e077b67d731da8)
BibTeX
@misc{dc0a32eb65e88a,
title = {Verified Linear Programming through Tolerance-Aware Precision Boosting — arXiv:2609.11721},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.11721},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0a32eb65e88a; sha256 fabd38314e5698a7b6b7ba7f937e155f35e6b85822c5de1439e077b67d731da8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11721. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Linear programming plays a fundamental role in computer science, with applications in optimization, formal verification, SMT solving, and numerous other domains. When exactness guarantees are required, numerical inaccuracies arising from floating-point arithmetic can compromise soundness, whereas exact rational arithmetic often incurs significant computational overhead. In this paper, we investigate the numerical stability of the simplex algorithm and establish conditions under which a precision-boosting floating-point implementation provably produces the same pivot decisions and final basis as an exact rational implementation, from which the final result is reconstructed and certified exactly. Our analysis shows that correctness depends on both arithmetic precision and a careful handling of numerical tolerances. Based on these results, we develop a tolerance-aware, precision-boosting simplex algorithm with formal correctness guarantees. Finally, we introduce a delta-complete termination criterion that allows the algorithm to terminate once certified upper and lower bounds on the optimal objective differ by at most a user-specified threshold delta, providing a certified, user-controlled optimality gap. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-11 in math.OC). Categorie arXiv: Optimization and Control (math.OC) ; Numerical Analysis (math.NA). Pagina del lavoro: https://arxiv.org/abs/2609.11721 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T05:52:41.419Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).