Sélectionnez le plus d'éléments qui ne se chevauchent pas de sorte que la somme de leur taille est maximisée

Question

J'essaie de trouver un algorithme pour le problème suivant.

Dire que j'ai un certain nombre d'objets A, B, C, ...

J'ai une liste de combinaisons valides de ces objets. Chaque combinaison est de longueur 2 ou 4.

Par exemple. AF, CE, CEGH, ADFG, ... et ainsi de suite.

Pour les combinaisons de deux objets, par ex. AF, la longueur de la combinaison est 2. Pour la combinaison de quatre objets, par exemple CEGH, la longueur de la combinaison.

Je ne peux sélectionner que des combinaisons qui ne se chevauchent pas, c'est-à-dire que je ne peux pas sélectionner AF et ADFG parce que les deux nécessitent les objets 'A' et 'F'. Je peux choisir les combinaisons AF et CEGH car elles ne nécessitent pas d'objets communs. Si ma solution ne comprend que les deux combinaisons AF et CEGH, alors mon objectif est la somme de la longueur des combinaisons, soit 2 + 4 = 6.

Étant donné une liste d'objets et leurs combinaisons valides, comment est-ce que je choisis les combinaisons les plus valides qui ne se superposent pas les unes aux autres de sorte que je maximise la somme des longueurs des combinaisons? Je ne veux pas le formuler comme une IP car je travaille avec une instance de problème avec 180 objets et 10 millions de combinaisons valides et la résolution d'une adresse IP en utilisant CPLEX est extrêmement lente. Vous cherchez un autre moyen élégant de le résoudre. Puis-je peut-être convertir cela en réseau? Et le résoudre en utilisant un algorithme max-flow? Ou un programme dynamique? Coincé sur la façon de résoudre ce problème.

Answer 1

Ma première tentative pour montrer que ce problème était NP-difficile était erronée, car elle ne tenait pas compte du fait que seules les combinaisons de taille 2 ou 4 étaient autorisées. Cependant, en utilisant Jim D.'s suggestion pour réduire de 3-dimensional matching (3DM), nous pouvons montrer que le problème est néanmoins NP-difficile. Je vais montrer que la forme de problème de décision naturelle de votre problème ("Étant donné un ensemble O d'objets, et un ensemble C de combinaisons de 2 ou 4 objets de O, et un entier m, existe-t-il un sous-ensemble D de C tel que tous les ensembles dans D sont disjoints par paires, et l'union de tous les ensembles dans D a une taille au moins m? ") est NP-difficile. Il est clair que le problème d'optimisation (c'est-à-dire, votre problème original, où nous cherchons un sous-ensemble réel de combinaisons qui maximise m au-dessus) est au moins aussi difficile que ce problème. (Pour voir que le problème d'optimisation n'est pas "beaucoup" plus dur que le problème de décision, notez que vous pouvez d'abord trouver la valeur m maximale pour laquelle une solution existe en utilisant une recherche binaire sur m dans laquelle vous résolvez un problème de décision à chaque étape. puis, une fois que cette valeur m maximale a été trouvée, résoudre une série de problèmes de décision dans laquelle chaque combinaison est à son tour supprimée: si la solution après avoir supprimé une combinaison particulière est toujours "OUI", alors elle peut également être omise les futures instances de problèmes, alors que si la solution devient "NON", alors il est nécessaire de garder cette combinaison dans la solution.Étant donné une instance (X, Y, Z, T, k) de 3DM, où X, Y et Z sont des ensembles qui sont disjoints par paire les uns des autres, T est un sous-ensemble de X * Y * Z (c.-à.-d. , un ensemble de triplets ordonnés avec les premier, deuxième et troisième composants de X, Y et Z, respectivement) et k étant un entier, notre tâche est de déterminer s'il existe un sous-ensemble U de T tel que | U | > = k et tous les triplets dans U sont disjoints par paires (c'est-à-dire, pour répondre à la question, "Y a-t-il au moins k triplets sans chevauchement dans T?"). Pour transformer une telle instance de 3DM en une instance de votre problème, tout ce que nous devons faire est de créer une nouvelle combinaison de 4 à partir de chaque triple dans T, en ajoutant une valeur factices distincte à chacun. L'ensemble d'objets dans l'instance construite de votre problème consistera en l'union de X, Y, Z et du | T | valeurs fictives que nous avons créées. Enfin, définissez m sur k. Supposons que la réponse à l'instance 3DM d'origine soit "OUI", c'est-à-dire qu'il y ait au moins k triplets non chevauchants dans T. Alors chacun des k triplets dans une telle solution correspond à une combinaison de 4 dans le entrée C à votre problème, et pas deux de ces 4 combinaisons se chevauchent, puisque par construction, leurs 4èmes éléments sont tous distincts, et par hypothèse du. Il y a donc au moins m = k combinaisons non chevauchantes dans le cas de votre problème, donc la solution pour ce problème doit aussi être "OUI". Dans l'autre sens, supposons que la solution à l'instance construite de votre problème soit "OUI", c'est-à-dire qu'il y ait au moins m combinaisons de 4 chevauchements en C. Nous pouvons simplement prendre les 3 premiers éléments de chacune des 4-combinaisons (en jetant la quatrième) pour produire un ensemble de k = m non-chevauchement des triplets dans T, de sorte que la réponse à l'instance originale 3DM doit également être "OUI".

Nous avons montré qu'une réponse OUI à un problème implique une réponse OUI à l'autre, donc une réponse NON à un problème implique une réponse NON à l'autre. Ainsi, les problèmes sont équivalents. L'instance de votre problème peut clairement être construite dans le temps et l'espace polynomiaux. Il s'ensuit que votre problème est NP-difficile.

Answer 2

Vous pouvez réduire ce problème au maximum weighted clique problem, qui est malheureusement NP-difficile. Construisez un graphique tel que chaque combinaison soit un sommet de poids égal à la longueur de la combinaison, et connectez des sommets si les combinaisons correspondantes ne partagent aucun objet (c'est-à-dire si vous pouvez les prendre tous les deux en même temps). Ensuite, une solution est valide si et seulement si c'est une clique dans ce graphe.

Une simple recherche sur google fait apparaître beaucoup d'algorithmes d'approximation pour ce problème, tels que this one.