minimizing the summed cardinality of set unions

Question

this optimization problem, I am working on, is kind of making me crazy. ;)

Given is a list o of sets (with finite cardinality) of strictly positive integer values (Z>0), e.g.:

o_without_sizes =
[ {1, 2, 3, 4}
, {5, 6}
, {2, 3, 4, 5}
, {5, 6, 7}
, {7, 8}
. {9} ]

Every set has a name n (also in Z>0, but only for identification) and a fixed independent size value s (also in Z>0), e.g.:

type O = [(Name, Size, Values)]
o =
[ (1, 2, {1, 2, 3, 4})
, (2, 1, {5, 6})
, (3, 2, {2, 3, 4, 5})
, (4, 3, {5, 6, 7})
, (5, 2, {7, 8})
. (6, 1, {9}) ]

These sets are to be combined to unions b of a maximum size value sum h (>= max s, that means that no set has a size making it too big to fit into a single union), e.g. 4.

The goal is to find the b so that the sum of cadinalities of the unions in it is as small as possible. here is a bad b:

size:   3,  cardinality:   6,   sets: [1,2]  ,  values: [1,2,3,4,5,6]
size:   2,  cardinality:   4,   sets: [3]    ,  values: [2,3,4,5]
size:   3,  cardinality:   3,   sets: [4]    ,  values: [5,6,7]
size:   3,  cardinality:   3,   sets: [5,6]  ,  values: [7,8,9]
cardinality sum:  16

and the optimum b for this example:

size:   4,  cardinality:   5,   sets: [3,1]  ,  values: [1,2,3,4,5]
size:   4,  cardinality:   3,   sets: [2,4]  ,  values: [5,6,7]
size:   3,  cardinality:   3,   sets: [5,6]  ,  values: [7,8,9]
cardinality sum:  11

Until now I only implemented a naive brute force solution (Haskell code): http://lpaste.net/7204008959806537728

I was hoping to find a dynamic programming solution like it exists for the (Z>0) 0-1 knapsack problem, but did not yet succeed. Is my problem perhaps NP-hard? If so, is it many-one-reducible to SAT or something? Or is there a good approximation?

Of course, if there exists a known efficient optimal algorithm, it would be awesome if you could enlighten me. :)

Answer 1

Apparently, your problem is NP-complete (thanks FrankW), so we cannot expect a polynomial-time solution.

Nonetheless, if you are forced to do the best you can in practice, you might try formulating this as an integer linear programming (ILP) problem. You can introduce integer zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ if set $j$ is present in the $i$th union, and $x_{i,j}=0$ otherwise. This intended meaning can be enforced by adding constraints $0 \le x_{i,j} \le 1$ and

$$\sum_j \text{size}(j) x_{i,j} \le h \forall i,$$

$$\sum_i x_{i,j} \le 1 \forall j.$$

Now you introduce zero-or-one variables $y_{i,j}$, with the intended meaning that $y_{i,k}=1$ if the $i$th union includes the integer $k$, and $y_{i,k}=0$ otherwise. This intended meaning can be enforced by adding constraints $0 \le y_{i,k} \le 1$, and for each set $j$ that contains the integer $k$, we add the constraint

$$y_{i,k} \ge x_{i,j} \forall i.$$

Also, for each $i,k$, we add the constraint

$$y_{i,k} \le \sum_j x_{i,j}$$

where the sum ranges over all sets that contain the integer $k$.

Then you maximize the objective function

$$\sum_{i,k} y_{i,k}.$$

The solution to this ILP instance will give you the optimal solution to your optimization problem.

Answer 2

Your problem is NP-complete. We show this by reducing Partition to it.

In Partition you are given a set of numbers $a_1, \ldots, a_k$ and have to decide, if this set can be partitioned into two sets that sum up to the same value.

We map an instance of Partition to your problem by introducing for each $a_i$ the set $(i, a_i, \{1\})$. Set the maximum size to $\frac 12\sum_{i=1}^ka_i$. The original instance can be partitioned if and only if the resulting one can be united to cardinality sum 2.