Consider the following binary ILP:

max 13x1 + 22x2 + 18x3 + 17x4 + 11x5 + 19x6 + 25x7 s.t. a 7

j = 1xj … 3 3x1 + 7x2 + 5x3 … 15 12x4 + 9x5 + 8x6 + 6x7 … 11 xj binary, j = 1,c, 7

(a) State the corresponding Lagrangian relaxation dualizing only the first main constraint, and initializing its dual multiplier at v = 20 or v = -20, whichever is appropriate.

(b) Briefly justify why your Lagrangian of (a)

is indeed a relaxation of the original model.

(c) Solve the relaxation of

(a) by inspection, using multiplier v = 10 and identify an optimal solution and solution value for it.

Justify your computations.

(d) Beginning from your results of part

(c), compute the subgradient direction Algorithm 13C would follow.