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