查找线性程序的确切解决方案 [英] 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可以执行精确的算术运算，但不能将解显示为有理数(即1/3时我得到0.3333).我可能会尝试猜测这个数字是什么意思，但这似乎很脆弱.

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.

我无法找到可以执行此类操作的LP解算器.有一个吗?性能不是一个大问题.我的问题很小. (我确实研究过使用像Z3这样的SMT求解器；它们可以解决这类问题并提供确切的合理解决方案，但它们诉诸于量词消除，而不是对像Simplex这样的线性程序使用更合适的算法)

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)

推荐答案

SoPlex 可以使用有理算法来求解LP.确切地.像这样使用它:

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

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

选项X和Y将以有理数打印原始解和对偶解，而o0和f0将最优性和可行性公差设置为0，从而精确地求解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.

您需要安装GMP(或Windows上的MPIR)才能使用合理的功能.与QSopt_exact相比，一个优点是SoPlex使用了一种混合技术，将双精度计算的速度与有理算术的精确精度结合在一起(

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

这篇关于查找线性程序的确切解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！