3
$\begingroup$

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.

Context

Perhaps one way to think about this, is that you have a paint brush of a certain size that is larger than an element - that is it can only paint a collection of elements in one stroke. The allowed places to 'stroke' are overlapping - they are the sets in S. When you paint a particular set a particular color there is a cost associated with it that you would like to minimize. When you paint an area, you can paint the overlapping areas the same color only paying for the 'difference' in cost (kinda).

Questions

  • Is the formulation above well formed, and understandable? Is there a better formulation more related to an already existing problem?
  • Can this be expressed as an integer linear programming problem?
  • How would you solve this problem?

I have constructed an algorithm to solve this problem that first tries to use branch and bound to construct the optimal solution - it does quite well, but as the problem gets larger it slows down. If it starts to take too long I stop the branch and bound and use a random search to improve a solution. I think that having a better mathematical understanding of the problem will help me solve it better - I would also like to prove that this is NP-Hard.

One idea I have toyed with is to construct a new collection of sets $S'$ which consists not only of all the original sets but all of their combinations / unions (I understand this will be a lot, $2^k - 1$ right, but for at least proving the complexity of the problem it should be ok..) and then duplicating those sets once for each color, and then solving for the weighted exact set cover. Does that 'reduction' prove that this is NP-Hard? Is that even a reduction?

I've also thought about thinking about the problem the other way around, that is thinking about it in terms of the sets being assigned a certain color - but then I don't know exactly how to account for the overlapping of the sets in the minimization, also there will be some sets that do not have a single color so long as the sets that do have a single cover form a covering of the universe.

Thanks in advance.

$\endgroup$
  • $\begingroup$ I'm afraid your strategy won't give you an NP-hardness result. To show NP-hardness, you (confusingly) actually need to show how to convert any instance of some chosen NP-hard problem into an instance of your problem. This is the opposite direction to what most people expect. $\endgroup$ – j_random_hacker Feb 11 '17 at 13:10
  • $\begingroup$ @j_random_hacker Ah, yes that makes perfect sense. Just because a problem could be expressed as a harder problem doesn't mean it is hard. For example, the min cut can be expressed as a linear program, but there are polynomial algorithms for getting the min cut / max flow. Gotcha - Hmm. $\endgroup$ – Matt D Feb 11 '17 at 15:35
2
$\begingroup$

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 must be at least one ground-set element $b \in x_i$ that is not also in $x_j$. Thus assigning $b$ the colour $x_j$ incurs a cost of 1, which cannot be recouped via any other means. Since we know that $(X'', f'')$ has a cost of 0, this is a contradiction. Thus it follows that if there exists a zero-cost solution $(X, f)$ to the constructed instance of your problem, then there must also exist a zero-cost solution $(X'', f'')$ to it in which no chosen set contains any other chosen set and in which no set properly overlaps any other set. $X''$ is, thus, an exact cover -- so the answer to the Exact Cover instance must also be "YES".

We have established that a "YES" answer to the constructed instance of your problem implies a "YES" answer to the original Exact Cover instance, and vice versa. This implies that a "NO" answer to either instance implies a "NO" answer to the other, which in turn implies that the two problems are equivalent. Since the construction of instance of your problem took only polynomial time and space, an algorithm that solves your problem in polynomial time could also be used to solve Exact Cover in polynomial time. Since Exact Cover is NP-hard, it follows that your problem must be NP-hard too.

$\endgroup$
  • $\begingroup$ I have been thinking about your answer a bit more. I believe that your proof could be simplified by the second constraint: namely that each ground element is only allowed a single color. In your construction you have created a color for each set, and if we assume that a solution $(X, f)$ exists with minimum cost (0), then each of the selected sets in $X$ must be their corresponding color $f(x_i) = c_i$, and because of the constraint that no block is allowed to have multiple colors, these sets must not overlap, either fully contained or otherwise. $\endgroup$ – Matt D Apr 11 '17 at 18:50
  • $\begingroup$ "if we assume that a solution $(X,f)$ exists with minimum cost (0), then each of the selected sets in $X$ must be their corresponding color" -- you seem to think that this step is immediate, but it's not, partly because it's not true ;) Specifically, any solution that has 2 sets, one of which contains the other, must violate this: the elements that belong to both sets can only be assigned the colour corresponding to (at most) one of them. Proving that this statement actually does hold -- for some solution -- is what takes most of the work in my proof. $\endgroup$ – j_random_hacker Apr 11 '17 at 20:31
  • $\begingroup$ As I was writing up a long comment explaining how you were wrong - I realized that no, I was wrong. Thanks for the clarification ;) I believe I understand now. The breakdown in my thinking was somewhat strange in retrospect; the part that I was missing is that a set $x_i$ contained within some other set $x_j$ will have a minimum cost assignment in either $c_i$ or $c_j$. I had mistakenly thought that any other color assignment would necessarily introduce some cost - but it does not. Thanks again! $\endgroup$ – Matt D Apr 11 '17 at 21:20
  • $\begingroup$ No problem :) Writing long comments explaining why someone else is wrong is also one of my favourite ways to discover that I'm actually wrong myself ;) $\endgroup$ – j_random_hacker Apr 11 '17 at 22:29

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.