Comportement de type XOR dans les réseaux de flux

XOR n'est pas le nom correct, mais je recherche une sorte de comportement exclusif.

Je suis en train de résoudre un ensemble de problèmes (d'affectation) différents en modélisant des réseaux de flux et en exécutant un algorithme de min-cost-max-flow. Les réseaux de flux sont très pratiques car de nombreux problèmes peuvent leur être réduits de manière simple et compréhensible. Dans mon cas, ce sont des correspondances avec des contraintes supplémentaires. Comme ces contraintes deviennent plus complexes, je me demande s'il existe des constructions existantes pour modéliser des comportements spécifiques.

Dans ce cas, je souhaite limiter le flux sortant d'un nœud à un seul bord.

Étant donné un graphique , les capacités intégrales et les coûts . Un noeud arbitraire est appelé . voisins directs sont appelés . Pouvons-nous remplacer les arêtes (rouge) par une construction de sorte qu'une seule arête puisse recevoir le flux ? Ce qui signifie que si obtient un flux (par exemple ), aucun autre bord (rouge) ne peut recevoir de flux.$G=(V, E)$$c(u,v)$$k(u,v)$$A$$B_1, ..B_n$$AB_1,...AB_n$$AB_1$$5/10$

Nous pourrions ajouter des nœuds / arêtes intermédiaires et jouer avec les coûts et les capacités. La capacité totale de notre nouvelle construction doit rester la même et le coût des différentes alternatives doit rester en quelque sorte proportionnel.

Mes questions sont donc:

1. Y a-t-il des constructions comme celle-ci en général? (Tous les mots clés, liens, articles)
2. Pouvez-vous suggérer une solution à mon problème spécifique?

En général, la réponse est non. Si nous mettons des restrictions de type XOR sur les bords sortants d'un sommet, nous pouvons prouver que trouver un écoulement min-coupe-max est NP-difficile. La technique consiste à y réduire le 3-SAT.

Supposons qu'il existe variables dans les clauses 3-SAT et . Nous créons un graphe encodant l'instance du problème 3-SAT. Pour chaque variable , nous créons un sommet connecté à la source avec un bord de capacité. Deux autres sommets , qui sont connectés à , sont créés pour représenter prenant également la valeur 0 ou 1 avec des arêtes de capacité .$n$$x_1, x_2, ..., x_n$$m$$c_1, c_2, ..., c_m$$G(V,E)$$x_i$$v_i$$s$$\infty$$u_i, w_i$$v_i$$x_i$$\infty$

Pour chacune des clauses , on crée un sommet correspond et est connecté aux variables ou à leurs négations dans la clause à arêtes de capacité . Par exemple, si , nous le connectons à avec des bords de capacité. Tous les sont connectés à l'évier avec des bords de capacité 1.$c_i$$o_i \in G$$o_i$$1$$c_i = (x_3 \lor x_4 \lor \neg x_5)$$u_3, u_4, w_5$$o_i$

Puisque et ne peuvent pas prendre la même valeur, nous mettons la restriction XOR sur les bords , , . Il peut être prouvé qu'il existe un flux maximal de taille si et seulement si l'instance 3-SAT est satisfaisable. Puisque le problème est trivial dans et que la réduction est polynomiale, nous concluons que la version de décision du flux du réseau de restriction XOR est NP-Complete.$x_i$$\neg x_i$$(v_i, u_i)$$(v_i, w_i)$$\forall i = 1,2,3,...,n$$m$$NP$

Pour votre première question, je ne connais aucune technique ou règle générale que vous pouvez utiliser pour modéliser des restrictions arbitraires dans les réseaux de flux. La plupart des exemples que j'ai vus sont généralement basés sur une certaine intuition quant à la nature des restrictions et semblent souvent au premier abord arbitraires.

Pour votre cas particulier, je n'ai pas encore trouvé de bonne correspondance avec max-flow. Cependant, je peux suggérer une solution alternative simple (vous l'avez peut-être déjà compris): Depth First Search from source .$s$

