3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I can't understand what you mean by "of a maximum size value sum h (> max s)". Can you elaborate? Perhaps split that into two sentences, and define all phrases bebefore using them? What's a "maximum size value sum"? What's h? What do you mean by > max s? In particular: how does the size of a union of sets depend upon the size of the individual sets? $\endgroup$ – D.W. Feb 21 '14 at 0:55
  • $\begingroup$ Thanks for helping me cleaning up my question. I edited it and hope it is better now. $\endgroup$ – Tobias Hermann Feb 21 '14 at 9:56
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That sounds great. Thank you very much. I think I got the the x and y part right. They should look like so for my shown optimum codepad.org/DEdTnl1V Now I "only" have to learn about ILP and how to apply it to the inequality constraints you showed. ;) Do you have any hints or links for me to get me started on this? (In the end I will probably try to use C++, Python or Haskell.) $\endgroup$ – Tobias Hermann Feb 21 '14 at 10:05
  • 1
    $\begingroup$ @Dobi, python would be your best bet, as it has nice hookups to CPLEX [excellent software for solving ILPs, LPs, and QPs]. However it costs money. If you are a student you may request an academic license for free. Otherwise there are still free-alternatives $\endgroup$ – Nicholas Mancuso Feb 24 '14 at 18:05
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I suspected something like this. Thanks for simple and good explanation. $\endgroup$ – Tobias Hermann Feb 21 '14 at 10:00

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.