Consider the problem of 4.1, and let I = {1, 2, 3, 4} index the four constraints. Define a parameterized relaxation (4.4) by letting f(x, u) = 2x1 + x2 and letting C(x, u) be the set of constraints...

Consider the problem of 4.1, and let I = {1, 2, 3, 4} index the

four constraints. Define a parameterized relaxation (4.4) by letting f(x, u) =

2x1 + x2 and letting C(x, u) be the set of constraints indexed by u ⊂ I,

where |u| ≤ 2. What is θ(u) for each u? What is an optimal solution of the

relaxation dual? What is the duality gap?