The second constrain should be ? from j=1 to n {a_ij}{x_ij}?{b_i}

1. (20 points) The generalized assignment problem is stated as the following integer program: m y 1, j-1,..,n =1, 1772 Tij E 10, 13, Vi,j where ay 20,,20,ij where aij 2 0,bi2 0, V2,) Consider the following two ways of obtaining a lower bound for this problem using Lagrangian relaxation: Dualize constraints (1) Dualize constraints (2 Now answer the following (a) In each of the above cases, explain how the relaxed integer program can be easily solved to obtain a (b) In each of the above cases, formulate the (nonlinear) optimization problem of selecting the Lagrangian lower bound. variable (u) that gives tightest (i.e., highest) lower bound. Is this a convex program? Why? 1. (20 points) The generalized assignment problem is stated as the following integer program: m y 1, j-1,..,n =1, 1772 Tij E 10, 13, Vi,j where ay 20,,20,ij where aij 2 0,bi2 0, V2,) Consider the following two ways of obtaining a lower bound for this problem using Lagrangian relaxation: Dualize constraints (1) Dualize constraints (2 Now answer the following (a) In each of the above cases, explain how the relaxed integer program can be easily solved to obtain a (b) In each of the above cases, formulate the (nonlinear) optimization problem of selecting the Lagrangian lower bound. variable (u) that gives tightest (i.e., highest) lower bound. Is this a convex program? Why