XOR-ähnliches Verhalten in Flussnetzwerken

XOR ist nicht der richtige Name, aber ich suche nach einem exklusiven Verhalten.

Ich löse derzeit eine Reihe verschiedener (Zuweisungs-) Probleme, indem ich Flussnetzwerke modelliere und einen Min-Cost-Max-Flow-Algorithmus ausführe. Flow-Netzwerke sind sehr praktisch, da viele Probleme auf einfache und verständliche Weise auf sie reduziert werden können. In meinem Fall handelt es sich um Übereinstimmungen mit einigen zusätzlichen Einschränkungen. Da diese Einschränkungen immer komplexer werden, habe ich mich gefragt, ob es einige Konstruktionen gibt, um bestimmte Verhaltensweisen zu modellieren.

In diesem Fall möchte ich den ausgehenden Fluss eines Knotens auf eine einzelne Kante beschränken.

Bei gegebenem Graphen $G=(V, E)$ sind die Integralkapazitäten $c(u,v)$ und die Kosten $k(u,v)$ . Ein beliebiger Knoten heißt $A$ . Die direkten Nachbarn heißen $B_1, ..B_n$ . Können wir die Kanten ersetzen? $AB_1,...AB_n$ (rot) mit einer Konstruktion, so dass nur eine Kante fließen kann? Das bedeutet , dass , wenn eine gewisse Strömung erhält (zB 5 / 10 ) kein anderes (rot) Randströmung aufnehmen kann.$AB_1$$5/10$

Wir könnten Zwischenknoten / Kanten hinzufügen und mit Kosten und Kapazitäten spielen. Die Gesamtkapazität unseres Neubaus muss gleich bleiben und die Kosten für die verschiedenen Alternativen müssen irgendwie proportional bleiben.

Meine Fragen sind also:

1. Gibt es solche Konstruktionen im Allgemeinen? (Alle Schlüsselwörter, Links, Papiere)
2. Können Sie eine Lösung für mein spezifisches Problem vorschlagen?

Im Allgemeinen lautet die Antwort nein. Wenn wir XOR-ähnliche Einschränkungen für die ausgehenden Kanten eines Scheitelpunkts festlegen, können wir beweisen, dass das Finden eines Min-Cut-Max-Flusses NP-schwer ist. Die Technik besteht darin, 3-SAT darauf zu reduzieren.

Nehmen wir an, es gibt Variablen x 1 , x 2 , . . . , x n in den 3-SAT- und m- Klauseln c 1 , c 2 , . . . , C m . Wir erstellen einen Graphen G ( V , E ) , der die Instanz des 3-SAT-Problems codiert. Für jede Variable x i erstellen wir einen Scheitelpunkt v i, der mit der Quelle s mit einer Kante von $n$$x_1, x_2, ..., x_n$$m$$c_1, c_2, ..., c_m$$G(V,E)$$x_i$$v_i$$s$$\infty$Kapazität. Zwei weitere Eckpunkte , die mit v i verbunden sind , werden erzeugt, um x i darzustellen, wobei der Wert 0 oder 1 auch mit Kanten der Kapazität ∞ angenommen wird .$u_i, w_i$$v_i$$x_i$$\infty$

Für jede der Klauseln erstellen wir einen entsprechenden Scheitelpunkt o i ∈ G und o i ist mit den Variablen oder ihren Negationen in der Klausel mit Kanten der Kapazität 1 verbunden . Zum Beispiel, wenn c i = ( x 3 ∨ x 4 ∨ ¬ x 5 ) , schließen wir es u 3 , u 4 , w 5 mit den Kanten der Kapazität. Alle o i sind mit Kanten der Kapazität 1 mit der Spüle verbunden.$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$

Da und ¬ x i nicht den gleichen Wert annehmen können, setzen wir die XOR-Beschränkung auf Kanten ( v i , u i ) , ( v i , w i ) , ∀ i = 1 , 2 , 3 , . . . , N . Es kann bewiesen werden, dass genau dann ein maximaler Fluss der Größe m vorliegt, wenn die 3-SAT-Instanz erfüllt werden kann. Da das Problem trivial in N $x_i$$\neg x_i$$(v_i, u_i)$$(v_i, w_i)$$\forall i = 1,2,3,...,n$$m$$NP$ und die Reduktion ist polynomisch, wir schließen daraus, dass die Entscheidungsversion des XOR-Restriktionsnetzwerkflusses NP-vollständig ist.

