(Constraint Relaxation and Lagrangian Relaxation) The purpose of this exercise is to compare the lower bounds obtained by relaxing integer constraints and by dualizing the side constraints. Consider the nonlinear network optimization problem with a cost function f(x), the conservation of flow constraints, and the additional constraint
where Xij are given subsets of the real line and the functions gt are linear. We assume that f is convex over the entire space of flow vectors x. We introduce a Lagrange multiplier µt for each of the side constraints gt(x) ≤ 0, and we form the corresponding Lagrangian function
\