Rigorous Lower and Upper Bounds in Linear Programming

Publisher Website
Google Scholar
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.

This publication has 11 references indexed in Scilit: