0
$\begingroup$

I've got 30 elements which has to be grouped/sorted into 10 ordered 3-tuple. There are several rules and constraints about grouping/sorting. For example: Element $A$ must not be in the same tuple same unit $B$. Element $C$ must not be right in front of element $A$, etc.

I am searching for an approximated algorithm:

  1. We don't need to achieve the exact optimum
  2. It is OK for some rules not to be satisfied, if it helps to fulfill more rules.

Do you know of any algorithm/proceeding that solve this problem or a similar one? I fear to solve it in an optimal way, you have to try out every possible solution-> $2 ^ {30}$

EDIT: Sorry for the bad explanation. I am trying to make it a bit clearer: I got 30 elements for example: $\{1,2,3,\ldots,30\}$. I need to group them into 3-tuples so that i get something like: $(1,2,3)$, $(4,5,6)$,$\ldots$,$(28,29,30)$.

There are several constraints. For example:

  • 1 cannot precede 2 in an ordered tuple, so, for instance $(1,2,3)$ is not a valid tuple.
  • 5 must be together with 4.

Those constraints can be broken and its possible that there is no solution where all rules can be fulfilled.
An solution is considered as good if the amount of rules broken is "low".

Hope that makes it clearer and thanks for the help so far.

$\endgroup$
  • $\begingroup$ Sorry, but I can't understand your requirements or what you are asking. What does it mean to sort 30 units "into ordered 3-tuple"? Perhaps you might want to edit the question to try to explain more clearly and give an example. Also, since you say that some rules can be broken, what qualifies as a valid solution? How would you recognize whether an alleged solution is acceptable or not? Are you looking for a "sorting" (of some form) that minimizes the number of rules that are broken, or minimizes the number of units that participate in a broken rule, or something like that? If so, what? $\endgroup$ – D.W. Nov 25 '13 at 3:40
  • $\begingroup$ Have you looking into using SLD resolution (Wikipedia)? SLD resolution is how Prolog solves problems. $\endgroup$ – Guy Coder Nov 25 '13 at 12:10
  • $\begingroup$ $2^30$ would be fine for brute forcing: it's only a billion. But I think you'd actually need to consider something like $30!/10! \approx 7\times 10^{25}$ cases. $\endgroup$ – David Richerby Nov 25 '13 at 20:08
  • $\begingroup$ Thanks, you are of course right. So the optimal solution can not be found by brute force but a nearly optimal solution by a genetic algorithm $\endgroup$ – Tim SP Nov 26 '13 at 0:59
  • 1
    $\begingroup$ What is "low"? 50% of the constraints? 7 of them? Can you try to be more formal, or give more sources to your problem? $\endgroup$ – Ran G. Dec 16 '13 at 0:38
2
$\begingroup$

The question of whether we can solve this problem without violating any rules is a set cover problem.

In particular, the universe is $U=\{1,2,\dots,30\}$, and each possible tuple $t_i$ that follows all the rules corresponds to a set $S_i \subseteq U$. In this way, we get many sets $S_1,S_2,\dots,S_n$. We want to know whether there is some 10 of these sets whose union is all of $U$. That's the set cover problem. There are well-known hardness results and approximation algorithms for the set cover problem.


Now let's introduce the opportunity to violate some of the rules. Associate to each tuple $t_i$ a cost $c_i$. If the tuple $t_i$ follows all the rules, there is no cost for using that tuple: $c_i=0$. If the tuple $t_i$ violates some of the rules, we'll set $c_i$ to denote the cost of those violations (for instance, if each rule that is violated costs \$1, then $c_i$ can be set accordingly). In this way we get a collection of sets $S_1,S_2,\dots,S_n$ with associated costs $c_1,c_2,\dots,c_n$ for each of them.

Now our goal is to find some 10 of those sets whose union is $U$, and where the sum of their costs is minimized.

This can be formulated as an integer linear program (ILP). In particular, we'll introduce $n$ integer variables $x_i$; the intended meaning is that $x_i=1$ means that $S_i$ is one of the 10 sets that were selected, and $x_i=0$ means $S_i$ was not selected. Now we want to minimize

$$\sum_i c_i x_i,$$

subject to the constraints

$$\sum_{j \in S_i} x_i \ge 1 \text{ for each $j=1,2,\dots,30$}$$

(where the sum is over all $i$ such that $j \in S_i$) and $0 \le x_i \le 1$. Now you could throw any ILP solver at this problem and see what solution it turns up.

$\endgroup$
1
$\begingroup$

Just to let anyone know, who got a similiar problem. I found genetic algorithm as an solution to it.

  1. Create a population by creating multiple individuals. This is done by setting the elements on a random spot in a vector.
  2. Generating the fitness of the individuals by checking how many rules are broken. The fitness is reduced by 1 per rule broken.
  3. Checking if the solution is acceptable(Either fitness = 0 or termination criteria satisfied)
  4. Doing tournament selection with suitable size(i chosed 3) on the population -> Getting the tournament winner -> Reproduct it, Mutate it or 1-Point-Crossover 2 of them and add it to the limbo. -> Repeat 4. till the limbo got population size
  5. Goto 3.

Hope you get the idea of it. Thanks for the comments on the original question. If you got any question, feel free to ask.

$\endgroup$

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.