Jansson, C. and Rump, S.M. (1991) Rigorous Solution of Linear Programming Problems with Uncertain Data. Zeitschrift für Operations Research, 35, 87-111.

has been cited by the following article:

• TITLE: Safe Bounds in Semidefinite Programming by Using Interval Arithmetic

  AUTHORS: Orkia Derkaoui, Ahmed Lehireche

  KEYWORDS: Semidefinite Programming, Interval Arithmetic, Rigorous Error, Bounds, SDPA Solver, Branch and Bound Algorithm

  JOURNAL NAME: American Journal of Operations Research, Vol.4 No.5, September 15, 2014

  ABSTRACT: Efficient solvers for optimization problems are based on linear and semidefinite relaxations that use floating point arithmetic. However, due to the rounding errors, relaxation thus may overestimate, or worst, underestimate the very global optima. The purpose of this article is to introduce an efficient and safe procedure to rigorously bound the global optima of semidefinite program. This work shows how, using interval arithmetic, rigorous error bounds for the optimal value can be computed by carefully post processing the output of a semidefinite programming solver. A lower bound is computed on a semidefinite relaxation of the constraint system and the objective function. Numerical results are presented using the SDPA (SemiDefinite Programming Algorithm), solver to compute the solution of semidefinite programs. This rigorous bound is injected in a branch and bound algorithm to solve the optimisation problem.