 # Packing problem

The set packing problem is the question, "Does a collection of sets contain at least $LaTeX: K$ mutually disjoint subsets?" ( $LaTeX: K$ is a positive integer not greater than the number of sets given.) This is solvable in polynomial time if no set has more than 2 members. Otherwise, it has the NP-hard equivalent integer program: $LaTeX: \textstyle \max \left \{ \sum_j x_j: Ax \le 1, x \in \left \{0, 1 \right \}^n\right\},$ where $LaTeX: x_j = 1$ if element $LaTeX: j$ is selected; else, $LaTeX: x_j = 0.$ The matrix $LaTeX: A$ has 0's and 1's, where the i-th row corresponds the i-th set to be packed: $LaTeX: A_{(i, j)}=1$ means element j is in set i; else, $LaTeX: A_{(i, j)}=0.$ The constraint $LaTeX: Ax \le 1$ means that at most one element of each set can be selected. If the IP maximum is less than $LaTeX: K-1,$ or if it equals $LaTeX: K-1 =$ number of elements, the answer to the set packing problem is "No". Otherwise, let $LaTeX: \textstyle x_1, \dots, x_{(K-1)}$ be among those elements selected (re-index, if necessary). Let $LaTeX: S_i$ be all sets containing $LaTeX: x_i.$ Due to the packing constraints, no selected element can be in two sets, so these are disjoint. The remaining set, $LaTeX: S_K,$ is composed of all other elements $LaTeX: \textstyle (x_K, \dots, x_n),$ and must be disjoint from the other sets, so the answer to the set packing question is "Yes" (and we can construct the disjoint subsets).
A special case is the node packing problem on a graph: find a set of nodes of maximum cardinality such that no node is incident with the same edge (or arc). In that case, every row of $LaTeX: A$ has exactly two 1's, and this is sometimes called egree-2 inequalities. Another special case is the bin packing problem.
The IP formulation has the natural extension: $LaTeX: \textstyle \max \left \{ cx: Ax \le b, x \in \left \{0,1 \right \}^n \right \},$ where $LaTeX: \textstyle c \ge 0$ and $LaTeX: \textstyle b \ge 1.$ This allows up to $LaTeX: b_i$ elements to be selected from the i-th set, and elements can be weighted by value $LaTeX: (c).$