In an integer programming problem minx≥0{cx | Ax ≥ b, x integral}, the Lagrangean relaxation is θ(u) = min x≥0 {(c − uA)x + ub | x integral} Show that when the Lagrangean relaxation can be solved as a...

In an integer programming problem minx≥0{cx | Ax ≥ b, x integral},

the Lagrangean relaxation is

θ(u) = min x≥0

{(c − uA)x + ub | x integral}

Show that when the Lagrangean relaxation can be solved as a linear programming problem, the Lagrangean dual gives the same bound as the linear

programming relaxation. That is, if

θ(u) = min x≥0

{(c − uA)x + ub}

then maxu≥0{θ(u)} = minx≥0{cx | Ax ≥ b}.