Research
Publications
2008
A Comparison of Software Packages for Verified Linear Programming
C. Keil, submitted to SIOPT (SIAM Journal on Optimization).
Linear programming is arguably one of the most basic forms of optimization. Its theory and algorithms can not only be applied to linear optimization problems but also to relaxations of nonlinear problems and branch-and-bound methods for mixed-integer and global optimization problems.
Recent research shows that against intuition bad condition numbers frequently occur in linear programming. To take this into account reliability is required. Here we investigate rigorous results obtained by verification methods. We will examine different current techniques and software tools for verified linear programming and compare numerical results for existing implementations.
Preprint: PDF
Test problems: ICOS (2.6MB), RealPaver (2.0MB), GlobSol (1.9MB), Random problems (13.2MB)To obtain the random problems you first have to extract the Random.tar.gz archive. This contains the compressed random LPs. These in turn have to be expanded with bzip2 and finally with the emps tool from Netlib. Beware that some of these quite large if decompressed (close to 100MB for the problems with 1500 variables).
The MPS formulations of the Netlib real-world problems can also be found at their repository.
The problems from the Meszaros collection can be found here.
2007
Rigorous Error Bounds for the Optimal Value in Semidefinite Programming
C. Jansson, D. Chaykin, and C. Keil, SIAM J. Numer. Anal. 46, 180 (2007), DOI:10.1137/050622870
A wide variety of problems in global optimization, combinatorial optimization as well as systems and control theory can be solved by using linear and semidefinite programming. Sometimes, due to the use of floating point arithmetic in combination with ill-conditioning and degeneracy, erroneous results may be produced. The purpose of this article is to show how rigorous error bounds for the optimal value can be computed by carefully postprocessing the output of a linear or semidefinite programming solver. It turns out that in many cases the computational costs for postprocessing are small compared to the effort required by the solver. Numerical results are presented including problems from the SDPLIB and the NETLIB LP library; these libraries contain many ill-conditioned and real life problems.
Preprint: PDF, zipped Postscript
2006
Computational Experience with Rigorous Error Bounds for the Netlib Linear Programming Library
C. Keil and C. Jansson, Reliable Computing - 2006 - Vol.12, No.4.
The Netlib library of linear programming problems is a well known suite containing many real world applications. Recently it was shown by Ordóñez and Freund that 71% of these problems are ill-conditioned. Hence, numerical difficulties may occur. Here, we present rigorous results for this library that are computed by a verification method using interval arithmetic. In addition to the original input data of these problems we also consider interval input data. The computed rigorous bounds and the performance of the algorithms are related to the distance to the next ill-posed linear programming problem.
Preprint: PDF, zipped Postscript
2005
-
Lurupa – Rigorous Error Bounds in Linear Programming
Proceedings of the Dagstuhl seminar " Algebraic and Numerical Algorithms and Computer-assisted Proofs "
Linear Programming has numerous applications. Recently it has been shown that many real world problems exhibit numerical difficulties due to ill-conditioning.
Preprint: PDF, zipped Postscript
This paper describes Lurupa, a software package for computing rigorous bounds for the optimal value of a linear program. The package can handle point and interval problems. Numerical experience with the Netlib lp library is given.
Slides: PDF
-
2004
Lurupa – Rigorose Fehlerschranken für Lineare Programme
Diploma thesis (in german)
zipped Postscript
Conferences
-
NIMS & EASIAM 2008, Daejeon, South Korea, October 10th – October 12th, 2008
-
Tokyo Metropolitan University, Tokyo, Japan, March 8th – March 9th, 2008
Slides: Verified Computations in Optimization with Applications (PDF)
-
INVA 2008 (International Workshop on Numerical Verification and Applications), Okinawa City, Japan, March 1st – March 7th, 2008
Slides: A Comparison of Software Packages for Verified Linear Programming (PDF)
-
GICOLAG (Global Optimization - Integrating Convexity, Optimization, Logic Programming, and Computational Algebraic Geometry), Vienna, Austria, October 1st – December 31st, 2006
-
ICNAAM (International Conference of Numerical Analysis and Applied Mathematics), Hersonissos, Greece, September 15th – 19th, 2006
Extended Abstract: Verified Linear Programming – a Comparison (PDF), zipped Postscript
Slides: PDF -
Dagstuhl seminar " Algebraic and Numerical Algorithms and Computer-assisted Proofs ", Wadern, Germany, September 25th – 30th, 2005
Slides and Paper: see publication "Lurupa – Rigorous Error Bounds in Linear Programming"
Software
If you encounter any problems with the software packages feel free to contact me.
Lurupa
The software part of my dissertation, Lurupa is a tool to rigorously bound the optimal value of a linear program and compute verified enclosures of near optimal feasible points. It is written in pure ANSI C++ and uses the interval library PROFIL/BIAS. In addition a linear programming solver is needed to compute approximate solutions. Currently only lp_solve is supported but modules to link to other solvers are planned and can be easily implemented.
Download:
lurupa-1.0.tar.gz
Documentation
Profil/BIAS
Profil is a C++ class library based on the C library BIAS for developing and implementing interval algorithms in a comfortable but nevertheless efficient way.
More details here.
readMps
This piece of software resulted out of my need to read MPS coded linear programs into MATLAB. Meanwhile it consists mostly of two header files that do the parsing and can thus parse MPS files in C++ programs. The Matlab interface is provided as a mex function. If you have GMP installed the C++ part can give you the EXACT linear program coded in the MPS file. In this case the decimal fractions in the MPS file are converted exactly to rational numbers.
open issues:
- doesn't support free mps format
- doesn't support RANGES and integer sections
- as for most software the documentation could be a little more polished
Download:
readMps-509.tar.bz2
This release from 2007-05-24 added:
readmps.m and mps2mat.m now display a help message if the mex functions can not be found.
Added makereadmps to compile the mex functions from the MATLAB prompt.
