Maximum set packing and minimum set cover duality

Question

I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the primal and dual LP problems should have the same value.

However, consider a universe $U = \{1, 2, 3, 4, 5\}$ and a collection of sets: $S = \{ \{1, 2, 3\}, \{3, 4, 5\}, \{1\}, \{2\}, \{3\}\}$. From what I understand, a minimum set cover would consist of the first 2 sets in set $S$, while the maximum set packing consists of the last 3 sets. These solutions aren't in accordance with the statement of the strong duality theorem.

Given that, I don't understand how the 2 problems can be dual of each other. What am I missing?

Thank you very much.

Answer 1

There is no contradiction. The strong duality theorem applies to the fractional linear programming formulations of the problems, where one is allowed to set fractional values for the variables, but these formulations are only relaxations of the two original problems. Strong duality does not apply to the integer linear programming formulations (as your example indeed shows).

Answer 2

Let $P$ be the LP relaxation for minimum set cover: $$\begin{align} \min \sum_{S \in \mathcal{S}} x_Sc(S) & \\ \sum_{S: \;e \in S} x_S \geq 1 &\quad\quad \forall e\in U \\ x_S \geq 0 &\quad\quad S \in \mathcal{S}\\ \end{align}$$ and $D$ be the dual LP which corresponds to the linear relaxation for maximum set packing: $$\begin{align} \max \sum_{e \in \mathcal{U}} y_e & \\ \sum_{e: \;e \in S} y_e \leq c(S) &\quad\quad \forall S\in \mathcal{S} \\ y_e \geq 0 &\quad\quad e \in \mathcal{U}\\ \end{align}$$ The strong duality theorem states that the optimal value of $P$ is the same as the optimum value of $D$. However, the solutions for the LPs aren't necessarily integral as in the case that you showed. Let $z^*$ be the value of the optimal solution to $P$, it can be shown that $OPT_I\leq H_nz^*$ where $OPT_I$ is the value for the optimal integral solution of $P$.

The worst case bound of the ratio $\frac{OPT_I}{z^*}$ is known as the integrality gap of an LP (note that the ratio is flipped for a maximization problem).

See here for a discussion on integrality gaps and here for an analysis of the set cover primal/dual.

Answer 3

The dual of Set Cover is not Set Packing (as defined in Wikipedia). In Set Cover you choose sets, e.g. you have a binary variable for each set. Thus, the dual problem can't have a variable for each set as well. Instead, you have a dual variable for each element that represents how much of that element you want to pack without overpacking the sets that contain this element (see the dual LP formulation below).

$$\min \sum_{e \in U} y_e$$ $$ s.t. \sum_{e: e \in s} y_e \le \text{cost}(s) \quad\quad (s \in S)$$ $$ y_e \ge 0 \quad\quad (e \in U)$$

Answer 4

The actual formulation of the dual of the set-packing problem is:

$$\min \sum_{e \in U} y_e$$ $$ s.t. $$ $$ \sum_{e: e \in s} y_e \ge w_s \quad\quad (s \in S)$$ $$ y_e \ge 0 \quad\quad (e \in U)$$

(Zideon's formulation is wrong, not enough reputation to reply him...)

I got the same confusion with that wiki statement some weeks ago. I will correct that article once I get the time to do it.