想改进这篇文章吗？提供这个问题的详细答案，包括引文和解释为什么你的答案是正确的。没有足够详细信息的答案可能会被编辑或删除。
我试图用整数线性规划（ILP）来实现一个问题的解决方案。由于这个问题是np难问题，我想知道单纯形法的解是否是最优的？有没有人能用单纯形法来评价ilp的最优性，或者指出一些来源。有没有其他算法可以提供ilp问题的最优解？
编辑：我正在寻找是/否的答案，以解决最优性的任何算法（单纯形法，分支和界限和切割平面）为ILP。
最佳答案
单纯形方法不能处理需要整数的约束简单地将结果四舍五入并不能保证给出最优解。
如果约束矩阵totally dual integral，使用单纯形法求解ilp问题确实有效。
一些求解ILP（不受完全对偶积分约束矩阵的约束）的算法是Branch and Bound，这是一个简单的实现方法，如果成本是合理的一致的（非常不一致的成本使得它尝试了许多看起来有希望但结果却不是这样的尝试），通常可以很好地工作，并且Cutting Plane我真的不太了解，但它可能是好的，因为人们正在使用它。