Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

abstract We describe a new exact-arithmetic approach to linear programming when the number of variables $n$ is much larger than the number of constraints $m$ (or vice versa). The algorithm is an implementation of the simplex method which combines exact (multiple precision) arithmetic with inexact (floating point) arithmetic, where the number of exact arithmetic operations is small and usually bounded by a function of $\min(n,m)$. Combining this with a ``partial pricing'' scheme (based on a result by Clarkson \cite{Cla}) which is particularly tuned for the problems under consideration, we obtain a correct and practically efficient algorithm that even competes with the inexact state-of-the-art solver CPLEX (trademark of CPLEX Optimization Inc.) for small values of $\min(n,m)$ and and is far superior to methods that use exact arithmetic in any operation.

Back to the publications page