PACKING PROBLEM
Packing problem - The set packing problem is the question, "Does a collection of sets contain at least K mutually disjoint subsets?" (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 : Max(Sum_j(x_j): Ax <= 1, x in (0,1)n), where x_j = 1 if element j is selected; else, x_j = 0. The matrix A has 0's and 1's, where the i-th row corresponds the i-th set to be packed: A(i, j)=1 means element j is in set i; else, A(i, j)=0. The constraint Ax <= 1 means that at most one element of each set can be selected. If the IP maximum is less than K-1, or if it equals K-1 = number of elements, the answer to the set packing problem is "No". Otherwise, let x_1, ..., x_(K-1) be among those elements selected (re-index, if necessary). Let S_i be all sets containing x_i. Due to the packing constraints, no selected element can be in two sets, so these are disjoint. The remaining set, S_K, is composed of all other elements (x_K, ..., 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 A has exactly two 1's, and this is sometimes called degree-2 inequalities . Another special case is the bin packing problem . The IP formulation has the natural extension: Max(cx: Ax <= b, x in (0,1)n), where c >= 0 and b >= 1. This allows up to b_i elements to be selected from the i-th set, and elements can be weighted by value (c).
