4. Lagrangian Relaxation

4.1. Theory

• Slides

4.2. Exercises

4.2.1. Set Covering Problem

Given \(m\) sets of integers, such that \(\cup_{i=1}^m S_i = \{1,\ldots,n\}\), associated each with a cost \(c_i\). The goal of the set covering problem is to find the sets covering the universe \(U=\{1,\ldots,n\}\) at minimum cost.

\[\begin{split}\min \quad & \sum_{i=1}^m c_ix_i & \\ & \sum_{\substack{i=1\\j \in S_i}}^m x_i \ge 1 \quad& j=1,\ldots,n\\ & x_i \in \{0,1\} & i=1,\ldots,m\end{split}\]

1. Give the Lagrangian relaxation formula.

2. Given the sets \(S_1 = \{1,2\}, S_2 = \{3\}, S_3 = \{1,3\}, S_4 = \{2,3\}\) with \(c_1=2, c_2=3, c_3=4, c_4=5\). What is the lower-bound for \(\lambda_1 = 1.5, \lambda_2 = 1.6, \lambda_3 = 2.2\)?

3. Design a subgradient procedure to compute a lower-bound.