XOR-ähnliches Verhalten in Flussnetzwerken

8

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 B1,..Bn . Können wir die Kanten ersetzen? AB1,...EINB.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.EINB.15/.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?
Patrick Schmidt
quelle
Um ganz klar zu sein, handelt es sich um ein Min-Cost-Max-Flow- Problem oder ein Min-Cost-Flow-Problem , bei dem eine bestimmte Menge an Flow auf die billigste Art und Weise gesendet werden muss?
Paresh
Es ist ein Min-Cost-Max-Flow-Problem. Meine Frage wurde aktualisiert.
Patrick Schmidt
1
Darf ich fragen, was das ursprüngliche Problem war, das Sie mit diesen Einschränkungen einem Flow-Netzwerk zugeordnet haben? Ich frage, weil es eine einfache alternative Lösung gibt, und ich möchte nur sicherstellen, dass dies nicht der ursprüngliche Algorithmus war, den Sie auf max-flow abbilden möchten.
Paresh
1
Bedeutet das, dass es nur einen Scheitelpunkt gibt, an dem diese Bedingung von nur 1 ausgehenden Flankenempfangsfluss erzwungen werden muss? Oder ist diese Einschränkung für alle Eckpunkte (in diesem Fall sollte meine Antwort Ihnen die einfachste Lösung bieten)? Außerdem habe ich nicht ganz verstanden, wie Sie Ihr Problem in die obige Konstruktion modelliert haben.
Paresh
1
Strömungsprobleme, die Strömungen auf Pfade beschränken, werden normalerweise als "nicht teilbare Strömungen" bezeichnet. Der nicht spaltbare Durchfluss bei minimalen Kosten ist im Allgemeinen NP-hart. Diese Version hat jedoch Anforderungen an Kanten, die Ihrer Version fehlen.
Nicholas Mancuso

Antworten:

6

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 ∞ verbunden istnx1,x2,...,xnmc1,c2,...,cmG(V,E)xivisKapazitä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 .ui,wivixi

Für jede der Klauseln erstellen wir einen entsprechenden Scheitelpunkt o iG 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 3x 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.cioiGoi1ci=(x3x4¬x5)u3,u4,w5oi

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 P istxi¬xi(vi,ui)(vi,wi)i=1,2,3,...,nmNP. und die Reduktion ist polynomisch, wir schließen daraus, dass die Entscheidungsversion des XOR-Restriktionsnetzwerkflusses NP-vollständig ist.

Strin
quelle
3

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

stst

  • 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

stO(|E|)

Paresh
quelle
Vielen Dank, aber da ich die Regel auf eine Teilmenge von Eckpunkten anwenden möchte, ist die Lösung nicht so einfach.
Patrick Schmidt
2

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.

EMS
quelle
-2

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.

aasa
quelle
3
Bitte vervollständigen Sie Ihre Antwort mit Referenzen und weiteren Details.
vonbrand
Keine Referenzen erforderlich, diese Antwort zeigt nur, dass es immer noch möglich ist, wenn P = NP ist. Das heißt, das Problem ist NP-vollständig, aber wenn P = NP ist, können wir es lösen.
Albert Hendriks