<分区>
我正在尝试使用整数线性规划 (ILP) 实现问题的解决方案。由于问题是 NP-hard 问题，我想知道 Simplex Method 提供的解决方案是否是最优的？任何人都可以评论使用单纯形法的 ILP 的最优性或指向某些来源。有没有其他算法可以为ILP问题提供最优解？
编辑:我正在寻找通过 ILP 的任何算法(单纯形法、分支定界和切割平面)获得的解决方案的最优性的是/否答案。
<分区>
我正在尝试使用整数线性规划 (ILP) 实现问题的解决方案。由于问题是 NP-hard 问题，我想知道 Simplex Method 提供的解决方案是否是最优的？任何人都可以评论使用单纯形法的 ILP 的最优性或指向某些来源。有没有其他算法可以为ILP问题提供最优解？
编辑:我正在寻找通过 ILP 的任何算法(单纯形法、分支定界和切割平面)获得的解决方案的最优性的是/否答案。
最佳答案
单纯形法不处理您需要整数的约束。简单地四舍五入结果并不能保证提供最佳解决方案。
如果约束矩阵为 totally dual integral，则使用单纯形法解决 ILP 问题确实有效.
一些解决 ILP(不限于完全对偶积分约束矩阵)的算法是 Branch and Bound ，这很容易实现，并且如果成本相当均匀(非常不均匀的成本使其尝试许多起初看起来很有希望但结果并非如此的尝试)通常效果很好，并且 Cutting Plane ，老实说我不太了解，但它可能很好，因为人们正在使用它。
关于algorithm - 整数线性规划是否给出最优解？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15302841/