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

Question

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

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

我的浮点实现有问题，解决方案不是最优的，或者据说问题不可行。这种情况尤其适用于我使用分支定界法求解的混合整数线性规划。

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

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

Answer 1

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

我对算法的数值稳定性也有疑问。

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

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

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