c - 单纯形算法的数值稳定性

Question

编辑：单纯形数学优化算法，不要与单纯形噪声或三角测量相混淆。

我正在实现自己的线性规划求解器，我想使用 32 位浮点数来实现。我知道 Simplex 对数字的精度非常敏感，因为它执行大量计算，如果使用的精度太低，可能会出现舍入误差。但是，我仍然想使用 32 位浮点数来实现它，这样我就可以将指令设为 4 宽，也就是说，我可以使用 SIMD 一次执行 4 次计算。我知道我可以使用双打并制作 2 宽的指令，但 4 大于 2 :)

我的浮点实现遇到了问题，其中解决方案不是最理想的，或者问题被认为是不可行的。这尤其发生在混合整数线性程序中，我用分支定界法解决了这个问题。

所以我的问题是：如何尽可能防止舍入错误导致不可行、无界或次优的解决方案？

我知道我可以做的一件事是缩放输入值，使它们接近一（http://lpsolve.sourceforge.net/5.5/scaling.htm）。还有什么我可以做的吗？

Answer 1

是的，我尝试使用分支定界方法和贪婪算法作为启发式算法来实现扩展背包问题的算法，它与使用选择最大目标增量的旋转策略运行的单纯形完全类似。

我也遇到了算法的数值稳定性问题。

就个人而言，如果我们继续使用浮点，我认为没有一种简单的方法可以消除这些问题，但是有一种方法可以检测分支过程中的不稳定性。

我认为，通过实验而不是严格的稳定性分析数学，大多数错误通过一个非常接近系统约束的整数解传播。

给定任何整数解，我们计算出该解的松弛度，如果向量的元素非常小，或者在 1e-14 到 1e-15 的量级上，则停止分支并报告不稳定性。