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

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

编辑：我正在寻找的是/否回答任何的算法得到的溶液的最优（单纯形法，分支定界和切割面）的ILP。

2013-03-08 Shan

具体。如果你问一个模糊的问题，你会得到一个模糊的答案。但是，如果您给我们详细信息和背景，我们可以提供一个有用的答案。 – 2013-03-08 20:39:22

如果您的ILP是您的问题的正确表述，您将得到一个对应于您的优化约束的解决方案。假如你有足够的耐心等待它，这可能需要很长时间。对于一个图形布局的np-hard问题，去年我使用了基于一般约束的编程;一天以上的图表不超过50个顶点和250个边缘。 – 2013-03-08 21:33:30

@罗伯特哈维全力以赴，问题不是模糊的。哈罗德有正确的答案。这个问题可能对于SO来说有点高级，与数学算法有关，而不是编程;但不需要上下文来理解所要求的内容。 – 2013-03-08 22:15:45

-2

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

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

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

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

2013-03-08 21:39:15

感谢您的回答！ – Shan 2013-03-09 00:03:05

因为这个答案是错误的而被Downvoted。在线性程序中，您正在寻找既满足约束又优化（最小化或最大化）给定目标函数的解决方案。它也不回答什么算法可以解决整数程序的问题。 – raoulcousins 2013-03-10 00:54:28

@raoulcousins为什么这个答案错了？ – Shan 2013-03-11 10:00:20

单纯形法不处理你想要的整数约束。简单地舍入结果并不能保证提供最佳解决方案。

单纯形法来解决的ILP问题，如果约束矩阵是totally dual integral确实工作。

解决ILP（不限于完全对偶积分约束矩阵）的一些算法是Branch and Bound，它易于实现，并且如果成本合理均匀一般效果良好（非常不均匀的成本使其尝试多次尝试一开始很有希望，但事实并非如此），并且Cutting Plane，我真的不太了解，但可能是很好的，因为人们正在使用它。

2013-03-08 22:11:12 harold

回答