16
$\begingroup$

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?

$\endgroup$
16
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.