整数线性规划是否能给出最优解？

Question

我正在尝试使用整数线性规划（ILP）来解决问题。由于该问题是NP难的，我想知道Simplex方法提供的解是否是最优的？有人能否评论ILP使用Simplex方法的最优性或指向一些资源？还有其他算法可以提供ILP问题的最优解吗？

编辑：我正在寻找对于任何算法（Simplex方法、分支定界和割平面）得到的解的最优性的是/否答案。

- Shan

---

具体一点。如果你问的问题含糊不清，你就会得到一个模糊的答案。但如果你提供细节和背景信息，我们就能给出有用的答案。 - Robert Harvey

如果您的整数线性规划（ILP）正确地表达了您的问题，那么您将得到与您的优化约束相对应的解决方案。前提是您有足够的耐心等待它，这可能需要很长时间。去年我在处理与图形布局有关的NP难题时使用了通用约束编程；对于一些顶点不超过50个、边不超过250条的图形，需要超过一天的时间。 - G. Bach

@RobertHarvey，恕我直言，这个问题并不含糊。Harold 给出了正确的答案。这个问题可能对于 SO 来说有点高级，更多地涉及数学算法而非编程；但是理解所问之意并不需要上下文。 - Heath Hunnicutt

Harold的回答既精确又正确——尽管它只回答了“Simplex是否解决ILP问题？”这个问题，而没有回答“哪些算法可以解决ILP问题？”这个附加问题。 - comingstorm

@StackUnderflow 对于一般的整数线性规划问题：单纯形法：不行。分支定界法：可以，在有限时间和有限内存下，但很容易超出典型计算机的处理速度或内存限制。割平面法：经典的Gomory割平面最终会得到最优解。由于数值不稳定性，它们的实际实现极其复杂（从它们的开发到实际实现之间有30多年的时间）。 - user327301

Answer 1

简单型法不能处理您希望获得整数的约束条件。简单地四舍五入结果并不能保证给出最优解。

如果约束矩阵是完全对偶整数，则使用简单型法来解决ILP问题是有效的。

一些解决ILP问题的算法（不受完全对偶整数约束矩阵的限制）包括分支定界法，如果成本相对均匀，则其实现较为简单且通常效果良好（非常不均匀的成本会使其尝试许多看起来很有前途但最终失败的尝试），以及割平面法，我对此了解不多，但人们可能会使用它，因为它很好。

- harold

Answer 2

线性规划问题的解集在定义上是最优的。

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

然而，如果您没有完全对问题进行建模，那么显然可能会有其他类型的解决方案更好。

---

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

- Tyler Durden

---

因为这个答案是错误的，所以被踩了。在线性规划中，你正在寻找一个既满足约束条件又优化（最小化或最大化）给定目标函数的解决方案。它也没有回答什么算法可以解决整数规划问题。 - user327301

答案说：“一旦您满足了约束条件，您就已经解决了问题，并且没有“更好”的解决方案，因为按定义，最佳结果是满足约束条件。”这在一般情况下并不正确。您不仅要满足约束条件，还要最小化（或最大化）目标函数。 - user327301

OP询问了关于整数线性规划方法的问题，经验表明这些方法可能会产生比去除仅限于整数要求所得到的解决方案更不理想的结果。您的回答似乎忽略了这一点。此外，@raoulcousins提出的最大化或最小化目标函数受约束条件的观点也是正确的。 - Bob Jarvis - Слава Україні

如果您使用单纯形法解决整数线性规划问题，那么（1）约束条件将被满足，（2）目标函数将被最大化。因此，答案将是最优的。案子结了。可能OP真正想问的是，是否有比单纯形法更好的已知技术来解决整数线性规划问题？对此的答案并不是很确定（如果我们认为切割平面方法是单纯形法的变体）。 - Tyler Durden