Rigorous Lower and Upper Bounds in Linear Programming
Author:
- Christian JanssonCJChristian Jansson
- 1 January 2004
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 14 (3) , 914-935
Abstract
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(n 2 ) 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.Keywords
This publication has 11 references indexed in Scilit:
- Safe bounds in linear and mixed-integer linear programmingMathematical Programming, 2004
- Computational Experience and the Explanatory Value of Condition Measures for Linear OptimizationSIAM Journal on Optimization, 2003
- Introduction to Numerical Analysis2001
- Deterministic Global Optimization2000
- Rigorous Global Search: Continuous Problems1996
- A global optimization algorithm for linear fractional and bilinear programsJournal of Global Optimization, 1995
- An improved branch and bound algorithm for mixed integer nonlinear programsComputers & Operations Research, 1994
- On the Implementation of a Primal-Dual Interior Point MethodSIAM Journal on Optimization, 1992
- Iterative methods for interval inclusion of fixed pointsBIT Numerical Mathematics, 1978
- Pracniques: construction of nonlinear programming test problemsCommunications of the ACM, 1965