Consider the Lagrangian relaxation:

a) If x is a feasible solution for a MIP problem, show that x also must be a feasible solution for the corresponding Lagrangian relaxation.

(b) If x* is an optimal solution for a MIP problem, with an objective function value of Z, show that where is the optimal objective function value for the corresponding Lagrangian relaxation.