Comme le flux est limité à un seul bord sortant pour chaque sommet, vous disposez d'un chemin de la source à la cible. Ce chemin satisfait aux deux propriétés qu'il peut transporter le flux maximum parmi tous les autres chemins de la source à la cible , et qu'il a le coût le plus bas parmi tous ces chemins qui pourraient transporter le même flux de à .$s$$t$$s$$t$

• Démarrer un DFS à partir du$s$
• Lorsque vous descendez le DFS, gardez une trace de la capacité minimale actuelle de tous les bords rencontrés jusqu'à présent.
• Gardez également une trace du coût total actuel (longueur du chemin) rencontré jusqu'à présent.
• Si est atteint pendant le DFS, comparez ces deux valeurs avec des valeurs globales et mettez à jour les valeurs globales si nécessaire.$t$
• Revenez sur et continuez avec le DFS.$t$

Fondamentalement, vous énumérez tous les chemins de à utilisant le DFS et choisissez celui qui répond à vos critères de coût minimal et de débit maximal. Le DFS lui-même prend du temps , ce qui est plus efficace qu'un algorithme de flux max.$s$$t$$O(|E|)$

Pour s'appuyer sur la réponse de Paresh, si toutes les capacités maximales sont une (et tout le reste est entier), vous pouvez également diviser chaque nœud en deux afin que le nœud (n-) ait tous les bords d'entrée, le nœud (n +) ait tout le sort bords, et (n-) et (n +) sont connectés avec un bord de capacité maximale 1. Résolvez ce nouveau réseau à moindre coût et vous avez terminé.

Si les capacités maximales ne sont pas toutes égales, alors le problème est plus difficile. Vous pouvez formuler le problème sous forme de MIP (Mixed Integer Program). Les seules contraintes entières sont les contraintes XOR.

Heureusement, ceux-ci peuvent être modélisés comme des ensembles commandés spéciaux - type SOS1 (voir http://en.wikipedia.org/wiki/Special_ordered_set ). La plupart des solveurs MIP représentent spécifiquement les contraintes SOS1 et les géreront beaucoup plus efficacement (parfois vous devez le dire, parfois il le trouvera - vérifiez vos documents de solveur).

Bien que le MIP finira par converger vers la réponse optimale, pour les très gros modèles, vous n'aurez peut-être pas le temps d'attendre qu'il se termine. Faire converger de grands MIP est souvent plus de l'art que de l'ingénierie.

La prochaine suggestion est beaucoup plus de travail. Vous pouvez utiliser un solveur de réseau à faible coût comme sous-programme et possédez-vous une ramification sur les bords XOR à l'aide des techniques SOS1. Par exemple, sur chaque branche, désactivez la moitié la moins utilisée des arêtes sortantes, résolvez le réseau à coût minime (très rapide), répétez jusqu'à ce que toutes les contraintes XOR soient satisfaites.

Vous pouvez prioriser la séquence de branchement selon vos propres critères (volume de flux, coût du volume X, capacité réservée, nombre d'arêtes possibles, etc.). En guidant vous-même la recherche, vous pouvez affiner les parties de la solution qui sont les plus importantes pour vous.

Vous n'indiquez pas si vous savez toujours si votre problème est réalisable ou non. Si c'est toujours faisable, vous pourrez peut-être vous en sortir avec une stratégie de branchement qui est "sans retour en arrière", c'est-à-dire que vous la suivez comme une heuristique.

S'il n'est pas garanti que le problème soit réalisable, un MIP pourrait disparaître pour toujours. Une heuristique basée sur ce qui précède peut encore être utile pour trouver rapidement une solution avec un nombre relativement faible de violations.

En général, la réponse est inconnue, pas impossible!

nous concluons que la version de décision du flux du réseau de restriction XOR est NP-Complete. donc (c'est possible, on peut le faire) si et seulement si P = NP.