# Packing problem

### From Glossary

The *set packing problem* is the question, "Does a collection of sets contain at least mutually disjoint subsets?" ( 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:
where if element is selected; else, The matrix has 0's and 1's, where the i-th row corresponds the i-th set to be packed: means element j is in set i; else, The constraint means that at most one element of each set can be selected. If the IP maximum is less than or if it equals number of elements, the answer to the set packing problem is "No". Otherwise, let
be among those elements selected (re-index, if necessary). Let be all sets containing Due to the packing constraints, no selected element can be in two sets, so these are disjoint. The remaining set, is composed of all other elements
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 has exactly two 1's, and this is sometimes called [1]egree-2 inequalities. Another special case is the bin packing problem.

The IP formulation has the natural extension: where and This allows up to elements to be selected from the i-th set, and elements can be weighted by value