The objective function for an optimization problem is: Min 3x

Question

The objective function for an optimization problem is: Min 3x - 2y, with constraints x ≥ 0, y ≥ 0. x and y must be integers. Suppose that the integer restriction on the variables is removed. If so, this would be a familiar two-variable linear program; however, it would also be an example of
A)the convex hull of the linear program.
B)a mixed-integer linear program.
C)an LP relaxation of the integer linear program.
D)a binary integer linear program.

Quizplus · Accepted Answer

Removing the integer restriction on the variables converts the problem from an integer linear program (ILP) to a linear program (LP). The LP relaxation of an ILP is a technique used to solve the ILP by first solving the LP without the integer restrictions and then rounding the fractional values of the LP solution to obtain a feasible solution for the original ILP. Therefore, C is the best choice because removing the integer restriction on the variables in this case would result in an LP relaxation of the original ILP.