Probleem met de stroom van meerdere goederen - Multi-commodity flow problem

Het multi-commodity flow-probleem is een netwerkstroomprobleem met meerdere commodities (flow-eisen) tussen verschillende source- en sink-knooppunten.

Definitie

Gegeven een stroomnetwerk , waar de rand capaciteit heeft . Er zijn commodities , bepaald door waar en is de bron en zinken van de grondstoffenprijzen , en is de vraag. De variabele definieert de fractie van de stroming langs de rand , waar in het geval de stroming kan worden opgesplitst over meerdere paden, en anders (dwz "single path routing"). Zoek een toewijzing van alle stroomvariabelen die aan de volgende vier beperkingen voldoen: ${\ displaystyle \, G (V, E)}$ ${\ displaystyle (u, v) \ in E}$ ${\ displaystyle \, c (u, v)}$ ${\ displaystyle \, k}$ ${\ displaystyle K_ {1}, K_ {2}, \ dots, K_ {k}}$ ${\ displaystyle \, K_ {i} = (s_ {i}, t_ {i}, d_ {i})}$ ${\ displaystyle \, s_ {i}}$ ${\ displaystyle \, t_ {i}}$ ${\ displaystyle \, i}$ ${\ displaystyle \, d_ {i}}$ ${\ displaystyle \, f_ {i} (u, v)}$ ${\ displaystyle \, i}$ ${\ displaystyle \, (u, v)}$ ${\ displaystyle \, F_ {i} (u, v) \ in [0,1]}$ ${\ displaystyle \, F_ {i} (u, v) \ in \ {0,1 \}}$

(1) Linkcapaciteit: de som van alle stromen die via een link worden gerouteerd, overschrijdt de capaciteit niet.

{\ Displaystyle \ forall (u, v) \ in E: \, \ sum _ {i = 1} ^ {k} F_ {i} (u, v) \ cdot d_ {i} \ eq c (u, v )}

(2) Stroombehoud op doorvoerknooppunten: de hoeveelheid stroom die een tussenliggend knooppunt binnenkomt, is dezelfde als die het knooppunt verlaat. ${\ displaystyle u}$

{\ Displaystyle \ forall i \ in K: \, \ sum _ {w \ in V} F_ {i} (u, w) - \ sum _ {w \ in V} F_ {i} (w, u) = 0 \ quad \ mathrm {when} \ quad u \ neq s_ {i}, t_ {i}}

(3) Stroombehoud aan de bron: een stroom moet zijn bronknooppunt volledig verlaten.

{\ Displaystyle \ forall i \ in K: \, \ sum _ {w \ in V} F_ {i} (s_ {i}, w) - \ sum _ {w \ in V} F_ {i} (w, s_ {i}) = 1}

(4) Stroombehoud op de bestemming: een stroom moet zijn sink-knoop volledig binnengaan.

{\ Displaystyle \ forall i \ in K: \, \ sum _ {w \ in V} F_ {i} (w, t_ {i}) - \ sum _ {w \ in V} F_ {i} (t_ { i}, w) = 1}

Bijbehorende optimalisatieproblemen

Load balancing is de poging om stromen zo te routeren dat het gebruik van alle links gelijk is, waar ${\ displaystyle U (u, v)}$ ${\ displaystyle (u, v) \ in E}$

{\ displaystyle U (u, v) = {\ frac {\ sum _ {i = 1} ^ {k} F_ {i} (u, v) \ cdot d_ {i}} {c (u, v)} }}

Het probleem kan bijvoorbeeld worden opgelost door te minimaliseren . Een veel voorkomende linearisering van dit probleem is het minimaliseren van de maximale benutting , waarbij ${\ Displaystyle \ som _ {u, v \ in V} (U (u, v)) ^ {2}}$ ${\ displaystyle U_ {max}}$

{\ Displaystyle \ forall (u, v) \ in E: \, U_ {max} \ geq U (u, v)}

Bij het probleem met de minimale kosten voor multi-commodity-stroom zijn er kosten voor het doorsturen van een stroom . U moet dan minimaliseren ${\ displaystyle a (u, v) \ cdot f (u, v)}$ ${\ displaystyle \, (u, v)}$

{\ Displaystyle \ som _ {(u, v) \ in E} \ left (a (u, v) \ som _ {i = 1} ^ {k} F_ {i} (u, v) \ right)}

