找到线性规划的精确解

Question

我需要找到线性程序的精确实数解（其中所有输入都是整数）。重要的是，求解器还将解输出为有理数，理想情况下无需使用浮点数执行任何中间步骤。

GLPK 可以进行精确算术，但无法将解显示为有理数（即 1/3 得到 0.3333）。我可能可以尝试猜测这意味着哪个数字，但这似乎非常脆弱。

我无法找到可以做这种事情的 LP 求解器。有吗？性能并不是一个大问题；我的问题很小。（我确实考虑过使用像 Z3 这样的 SMT 求解器；它们可以解决此类问题并提供精确的有理解，但它们采用量词消除，而不是使用更适合线性规划（如 Simplex）的算法）

Answer 1

SoPlex可以使用有理算术来精确求解 LP。像这样使用它：

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

选项X和Y将以有理数形式打印原始解和对偶解，同时o0将f0最优性和可行性容差设置为 0，从而精确求解线性规划。

您需要安装 GMP（或 Windows 上的 MPIR）才能使用合理的功能。相对于 QSopt_exact 的一个优点是 SoPlex 使用一种混合技术，将双精度计算的速度与有理算术的精确精度（迭代细化）相结合。