Solving for the minimum cost, colored, set cover

Formulation

This problem has four entities:

• A universe: $U = \{1, 2, ..., n\} $ of $n$ elements, indexed with $u$

• A set of available colors: $C \in \{1, 2, ..., m\} $ with $m$ colors, indexed with $c$

• A collection of sets: $S = \{s_1, s_2, ..., s_k\}$ where there are $k$ sets, indexed with $i$. These sets contain elements of the Universe. $\bigcup S = U$.

• A cost function: $cost(u, c)$ where $u$ is the element, $1 \le u \le n$, and $c$ is the color of that element $1 \le c \le m$

We must assign a single color to each element such that the overall cost of the color assignment is minimized AND such that a valid set cover exists such that all elements in each set of the set cover have the same color. That is:

$$min \sum\limits_u cost(u, c) x_{u,c}$$

subject to

• $0 \le x \le 1$. That is, $x_{u,c}$ is a binary decision variable which indicates that a particular element ($u$) is a particular color ($c$).

• $\sum \limits_c x_{u,c} = 1 \quad \forall u \in U$. That is, an element may only have one color.

• $\sum \limits_{s:u\in S} y_s \ge 1 \quad \forall u \in U$. That is, every element must be in the set cover.

• $0 \le y \le 1$. That is, $y_{s}$ is a binary decision variable which indicates that a particular set ($s$) is included in the set cover.

• $ x_{s_{i_1},c} = x_{s_{i_2}, c} = ... = x_{s_{i_l},c} \quad \forall s_i \in S \bigm| y_s = 1$. That is, given that a set is included in the set cover, everything in that set must be the same color.

Example

$U = \{1, 2, 3, 4, 5, 6, 7, 8\}$

$C = \{r, g\}$

$S = \{\{1, 2\}, \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 5\}, \{4, 5, 6\}, \{5, 6, 7\}, \{6, 7, 8\}, \{7, 8\}\}$

$cost_{r} = \{0, 0, 2, 1, 2, 1, 1, 0\}$

$cost_{g} = \{1, 0, 1, 2, 0, 0, 0, 3\}$

Optimal solution:
$= \{r, r, g, g, g, g, r, r\}, \quad cost=4$

That is, the set cover is $\{\{1, 2\}, \{3, 4, 5\}, \{4, 5, 6\}, \{7, 8\}\}$.

Typically, $U$ consists of 100-2000 elements, $C$ consists of 3 - 10 colors, $S$ consists of 200-4000 sets of 5-25 elements.

Unfortunately this is NP-hard (even if we use only the costs 0 and 1), so it's very unlikely that there exists a polynomial-time algorithm that will solve every instance. I'll show this by reducing the NP-hard problem Exact Cover to your problem. I'll work with the decision variant of your problem, in which we are given a number $q$ in addition to $U$, $C$, $S$ and $cost()$, and the task is to report whether or not there is a solution with cost at most $q$. (With an algorithm that answers the decision problem, minimisation/maximisation can then be accomplished efficiently with binary search, and an actual solution realising that optimal solution size can also be recovered without too much extra difficulty.)

Recall that in the Exact Cover problem, we are given a collection $A = \{a_1, \dots, a_r\}$ of sets, each of which is a subset of some ground set $B$, and our task is to report whether or not it is possible to choose a subset $X \subseteq A$ of sets in $A$ such that every element in $B$ belongs to exactly one set in $X$. To encode an instance of the Exact Cover problem as an instance of your problem:

• For each set $a_i$ in $A$:

• Add the set $a_i$ to $S$, as $s_i$.

• Add a new colour $c_i$ to $C$.

• Set $cost(b_j, c_i) = 0$ for every $b_j \in a_i$.

• Set $cost(b_j, c_i) = 1$ for every $b_j \notin a_i$.

• Set $U = \cup_{s_i \in S}s_i$ as usual.

• Set $q = 0$.

Basically, we create a colour $c_i$ for each set $a_i$ in $A$, and set the costs of that colour so that ground elements from the corresponding set ($a_i$) get no cost, while every other ground element gets a positive cost. This means that whenever there does exist an exact cover for $A$, it is possible to create a zero-cost solution to the corresponding constructed instance of your problem: just assign every ground-set element the colour corresponding to the unique set that contains it. Thus, a "YES" answer to the Exact Cover problem implies a "YES" answer to the constructed instance of your problem.

In the other direction, we would like to show that a "YES" answer to the constructed instance of your problem implies a "YES" instance to the original Exact Cover problem instance. So, we start by assuming a "YES" answer to the constructed instance of your problem. This means that there exists a zero-cost assignment of colours to ground-set elements that could be produced by choosing a set cover from $S$, then choosing a colour for each set in the cover, and assigning that colour to all ground-set elements belonging to that set. We can represent such a solution as a pair $(X, f)$, where $X \subseteq S$ is the set of ground-element sets chosen for the cover, and $f : X \to C$ is a function that maps a set in $X$ to a colour in $C$. (Even though it is individual ground-set elements that we colour and not sets of them, $f$ is still well-defined for a feasible solution, since we require of every set $x \in X$ that every $e \in x$ is assigned the same colour.)

In order to easily build a solution to the original Exact Cover instance from $(X, f)$, we want the ground-set elements having some particular colour to be exactly the ground-set elements in some set in $A$: then we can simply go through each colour present in the solution to the your problem (i.e., in the range of $f$) and include the corresponding set from $A$ in the Exact Cover solution. So in other words, we would like to have a solution $(X, f)$ that has $f(x_i) = c_i$ for each $x_i \in X$. But this is complicated by the fact that $X$ could contain sets that overlap, which is of course forbidden in an Exact Cover solution. Between any pair $x \in X, x' \in X$ there are two kinds of potential overlap: containment (either $x \subset x'$ or vice versa), and "proper overlapping", where $x \cap x' \neq \emptyset$ but neither set contains the other.

To address the problem of containment, it is easy to see that, whenever there exists a solution $(X, f)$ that contains a pair of sets $x \in X$ and $x' \in X$, one of which contains the other, then there also exists another solution $(X', f')$ with the same cost and in which the smaller of the two sets has been removed. (If $x = x'$, then just remove either one arbitrarily.) Iterating this process until we cannot apply it any more ensures that there must exist a solution $(X'', f'')$ in which no set in $X''$ contains any other set in $X''$. (Note that all we care about is the fact that such a solution must exist; for the purposes of answering the YES/NO question about the original Exact Cover instance, we don't need to know a specific solution.)

This leaves the problem of "properly overlapping" sets. I'll now show that these cannot occur in any zero-cost solution to your problem.

Suppose towards contradiction that there is some chosen set $x_i \in X''$ such that $f(x_i) \neq c_i$. Then $f(x_i) = c_j$ for some $j \neq i$, with $x_j \in X''$ also. But because there is no other set in $X''$ that contains $x_i$ as a subset, there

StackExchange Computer Science Q#70148, answer score: 2