In het probleem met de maximale stroom van meerdere goederen is de vraag van elk product niet vast en wordt de totale doorvoer gemaximaliseerd door de som van alle eisen te maximaliseren ${\ displaystyle \ sum _ {i = 1} ^ {k} d_ {i}}$

Verhouding tot andere problemen

De minimale kostenvariant van het multi-commodity-stroomprobleem is een generalisatie van het minimale-kostenstroomprobleem (waarbij er slechts één bron en één put is . Varianten van het circulatieprobleem zijn generalisaties van alle stroomproblemen. Dat wil zeggen, elk stroomprobleem) kan worden gezien als een bepaald circulatieprobleem. ${\ displaystyle s}$ ${\ displaystyle t}$

Gebruik

Routing en golflengtetoekenning (RWA) in optische burst-schakeling van optisch netwerk zou worden benaderd via multi-commodity flow-formules.

Oplossingen

In de beslissingsversie van problemen is het probleem van het produceren van een integer-stroom die aan alle eisen voldoet NP-compleet , zelfs voor slechts twee artikelen en eenheidscapaciteiten (waardoor het probleem in dit geval sterk NP-compleet is).

Als fractionele stromen zijn toegestaan, kan het probleem worden opgelost in polynoomtijd door middel van lineaire programmering , of door (meestal veel snellere) volledig polynoomtijdbenaderingsschema's .

Externe bronnen

Papers van Clifford Stein over dit probleem: http://www.columbia.edu/~cs2035/papers/#mcf
Software die het probleem oplost: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

Referenties

^ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Netwerkstromen. Theorie, algoritmen en toepassingen . Prentice Hall.
^ S. Even en A. Itai en A. Shamir (1976). ‘Over de complexiteit van problemen met de dienstregeling en de stroom van meerdere goederen’. SIAM Journal on Computing . SIAM. 5 (4): 691-703. doi : 10.1137 / 0205048 . Zelfs, S .; Itai, A .; Shamir, A. (1975). "Over de complexiteit van tijdschema en multi-commodity flow-problemen". 16e jaarlijkse symposium over de grondslagen van de informatica (SFCS 1975) . blz. 184-193. doi : 10.1109 / SFCS.1975.21 .
^ Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest en Clifford Stein (2009). "29". Inleiding tot algoritmen (3e ed.). MIT Press en McGraw – Hill. p. 862. ISBN 978-0-262-03384-8 . CS1 maint: meerdere namen: auteurslijst ( link )
^ George Karakostas (2002). "Snellere benaderingsschema's voor fractionele stroomproblemen met meerdere grondstoffen" . Proceedings van het dertiende jaarlijkse ACM-SIAM-symposium over discrete algoritmen . blz. 166-173 . ISBN 0-89871-513-X .

Toevoegen: Jean-Patrice Netter, Flow Augmenting Meshings: een primair type benadering van de maximale integer-stroom in een muti-commodity-netwerk, Ph.D dissertatie Johns Hopkins University, 1971

[ahuja_et_al_1993-1] Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Netwerkstromen. Theorie, algoritmen en toepassingen . Prentice Hall.

[EIS76-2] S. Even en A. Itai en A. Shamir (1976). ‘Over de complexiteit van problemen met de dienstregeling en de stroom van meerdere goederen’. SIAM Journal on Computing . SIAM. 5 (4): 691-703. doi : 10.1137 / 0205048 . Zelfs, S .; Itai, A .; Shamir, A. (1975). "Over de complexiteit van tijdschema en multi-commodity flow-problemen". 16e jaarlijkse symposium over de grondslagen van de informatica (SFCS 1975) . blz. 184-193. doi : 10.1109 / SFCS.1975.21 .

[3] Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest en Clifford Stein (2009). "29". Inleiding tot algoritmen (3e ed.). MIT Press en McGraw – Hill. p. 862. ISBN 978-0-262-03384-8 . CS1 maint: meerdere namen: auteurslijst ( link )

[4] George Karakostas (2002). "Snellere benaderingsschema's voor fractionele stroomproblemen met meerdere grondstoffen" . Proceedings van het dertiende jaarlijkse ACM-SIAM-symposium over discrete algoritmen . blz. 166-173 . ISBN 0-89871-513-X .

Languages

In other projects