linear-programming - 有界变量工具的单纯形法

Question

是否有任何可靠的工具或源代码（最好是 C++）通过单纯形法求解有界变量的 LP？在我的问题中，所有变量都限制为 1。

我实际上在 StackOverflow 帖子中找到了一些工具：SoPlex、CLP 和 lpsolve。

其中，我想 SoPlex 更广泛。在文档中，据说 SoPlex 考虑变量边界。然后它说：

“如果所有原始变量都在其范围内，则称单纯形基是原始可行的。类似地，如果所有对偶变量都在其范围内，则称为对偶可行。如果一个基础既原始可行又对偶可行，则最优已经找到解决方案。”

我的印象是它不会强制基础在变量范围内，而是检查解决方案的变量是否在范围内。如果是这样，它认为解决方案是最优的。

是否有任何工具可以找到考虑变量界限的可行解决方案？

Answer 1

具有有界或盒装变量的 LP 是完全正常且非常常见的。就像范围约束的问题一样，即左侧和右侧的约束。

SoPlex能够同时运行原始单纯形法和对偶单纯形法。它从一个松弛的基础开始——所有变量都在一个界限上——并相应地移动界限以使这个基础对各自的单纯形类型来说是原始的或对偶的。

获得可行基础的另一种可能性是使用所谓的阶段 1。这解决了修改后的 LP，然后切换回原始 LP。