Consider the facilities location ILP min 3x1,1 + 6x1,2 + 5x2,1 + 2x2,2

+250y1 + 300y2 s .t . 30x1,1 + 20x1,2 … 30y1 30x2,1 + 20x2,2 … 50y2 x1,1 + x2,1 = 1 x1,2 + x2,2 = 1 0 … x1,1, x1,2, x2,1, x2,2 … 1 y1 = 0 or 1

(a) Use total enumeration to compute all optimal solution.

(b) Form a Lagrangian relaxation dualizing the third and fourth constraints with Lagrange multipliers v1 and v2.

(c) Explain how the dualization in part (b)
leaves a relaxation that is easier to solve than the full ILP.

(d) Use total enumeration to solve the Lagrangian relaxation of part

(b) with v1 = v2 = 0, and verify that the relaxation optimal value provides a lower bound on the true optimal value computed in part (a).

(e) Repeat part

(d) with v1 = v2 = -100.

(f) Repeat part

(d) with v1 = 1000, v2 = 500.