Options
Rigorous lower and upper bounds in linear programming
Publikationstyp
Journal Article
Date Issued
2004-07-28
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
14
Issue
3
Start Page
914
End Page
935
Citation
SIAM Journal on Optimization 14 (3): 914-935 (2004)
Publisher DOI
Scopus ID
Publisher
SIAM
We consider the computation of rigorous lower and upper error bounds for the optimal value of linear programming problems. The input data of the lp-problem may be exactly given or may vary between given lower and upper bounds. The results are then verified for the family of lp-problems with input data inside these bounds. In many cases only a small computational effort is required. For problems with finite simple bounds, the rigorous lower bound of the optimal value can be computed with O(n2) operations. The error bounds can be used as well to perform a sensitivity analysis, provided the width of the uncertainties is not too large. Some numerical examples are presented.
Subjects
Interval arithmetic
Linear programming
Rigorous error bounds
Sensitivity analysis
DDC Class
510: Mathematik