Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision

Ding Ma; Michael A. Saunders

doi:10.1007/978-3-319-17689-5_9

Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision

Ding Ma, Michael A. Saunders^*

^*Corresponding author for this work

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

15 Citations (Scopus)

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⁻⁶ to 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⁻³⁰) when no more than 10⁻¹⁵ is requested. On a significant ME model we also observe robustness in almost all (even small) solution values following relative perturbations of order 10⁻⁶ to non-integer data values.
Double and Quad Fortran 77 implementations of the linear and nonlinear optimization solver MINOS are available upon request.

Original language	English
Title of host publication	Numerical Analysis and Optimization
Editors	Mehiddin Al-Baali, Lucio Grandinetti, Anton Purnama
Publisher	Springer International Publishing
Pages	223–235
ISBN (Electronic)	9783319176895
ISBN (Print)	9783319176888
DOIs	https://doi.org/10.1007/978-3-319-17689-5_9
Publication status	Published - 2015
Externally published	Yes
Event	3rd International Conference on Numerical Analysis and Optimization (NAO-III 2014) - Muscat, Oman Duration: 5 Jan 2014 → 9 Jan 2014

Publication series

Name	Springer Proceedings in Mathematics & Statistics
Volume	134
ISSN (Print)	2194-1009
ISSN (Electronic)	2194-1017

Conference

Conference	3rd International Conference on Numerical Analysis and Optimization (NAO-III 2014)
Abbreviated title	NAO-III 2014
Country/Territory	Oman
City	Muscat
Period	5/01/14 → 9/01/14

Research Keywords

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

Access Output

10.1007/978-3-319-17689-5_9

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{c32cbc8e2fdb42679344e49272827eeb,

title = "Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision",

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

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

author = "Ding Ma and Saunders, {Michael A.}",

year = "2015",

doi = "10.1007/978-3-319-17689-5_9",

language = "English",

isbn = "9783319176888",

series = "Springer Proceedings in Mathematics & Statistics",

publisher = "Springer International Publishing ",

pages = "223–235",

editor = "Mehiddin Al-Baali and Lucio Grandinetti and Anton Purnama",

booktitle = "Numerical Analysis and Optimization",

address = "Switzerland",

note = "3rd International Conference on Numerical Analysis and Optimization (NAO-III 2014), NAO-III 2014 ; Conference date: 05-01-2014 Through 09-01-2014",

}

Ma, D & Saunders, MA 2015, Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision. in M Al-Baali, L Grandinetti & A Purnama (eds), Numerical Analysis and Optimization. Springer Proceedings in Mathematics & Statistics, vol. 134, Springer International Publishing , pp. 223–235, 3rd International Conference on Numerical Analysis and Optimization (NAO-III 2014), Muscat, Oman, 5/01/14. https://doi.org/10.1007/978-3-319-17689-5_9

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 , 2015. p. 223–235 (Springer Proceedings in Mathematics & Statistics; Vol. 134).

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

TY - GEN

T1 - Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision

AU - Ma, Ding

AU - Saunders, Michael A.

PY - 2015

Y1 - 2015

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

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

KW - Flux balance analysis

KW - Metabolic expression model

KW - Multiscale linear program

KW - Simplex method

KW - Quadruple precision

KW - Gfortran libquadmath

KW - MINOS

UR - http://www.scopus.com/inward/record.url?scp=84947073615&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84947073615&origin=recordpage

U2 - 10.1007/978-3-319-17689-5_9

DO - 10.1007/978-3-319-17689-5_9

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783319176888

T3 - Springer Proceedings in Mathematics & Statistics

SP - 223

EP - 235

BT - Numerical Analysis and Optimization

A2 - Al-Baali, Mehiddin

A2 - Grandinetti, Lucio

A2 - Purnama, Anton

PB - Springer International Publishing

T2 - 3rd International Conference on Numerical Analysis and Optimization (NAO-III 2014)

Y2 - 5 January 2014 through 9 January 2014

ER -

Solving Multiscale Linear Programs Using the Simplex Method in Quadruple Precision

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this