Consider the binary integer program min 5x1 - 2x2 s .t. 7x1 - x2 5 x1, x2 binary (a) Formulate and justify a Lagrangian

Consider the binary integer program min 5x1 - 2x2 s .t. 7x1 - x2 Ú 5 x1, x2 binary

(a) Formulate and justify a Lagrangian relaxation dualizing the only main constraint with multiplier v.

(b) Briefly explain why your relaxation of (a)
is indeed a relaxation of the full ILP model.

(c) Comment on whether this relaxation can always be solved by LP ( 13.11 ).

(d) There are four possible integer solutions to the relaxation. Develop four (linear)
expressions for the relaxation objective function in terms of multiplier v, assuming in turn that each of the four is optimal.

(e) Use results of

(d) to develop a plot for the Lagrangian relaxation dual solution value as a function of multipler v.

(f) Identify an optimal choice of v on your plot of (e), and explain your choice.