1
$\begingroup$

Im trying to present a Combinatorial Optimization Problem that is kind of Assignment-Like in a different way so that it is perhaps easier to solve with conventional Algorithms. I'd like you to look over my attempt and point out errors and have a go at reformulating it yourself. So I guess I have 2 specific questions. Are there mistakes with my attempt? How can this problem be restated so it's easier/more obvious to solve (there are many known algorithms for Graph Coloring, but not any for this exact problem)? The Problem goes like this: You are given objects/items/elements/... with each 2 properties, say A and B. Let the properties be labeled by some numbers $i$ and $j$ for property A and B respectively. The number $n_{ij}$ describes the number of objects with the $i$-th property A and $j$-th property B. Assign objects to groups so that there is at least one object with each property A in every group, meaning groups will contain all properties of A. Furthermore the boolean number $f_{gk}$ indicates wether an object with the $g$-th property B can be in the same group as an object with the $k$-th property B.

Firstly I tried presenting it as a linear integer program, which is quite simple. The amount of variables scale with the product of the number groups and the number of properties A and B, so id assume that such an approach would be unviable even for small inputs. Another idea was to represent an object as a node in a graph. Such a node would then be connected to another node if their property A differ or their properties B "don't like each other". A colouring of that graph with the least amount colours should (I think) solve the problem, with each color corresponding to one group. One concern I have with this approach is that I don't know wether it promises to fufill the first restriction (all kinds property A in one Group). Obviously latter task is not much easier, but there are more conventional heuristics.

$\endgroup$
8
  • 1
    $\begingroup$ "there is at least one object with any property A in every group" > this is unclear: as you have described the problem, every object has a property $A$ and a property $B$. As such, a solution with one group per couple $(i, j)$ satisfies the conditions. $\endgroup$
    – Nathaniel
    Apr 3 at 0:32
  • $\begingroup$ @Nathaniel What is meant is that each group contains all properties A $\endgroup$
    – ImNotSure
    Apr 3 at 11:55
  • $\begingroup$ Given that the problem seems to be strongly NP-hard (per answer below), to have any hope of solving your instances you'll have to take advantage of their particular attributes, such as their sizes. Can you share any more information of this kind? $\endgroup$
    – Neal Young
    Apr 4 at 21:39
  • $\begingroup$ @NealYoung The number of properties of type $A$ and of type $B$ is roughly below 30. Furthermore the number of combinations of $B$ that can't be in a group together is way less than the number of combinations of $B$ that can be together in a group. But it doesn't seem as if there are any hidden attributes of the instances that can be exploited. $\endgroup$
    – ImNotSure
    Apr 5 at 9:00
  • $\begingroup$ How many objects? (I.e. $\sum_{ij} n_{ij}$) Any upper bound on the number of groups in a solution? Are you willing to accept any kind of approximate solution (e.g., not all constraints are met)? $\endgroup$
    – Neal Young
    Apr 5 at 13:38

1 Answer 1

0
$\begingroup$

This "answer" probably doesn't answer the question and might not be surprising, but it may be helpful to know in designing algorithms for the problem.

Lemma 1. The problem is strongly NP-hard, even when each $n_{ij}$ is in $\{0,1\}$ and there are at most two groups in any solution.

Proof sketch. The proof is by reduction from NAE-3SAT. Given a NAE-3SAT formula $\phi$, the reduction outputs an instance $I_\phi$ of OP's problem defined as follows.

  • For each variable $x$, there are two objects $(x, x)$ and $(x, \overline x)$ with $A$-property $x$, and $B$-properties $x$ and $\overline x$ respectively.

  • For each clause $C$ and literal $\ell$ in $C$ there is an object $(C, \ell)$ with $A$-property $C$ and $B$-property $\ell$.

  • For each variable $x$, disallow objects with $B$-property $x$ from being in the same group as objects with $B$-property $\overline x$.

This completes the reduction. It can be implemented in polynomial time. To finish we verify that it is correct. That is, $I_\phi$ is feasible if and only if $\phi$ is NAE-satisfiable.

First, suppose that $I_\phi$ is feasible. Because of the "variable" objects (of the form $(x, x)$ and $(x, \overline x)$) there must be exactly two groups. Call them $T$ and $F$. Define assignment $A$ to assign each variable $x$ as follows:

  • Assign $x$ true if $(x, x)$ is in $T$ and $(x, \overline x)$ is in $F$, and false otherwise (that is, if $(x, \overline x)$ is in $T$ and $(x, x)$ is in $F$).

Fix any clause $C$. By definition of $I_\phi$, group $T$ must contain the object $(C, \ell)$ for some literal $\ell$ in $C$. Also, $A$ must make $\ell$ true, because, letting $x$ be the variable of $\ell$ and $\ell'$ be the opposite literal, $(x, \ell')$ cannot be in $T$, so $(x, \ell)$ must be. So some literal in $C$ is true. Similarly, group $F$ must contain the object $(C, \ell)$ for some literal $\ell$ in $C$, so some literal in $C$ must be false. So $A$ NAE-satisfies $\phi$.

Conversely, suppose that $\phi$ has some NAE-satisfying assignment, say $A$. Construct a two-group solution $(T, F)$ for $I_\phi$ as follows:

  • For each object $(z, \ell)$, if $A$ makes literal $\ell$ true, put $(z, \ell)$ in $T$. Otherwise put it in $F$.

Above $z$ can be either $\ell$'s variable or a clause containing $\ell$. We leave it as an exercise to verify that $(T, F)$ is feasible for $I_\phi$. $~~~~\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.