整数线性规划和线性规划的绑定原理

Question

目前，我正在学习近似算法。当我通过LP学习顶点覆盖时，我遇到了一个叫做边界原则的原则。它是这样的：

（1） ILP 问题的最大值始终小于或等于最大值LP 松弛的值：

用于 ILP 的 MAX ≤用于 LP 松弛的 MAX

（2） ILP 问题的最小值始终大于或等于LP 放松的最低要求：

ILP 的最小值

≥ LP 松弛的最小值

我不知道为什么"ILP 的 MAX ≤ LP 松弛的 MAX"和"ILP 的最小值≥ LP 松弛的最小值"。

谁能解释一下，谢谢！

Answer 1

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

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