Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

15 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Title of host publicationNumerical Analysis and Optimization
EditorsMehiddin Al-Baali, Lucio Grandinetti, Anton Purnama
PublisherSpringer International Publishing Switzerland
Pages223–235
ISBN (electronic)9783319176895
ISBN (print)9783319176888
Publication statusPublished - 2015
Externally publishedYes

Publication series

NameSpringer Proceedings in Mathematics & Statistics
Volume134
ISSN (Print)2194-1009
ISSN (electronic)2194-1017

Conference

Title3rd International Conference on Numerical Analysis and Optimization (NAO-III 2014)
PlaceOman
CityMuscat
Period5 - 9 January 2014

Abstract

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

Research Area(s)

  • Flux balance analysis, Metabolic expression model, Multiscale linear program, Simplex method, Quadruple precision, Gfortran libquadmath, MINOS

Citation Format(s)

Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision. / Ma, Ding; Saunders, Michael A.
Numerical Analysis and Optimization. ed. / Mehiddin Al-Baali; Lucio Grandinetti; Anton Purnama. Springer International Publishing Switzerland, 2015. p. 223–235 (Springer Proceedings in Mathematics & Statistics; Vol. 134).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review