zbMATH — the first resource for mathematics

Solving multiscale linear programs using the simplex method in quadruple precision. (English) Zbl 1330.65088
Al-Baali, Mehiddin (ed.) et al., Numerical analysis and optimization. Selected papers based on the presentations at the 3rd international conference, NAO-III, Muscat, Oman, January 5–9, 2014. Cham: Springer (ISBN 978-3-319-17688-8/hbk; 978-3-319-17689-5/ebook). Springer Proceedings in Mathematics & Statistics 134, 223-235 (2015).
Summary: Systems biologists are developing increasingly large models of metabolism and integrated models of metabolism and macromolecular expression. These metabolic expression (ME) models lead to sequences of multiscale linear programs for which small solution values of order \(10^{-6}\) to \(10^{-10}\) are meaningful. Standard linear programming (LP) solvers do not give sufficiently accurate solutions, and exact simplex solvers are extremely slow. We investigate whether double-precision and quadruple-precision simplex solvers can together achieve reliability at acceptable cost.
A double-precision LP solver often provides a reasonably good starting point for a Quad simplex solver. On a range of multiscale examples we find that 34-digit Quad floating-point achieves exceptionally small primal and dual infeasibilities (of order \(10^{-30}\)) when no more than \(10^{-15}\) is requested. On a significant ME model we also observe robustness in almost all (even small) solution values following relative perturbations of order \(10^{-6}\) to non-integer data values.
Double and Quad Fortran 77 implementations of the linear and nonlinear optimization solver MINOS are available upon request.
For the entire collection see [Zbl 1326.65008].

65K05 Numerical mathematical programming methods
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
90C05 Linear programming
92-08 Computational methods for problems pertaining to biology
Full Text: DOI