5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.