algorithm - 整数线性规划是否提供最佳解决方案？

Question

我正在尝试使用整数线性规划 (ILP) 来解决问题。由于问题是 NP-hard ，我想知道 Simplex Method 提供的解决方案是否是最优的？任何人都可以评论使用单纯形法的 ILP 的最优性或指向某些来源。是否有任何其他算法可以为 ILP 问题提供最佳解决方案？

编辑：我正在寻找通过 ILP 的任何算法（单纯形法、分支定界和切割平面）获得的解决方案的最优性的是/否答案。

score 5 · Accepted Answer

单纯形法不处理您想要整数的约束。简单地对结果进行四舍五入并不能保证给出最佳解决方案。

如果约束矩阵是完全对偶积分，则使用单纯形法解决 ILP 问题确实有效。

一些解决 ILP（不限于完全对偶积分约束矩阵）的算法是Branch and Bound，它易于实现，并且如果成本合理均匀（非常不均匀的成本使其尝试许多看起来很有希望的尝试），通常效果很好首先，但事实并非如此）和切割平面，老实说我不太了解，但它可能很好，因为人们正在使用它。

score -2 · Accepted Answer

根据定义，线性规划问题的解集是最优的。

线性规划是一类称为“约束满足”的算法。一旦你满足了约束，你就解决了问题并且没有“更好”的解决方案，因为根据定义，最好的结果是满足约束。

但是，如果您还没有完全模拟问题，那么显然其他类型的解决方案可能会更好。

澄清：当我在上面写“满足约束”时，我包括目标函数的最大化。切割平面算法本质上是单纯形算法的扩展。

2 回答 2