A Comparison of Software Packages for Verified Linear Programming

Christian Keil(c.keiltu-harburg.de)

Abstract: 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.

Keywords: linear programming, interval arithmetic, rigorous error bounds, comparison, software packages

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Optimization Software and Modeling Systems

Citation: Submitted to SIOPT.

Download: [PDF]

Entry Submitted: 06/11/2008
Entry Accepted: 06/11/2008
Entry Last Modified: 06/11/2008

Modify/Update this entry