# Is there a Linear Programming Library that natively supports fractions instead of floating point arithmetic?

If one recalls how the Simplex method is taught by hand in most LP classes it takes place entirely in $$\mathbb{Q}$$. All operations yield exact fractions.

For this reason I'm looking for linear programming library that doesn't use floats/doubles and other imprecise arithmetic but exclusively uses exact fractions; as I had done some work assuming exact fraction representation of my vertices.

While anyone could build such a simplex solver by hand, I still want to avail the benefits of a commercial solver/well maintained open source tool in terms of speed (although I expect to lose some performance if not using state of the art algorithms/floating point arithmetic). What options are out there?

## 6 Answers

QSopt-Exact by Applegate, Cook, Dash, and Espinoza

Parma Polyhedra Library supports MIP on fractions. It's based on gmp and is used by gcc and Julia among other projects.

I suggest GLPK, which has the advantage of being fully open source and easily available everywhere (as a package on most Linux distribution).

Run it from the command line with the --exact option. It is limited to LPs though (no MIPs), and not so easy to use directly from a programming language. From the release notes:

### GLPK 4.13 (release date: Nov 13, 2006)

    A tentative implementation of the "exact" simplex method based
on bignum (rational) arithmetic was included in the package.

On API level this new feature is available through the routine
lpx_exact, which is similar to the routine lpx_simplex.

In the solver glpsol this feature is available through two new
command-line options: --exact and --xcheck. If the '--exact'
option is specified, glpsol solves LP instance using the exact
simplex method; in case of MIP it is used to obtain optimal
solution of LP relaxation. If the --xcheck option is specified,
LP instance (or LP relaxation) is solved using the standard
(floating-point) simplex method, however, then glpsol calls the
exact simplex routine to make sure that the final LP basis is
exactly optimal, and if it is not, to perform some additional
simplex iterations in exact arithmetic.

• To my knowledge, GLPK supports only integer and floating point arithmetic, not *fractions*/rational numbers as requested. – ojdo Dec 9 '20 at 13:25
• That is right there in the documentation I linked to. glpsol --exact – Gabriel Gouvine Dec 10 '20 at 17:17
• Good to know! I managed to miss that option for years. – ojdo Dec 11 '20 at 12:32
• Thanks for the edit :) – Gabriel Gouvine Dec 11 '20 at 14:24

You could also use polymake which includes a few exact linear programming libraries (including my own one). It should also be possible to compile SoPlex with GMP support, but I actually never tried it.

I agree with Rob Pratt about QSopt-Exact. That's probably the right thing to do if you're doing larger scale solves.

I think that you can also do exact LP in Sage (using fractions). Sage is based on Python, so this would be easy to code in, but you do have to download the whole Sage installation at this point. But I don't think this would be quite as robust as QSopt-Exact.

While working with polyhedra representations myself, I've come across the package lrslib by David Avis from McGill University.

The key functionality of the package is the conversion between V- and H-representations for polytopes, but it has an efficient built-in LP solver.

All computations are done exactly in either multiple precision or fixed integer arithmetic (under your control).