Find exact solutions to Linear Program

问题:

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)

回答1:

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