Für Ihre erste Frage kenne ich keine allgemeinen Techniken oder Faustregeln, mit denen Sie beliebige Einschränkungen in Flussnetzwerken modellieren können. Die meisten Beispiele, die ich gesehen habe, basieren im Allgemeinen auf einer gewissen Intuition über die Art der Beschränkungen und scheinen oft zunächst willkürlich.

$s$

$s$$t$$s$$t$

• $s$
• Behalten Sie beim Herunterfahren der DFS die aktuelle Mindestkapazität aller bisher angetroffenen Kanten im Auge.
• Behalten Sie auch die aktuellen Gesamtkosten (Pfadlänge) im Auge, die bisher aufgetreten sind.
• $t$
• $t$

$s$$t$$O(|E|)$

Um auf Pareshs Antwort aufzubauen: Wenn alle maximalen Kapazitäten eins sind (und alles andere eine ganze Zahl ist), können Sie auch jeden Knoten in zwei Teile aufteilen, sodass der Knoten (n-) alle In-Kanten und der Knoten (n +) alle Out-Kanten hat Kanten und (n-) und (n +) sind mit einer Kante maximaler Kapazität 1 verbunden. Lösen Sie dieses neue Min-Cost-Netzwerk und Sie sind fertig.

Wenn die maximalen Kapazitäten nicht alle eins sind, ist das Problem schwieriger. Sie können das Problem als MIP (Mixed Integer Program) formulieren. Die einzigen ganzzahligen Einschränkungen sind die XOR-Einschränkungen.

Glücklicherweise können diese als speziell bestellte Sets modelliert werden - Typ SOS1 (siehe http://en.wikipedia.org/wiki/Special_ordered_set ). Die meisten MIP-Löser stellen speziell SOS1-Einschränkungen dar und behandeln sie viel effizienter (manchmal müssen Sie es mitteilen, manchmal wird es herausgefunden - überprüfen Sie Ihre Solver-Dokumente).

Obwohl der MIP letztendlich zur optimalen Antwort konvergiert, haben Sie bei wirklich großen Modellen möglicherweise nicht die Zeit, auf den Abschluss zu warten. Die Konvergenz großer MIPs ist oft mehr Kunst als Technik.

Der nächste Vorschlag ist viel mehr Arbeit. Sie können einen Min-Cost-Netzwerklöser als Unterprogramm verwenden und mithilfe von SOS1-Techniken eine Verzweigung an den XOR-Kanten vornehmen. Schalten Sie beispielsweise in jedem Zweig die am wenigsten genutzte Hälfte der Außenkanten aus, lösen Sie das Min-Cost-Netzwerk auf (sehr schnell) und wiederholen Sie den Vorgang, bis alle XOR-Bedingungen erfüllt sind.

Sie können die Verzweigungssequenz nach Ihren eigenen Kriterien (Durchflussvolumen, Volumen X-Kosten, reservierte Kapazität, Anzahl möglicher Kanten usw.) priorisieren. Indem Sie die Suche selbst leiten, können Sie die für Sie wichtigsten Teile der Lösung genauer untersuchen.

Sie geben nicht an, ob Sie immer wissen, ob Ihr Problem machbar ist oder nicht. Wenn es immer machbar ist, können Sie möglicherweise mit einer Verzweigungsstrategie davonkommen, die "backtrackfrei" ist, dh Sie folgen ihr wie eine Heuristik.

Wenn das Problem nicht garantiert wird, kann ein MIP für immer verschwinden. Eine auf dem oben Gesagten basierende Heuristik kann immer noch wertvoll sein, um schnell eine Lösung mit einer relativ geringen Anzahl von Verstößen zu finden.

Im Allgemeinen ist die Antwort unbekannt, nicht unmöglich!

Wir schließen daraus, dass die Entscheidungsversion des XOR-Restriktionsnetzwerkflusses NP-Complete ist. daher (es ist möglich, wir können das tun) genau dann, wenn P = NP ist.