linear-programming - 找到线性规划的精确解

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，从而精确求解 LP。

您需要安装 GMP(或 Windows 上的 MPIR)才能使用合理的功能。与 QSopt_exact 相比的一个优势是 SoPlex 使用一种混合技术，将 double 计算的速度与有理算术的精确精度 ( iterative refinement) 相结合。