algorithm - 整数线性规划和线性规划的有界原理

Question

目前，我正在学习近似算法。在通过 LP 学习 Vertex Cover 的时候，我遇到了一个叫做 Bounding Principles 的原理。它像这样：

(1) ILP 问题的最大值总是小于或等于 LP 松弛的最大值：

ILP 的 MAX ≤ LP 松弛的 MAX

(2) ILP 问题的最小值总是大于或等于 LP 松弛的最小值：

ILP 的 MIN ≥ LP 松弛的 MIN

我无法弄清楚为什么“ILP 的 MAX ≤ LP 松弛的 MAX”和“ILP 的 MIN ≥ LP 松弛的 MIN”。

谁能解释一下，谢谢！

Answer 1

ILP 比 LP 问题具有额外的约束。约束是所有变量都应该是整数。

因此，ILP 的最优解充其量应该与 LP 问题的最优解一样好，永远不会更好。