Ismail I. Idriss and Wolfgang V. Walter
Institute of Applied Computer Sceince
Technical University Dresden
D-01062 Dresden, Germany
mailto: idriss@inf.tu-dresden.de
Approximate solutions of linear programming problems can be computed by various algorithms. Recently developed interior-point methods solve such problems in polynomial time. In practice, a linear programming problem is solved using a computer program which usually reports an approximation of the optimal solution, but gives no reliable estimate of the error. This can lead to completely wrong results or to an erroneous interpretation of the results. This paper proposes a verification method which proves or disproves the existence of a solution on a computer and, if it exists, encloses this solution in narrow bounds. This method is designed via reformulation of the linear programming problem as an equivalent system of nonlinear equations and uses mean value interval extensions of functions and a computational fixed point theorem.