Связанный принцип для целочисленного линейного программирования и линейного программирования

Question

В настоящее время я изучаю алгоритмы аппроксимации. Когда я узнал Vertex Cover через LP, я столкнулся с принципом, который называется Bounding Principles. это следующий образом:

(1) Максимальное значение для задачи ILP всегда меньше или равно максимальных значения для LP релаксации:

MAX для ILP ≤ MAX для LP релаксации

(2) минимальное значение для задачи ILP всегда больше или равна минимума для LP релаксации:

мин для ILP ≥ MIN для LP релаксации

Я не могу понять, почему «MAX для ILP ≤ MAX для релаксации LP» и «MIN для ILP ≥ MIN для релаксации LP».

Может кто-нибудь объяснить, thx!

Answer 1

У ILP есть дополнительное ограничение, чем проблема с LP. Ограничение состоит в том, что все переменные должны быть целыми числами.

Следовательно, оптимальное решение для ILP должно быть в лучшем случае оптимальным решением для проблемы с LP, оно никогда не может быть лучше.