Optimisation combinatoire avec des variables interdépendantes

Question

Ceci est mon premier post sur ces forums, merci d'avance pour toutes les réponses.

Je développe une application Java dans laquelle j'ai rencontré ce que je crois être un "problème d'optimisation combinatoire". Je n'ai que des compétences de base en mathématiques, donc essayer d'enquêter sur la mise en place d'un tel problème n'a pas été fructueux jusqu'à présent. Fondamentalement, ce que je voudrais faire est de programmer le moyen le plus efficace de trouver le sous-ensemble optimal n d'un plus grand ensemble N avec les variables v1, v2, v3 etc. Les variables ont toutes une valeur/score défini en plus à une valeur/score dépendant de certaines autres variables qui peuvent ou non être incluses dans le sous-ensemble.

Je suis intéressé par la sélection du sous-ensemble qui donne la valeur/le score total maximum.

Ainsi, par exemple, l'ensemble N comprend les variables suivantes et ont les valeurs définies ci-après, ainsi que les relations avec les autres variables:

v1 8 { v2 ; v8 } 
v2 6 { v1 ; v4 } 
v3 9 { } 
v4 7 { v2 ; v5 ; v8 } 
v5 6 { v4 ; v10 } 
v6 8 { v7 } 
v7 5 { v6 } 
v8 9 { v1 ; v4 } 
v9 6 { } 
v10 7 { v5 } 

Avoir une relation avec un ou plusieurs autres variables choisies signifie que la valeur totale aura un certain "décollage" - pour cet exemple, disons un pour chaque relation. donc sélectionner les cinq premières variables comme un sous-ensemble donnera une valeur totale de 30:

v1 8 { v2 ; v8 }  = 8 - 1 = 7 
v2 6 { v1 ; v4 }  = 6 - 2 = 4 
v3 9 { }    = 9 - 0 = 9 
v4 7 { v2 ; v5 ; v8 } = 7 - 2 = 5 
v5 6 { v4 ; v10 }  = 6 - 1 = 5 

Ceci est bien sûr pas un problème pour ces petits ensembles, mais je suis actuellement face à des ensembles de 100K et des sous-ensembles de 10K - Avec l'algorithme actuel, mon ordinateur a calculé la solution en 3 jours!

Je n'ai pas nécessairement besoin d'un code pour résoudre ce problème, mais plutôt la façon mathématique optimale de le faire (s'il y en a!). Gardez à l'esprit cependant que j'ai du mal à comprendre la notation mathématique au-dessus du niveau de base.

Encore une fois, merci d'avance pour toutes les réponses!

Answer 1

Malheureusement, ce problème est NP-difficile de trouver la solution optimale.

Si vous pouviez résoudre ce problème efficacement, vous pourriez résoudre le problème NP-difficile maximum independent set problem en définissant la valeur de chaque sommet à 1, et une pénalité très importante pour chaque bord.

Vous devriez plutôt chercher des solutions approximatives. Vous pouvez trouver que vous obtenez une réponse raisonnable avec un recuit simulé ou des algorithmes génétiques.

Answer 2

Vous pouvez voir votre ensemble sous forme de graphique. Chaque vX est un nœud/vertice avec la valeur respective. Exemple v1 est un nœud/vertice avec la valeur 8, v2 est un nœud/vertice avec la valeur 6, etc. Puis il y a des bords entre eux. L'exemple v1 a 2 bords: un pour v2 et un autre pour v8. Chaque arête peut également avoir une valeur (dans votre cas -1). Donc, si vous utilisez des graphiques, et sélectionnez v1 à v5: vous avez 8 + 6 + 9 + 7 + 6 (valeur de vertice) -1 -1 -1 -1 -1 -1 (valeur de bords). Essayez de voir ce http://jgrapht.org/ pour voir si cela vous aide.

Voir également Graph Teory: http://www.people.vcu.edu/~gasmerom/MAT131/graphs.html. Observer les plus longs/plus courts algorithmes de chemin (exemple: http://www.maxburstein.com/blog/introduction-to-graph-theory-finding-shortest-path/)

Answer 3

Pour un solveur de programme linéaire, prenez une entrée comme

v1 8 { v2 ; v8 } 
v2 6 { v1 ; v4 } 
v3 9 { } 
v4 7 { v2 ; v5 ; v8 } 
v5 6 { v4 ; v10 } 
v6 8 { v7 } 
v7 5 { v6 } 
v8 9 { v1 ; v4 } 
v9 6 { } 
v10 7 { v5 } 

et le convertir en un programme entier comme

maximize 8*v1 - v1v2 - v1v8 
     + 6*v2 - v2v1 - v2v4 
     + 9*v3 
     + 7*v4 - v4v2 - v4v5 - v4v8 
     + 6*v5 - v5v4 - v5v10 
     + 8*v6 - v6v7 
     + 5*v7 - v7v6 
     + 9*v8 - v8v1 - v8v4 
     + 6*v9 
     + 7*v10 - v10v5 

subject to 
v1 + v2 - v1v2 <= 1 
v1 + v8 - v1v8 <= 1 
v2 + v1 - v2v1 <= 1 
v2 + v4 - v2v4 <= 1 
v4 + v2 - v4v2 <= 1 
v4 + v5 - v4v5 <= 1 
v4 + v8 - v4v8 <= 1 
v5 + v4 - v5v4 <= 1 
v5 + v10 - v5v10 <= 1 
v6 + v7 - v6v7 <= 1 
v7 + v6 - v7v6 <= 1 
v8 + v1 - v8v1 <= 1 
v8 + v4 - v8v4 <= 1 
v10 + v5 - v10v5 <= 1 

binary v1, v1v2, v1v8, 
     v2, v2v1, v2v4, 
     v3, 
     v4, v4v2, v4v5, v4v8, 
     v5, v5v4, v5v10, 
     v6, v6v7, 
     v7, v7v6, 
     v8, v8v1, v8v4, 
     v9, 
     v10, v10v5 

Votre taille d'instance est probablement trop pour une solution optimale, mais Je ne sais jamais ...