5

I need to find an exact real solution to a linear program (where all inputs are integers). It is important that the solver also outputs the solutions as rational numbers, ideally without doing any intermediate steps with floating point numbers.

GLPK can do exact arithmetic, but cannot display the solutions as rational numbers (i.e. I get 0.3333 for 1/3). I could probably attempt to guess which number is meant by that, but that seems very fragile.

I was unable to find an LP solver that can do this kind of thing. Is there one? Performance is not a huge issue; my problems are very small. (I did look into using an SMT solver like Z3; they can solve these kinds of problems and provide exact rational solutions, but they resort to quantifier elimination instead of using a more apt algorithm for Linear Programs like Simplex)

Manuel Eberl
  • 7,858
  • 15
  • 24
  • 3
    QSopt_ex Rational LP Solver [(link)](http://www.math.uwaterloo.ca/~bico/qsopt/ex/) has source code available – Erwin Kalvelagen Mar 27 '16 at 17:47
  • This looks good, and it gets bonus points for being free software. Thanks! If you turn this into an answer, I'll accept it. – Manuel Eberl Mar 29 '16 at 15:13
  • 2
    For the benefit of future readers: I was unable to get the above QSopt_ex to build on my system, but this QSopt_ex fork on Github worked perfectly: https://github.com/jonls/qsopt-ex – Manuel Eberl Apr 21 '16 at 11:06

1 Answers1

3

SoPlex can use rational arithmetic to solve LPs exactly. Use it like this:

soplex -X -Y -o0 -f0 problem.lp

Options X and Y will print the primal and dual solution in rational numbers, while o0 and f0 set the optimality and feasibility tolerance to 0, hence solving the LP exactly.

You need GMP installed (or MPIR on Windows) to use the rational functionalities. One advantage over QSopt_exact is that SoPlex uses a hybrid technique combining the speed of double precision computation with the exact precision of rational arithmetic (iterative refinement).

mattmilten
  • 6,242
  • 3
  • 35
  • 65
  • That looks good. I would prefer if it were free software, and my problems are in Cplex format, but it might be worth it nevertheless. Thanks! – Manuel Eberl Mar 29 '16 at 15:11