The objective function value for the ILP problem can never
A) be as good as the optimal solution to its LP relaxation.
B) be as poor as the optimal solution to its LP relaxation.
C) be worse than the optimal solution to its LP relaxation.
D) be better than the optimal solution to its LP relaxation.

Question

Quizplus · Accepted Answer

The optimal solution to the LP relaxation serves as a lower bound for the objective function value of the ILP problem. Since the ILP problem adds integer constraints, the optimal solution to the ILP problem cannot be worse than the optimal LP relaxation. Therefore, the ILP problem can be equal to or better than the LP relaxation, making choice D the correct answer.

The Objective Function Value for the ILP Problem Can Never