我正在寻找一个 LP（线性程序）求解器，它使用 Simplex 算法或它喜欢的任何东西。我还有一个额外的要求，即求解器将在不损失任何精度的情况下进行所有计算！
因此，如果我能找到一个基于模板的 C++ 库，让我定义它使用的数值变量的下划线类型，我将让它使用 boost 的类型 cpp_ratinal，因此所有计算都不会因为四舍五入而损失任何精度浮点数。
这样的 C++ 库是否存在？
问问题
871 次
2 回答
0
SoPlex 和 QSOpt 都有精确的单纯形求解器。他们的表现会比你建议的要好。但是，我应该警告您，SoPlex 的精确单纯形求解器实际上不起作用。使用 SoPlex 报告不可行的合理数据构造一个可行的线性程序是相当简单的。
在整个求解过程中使用精确算术并不是一个好主意。您最终不得不在精确算术中对大矩阵进行行归约，并且所涉及的精确数字变得巨大。我相信 GLPK 的精确求解器在有理算术中运行单纯形；你可能会玩它，看看你有多喜欢它的性能。
在内点求解器中，SDPA-GMP 是一种内点方法，用于泛化使用任意精度算术的线性规划。您必须决定要使用的精度，但您可以使用 SDPA-GMP 获得非常高精度的解决方案，然后进行某种高精度交叉以获得精确的最佳解决方案。（我从来没有尝试过这个，因为我从来不想精确地求解 LP。）我怀疑在这种情况下，基于单纯形的求解器也会比 IPM 运行得更快。
于 2014-08-30T09:34:35.423 回答
-1
看看 SoPlex：
SoPlex 使用一种称为“迭代细化”的技术将解决方案质量提高到任意精度。所有单纯形运算都以双精度算术执行，以在短时间内获得接近最优的解决方案。之后，在稍微修改（减少错误）的 LP 上执行很少的枢轴来确定确切的解决方案。它以模板方式使用 GMP，即 Gnu 多精度库 - 如果您不喜欢 GMP，您也可以使用 cpp_rational。在当前版本中，LU 因式分解还不能用于精确算术，因此您无法获得最优性的精确证明。不过，这已经在我们的开发者版本中实现，并将在今年年底发布。
于 2014-08-30T09:25:50.543 回答