Solving multiscale linear programs using the simplex method in quadruple precision. (English) Zbl 1330.65088

Ma, Ding; Saunders, Michael A.

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].

MSC:

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

Keywords:

flux balance analysis; metabolic expression model; multiscale linear program; simplex method; quadruple precision; gfortran libquadmath; MINOS; numerical examples; macromolecular expression

Software:

CPLEX; Gurobi; libquadmath; LUSOL; Mosek; NETLIB LP Test Set; NLPLIB; OPERA; QSopt_ex; SNOPT; SoPlex; TOMLAB; XPRESS