Rigorous lower and upper bounds in linear programming

Download source code: rigorousLP.c
Output: output_gcc.txt output_win32.txt

My aim is to have an efficient implementation which does not depend on any interval library, yet works on many platforms. The implementation should use the sparse data structures of the LP solver.

Considering these aims, I have implemented a demo program of the algorithm of Neumaier and Shcherbina using GNU GLPK as LP solver. The implementation is very rough, currently only two compilers are supported (gcc on Linux and M$ VC on Win32), suggestions and help are welcome. I would like to extend my source code: if GLPK is used as an MILP solver then every node of the search tree should be checked with directed rounding. I also plan to implement this procedure for ILOG CPLEX. However, due to my various occupations it is not likely I will deal with it in the foreseeable future.

Far more advanced codes exist than mine, e. g.: Verified SemiDefinite Programming in Matlab-toolbox INTLAB (Prof. Jansson), Lurupa in C++ (Dr. Keil) or Verification software in MATLAB / INTLAB (Prof. Rohn).

It is important to mention here that the bound swapping dual algorithm, a variant of the dual simplex method, is very efficient if all variables have lower and upper bounds (box constrained variables, in case of interval methods it is always true). This method is also referred to as the bound flipping ratio test (BFRT, see also A. Koberstein, I. Maros a, I. Maros b, E. Kostina, R. Fourer, H. J. Greenberg). An open-source implementation of this method as available in the Coin-Or Clp solver. Unfortunately, I could not figure out the proper configuration of this LP solver, GLPK proved to be more stable with the its default settings.