Suppose that $we$ have the following integer program:

max,$3x_1,+,2x_2,+,5x_3,+,4x_4,$

$s.t.5x_1,+,x_2,+,8x_3,+,x_4,=,14$

$,-x_1,+,2x_2,+,3x_3,+,6x_4,=,10$

$,x_1,x_2,x_3,x_4,,0$

$,x_1,x_2,x_3,x_4$ Integers

The integer program $is$ feasible and has $an$ optimal solution. Which $of$ the following

statements $is$ true about its linear programming relaxation?

The linear programming relaxation could have larger $or$ smaller optimal value, but $it$ cannot $be$

infeasible.

The linear programming relaxation would $be$ infeasible.

Since $we$ have a maximization problem, the linear programming relaxation would have a smaller

$(or$ equal$)$ optimal value.

Since $we$ have a maximization problem, the linear programming relaxation would have a larger $(or$

equal$)$ optimal value.