20
$\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?

Improve this question
$\endgroup$

7 Answers 7

Reset to default
17
$\begingroup$

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

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

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

Improve this answer
$\endgroup$
7
$\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.

Improve this answer
$\endgroup$
6
$\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.

Improve this answer
$\endgroup$
4
$\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).

Improve this answer
$\endgroup$
3
$\begingroup$
  1. You can try to use solver implementing Simplex-method on the base of GMP, https://gmplib.org/, (GNU Multiple Precision Arithmetic Library). E.g. it might be SoPLex, https://soplex.zib.de, see additional info on GMP in SoPlex here https://soplex.zib.de/doc/html/INSTALL.php.
  2. For a rather "small" LP problem I can you recommend "simplex package" in Maxima (Computer Algebra System based on Lisp). An exact, rational arithmetic is a native for Maxima. See examples and some instructions here https://maxima.sourceforge.io/docs/manual/maxima_311.html, https://maxima.sourceforge.io/docs/manual/maxima_312.html.
Improve this answer
$\endgroup$

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