目前，我正在学习近似算法。当我通过lp学习顶点覆盖时，遇到了一个叫做边界原理的原理。
就像这样：
（1）ILP问题的最大值总是小于或等于最大值。
LP松弛值：
ilp的max≤lp松弛的max
（2）ILP问题的最小值总是大于或等于
LP松弛的最小值：
ILP的MIN≥LP松弛的MIN
我不明白为什么“I LP的MAX≤LP松弛的MAX”和“ILP的MIN≥LP松弛的MIN”。
有人能解释一下吗，thx！
最佳答案
ilp问题比lp问题有额外的约束。约束条件是所有变量都应该是整数。
因此，ilp的最优解充其量应该和lp问题的最优解一样好，它永远不会更好。