For minimization problems, the optimal objective function value to the LP relaxation provides what for the optimal objective function value of the ILP problem?
A) An upper bound.
B) A lower bound.
C) An alternative optimal solution.
D) An additional constraint for the ILP problem.

Question

Quizplus · Accepted Answer

For minimization problems, solving the LP relaxation (where the integer constraints are relaxed to allow for continuous variables) provides a lower bound for the objective function value of the Integer Linear Programming (ILP) problem. This is because the relaxation allows for more possible solutions (including non-integer ones), making the minimum possible value of the objective function in the LP relaxation potentially lower than the minimum value in the ILP, where solutions are restricted to integers.

For Minimization Problems, the Optimal Objective Function Value to the LP