Problém multikomoditního toku - Multi-commodity flow problem

The problém multikomoditního toku je tok sítě problém s více komoditami (požadavky na tok) mezi různými zdrojovými a potápěčskými uzly.

Definice

Vzhledem k toku sítě ${displaystyle, G (V, E)}$ , kde hrana ${displaystyle (u, v) v E}$ má kapacitu ${displaystyle, c (u, v)}$ . Existují ${displaystyle, k}$ komodity ${displaystyle K_ {1}, K_ {2}, tečky, K_ {k}}$ , definován ${displaystyle, K_ {i} = (s_ {i}, t_ {i}, d_ {i})}$ , kde ${displaystyle, s_ {i}}$ a ${displaystyle, t_ {i}}$ je zdroj a dřez zboží ${displaystyle, i}$ , a ${displaystyle, d_ {i}}$ je jeho poptávka. Proměnná ${displaystyle, f_ {i} (u, v)}$ definuje zlomek toku ${displaystyle, i}$ podél okraje ${displaystyle, (u, v)}$ , kde ${displaystyle, f_ {i} (u, v) v [0,1]}$ v případě, že lze tok rozdělit mezi více cest, a ${displaystyle, f_ {i} (u, v) v {0,1}}$ jinak (tj. „směrování jedné cesty“). Najděte přiřazení všech proměnných toku, které splňuje následující čtyři omezení:

(1) Link kapacita: Součet všech toků směrovaných přes odkaz nepřesahuje jeho kapacitu.

{displaystyle forall (u, v) v E:, součet _ {i = 1} ^ {k} f_ {i} (u, v) cdot d_ {i} leq c (u, v)}

(2) Zachování toku na tranzitních uzlech: Množství toku vstupujícího do mezilehlého uzlu ${displaystyle u}$ je stejný, který opouští uzel.

{displaystyle forall iin K:, sum _ {win V} f_ {i} (u, w) -sum _ {win V} f_ {i} (w, u) = 0quad mathrm {when} quad ueq s_ {i} , t_ {i}}

(3) Zachování toku u zdroje: Tok musí zcela opustit svůj zdrojový uzel.

{displaystyle forall iin K:, sum _ {win V} f_ {i} (s_ {i}, w) -sum _ {win V} f_ {i} (w, s_ {i}) = 1}

4) Zachování toku v místě určení: Tok musí zcela vstoupit do uzlu jímky.

{displaystyle forall iin K:, sum _ {win V} f_ {i} (w, t_ {i}) - sum _ {win V} f_ {i} (t_ {i}, w) = 1}

Odpovídající optimalizační problémy

Vyrovnávání zatížení je pokus o směrování toků tak, aby využití ${displaystyle U (u, v)}$ všech odkazů ${displaystyle (u, v) v E}$ je dokonce, kde

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

Problém lze vyřešit např. minimalizací ${displaystyle sum _ {u, vin V} (U (u, v)) ^ {2}}$ . Běžnou linearizací tohoto problému je minimalizace maximálního využití ${displaystyle U_ {max}}$ , kde

{displaystyle forall (u, v) v E:, U_ {max} geq U (u, v)}

V problém multikomoditního toku s minimálními náklady, je to cena ${displaystyle a (u, v) cdot f (u, v)}$ za odeslání toku ${displaystyle, (u, v)}$ . Pak musíte minimalizovat

{displaystyle sum _ {(u, v) in E} left (a (u, v) sum _ {i = 1} ^ {k} f_ {i} (u, v) ight)}

V problém s multikomoditním tokem, poptávka každé komodity není pevná a celková propustnost je maximalizována maximalizací součtu všech požadavků ${displaystyle sum _ {i = 1} ^ {k} d_ {i}}$

Vztah k dalším problémům

Varianta minimálních nákladů problému multikomoditního toku je zobecněním problém s minimálními náklady (ve kterém je pouze jeden zdroj ${displaystyle s}$ a jedno umyvadlo ${displaystyle t}$ . Varianty problém oběhu jsou zobecnění všech problémů s tokem. To znamená, že jakýkoli problém s tokem lze považovat za konkrétní problém s cirkulací.^[1]

Používání

Směrování a přiřazení vlnové délky (RWA) v přepínání optických dávek z Optická síť by se přistupovalo prostřednictvím multikomoditních vzorců toku.

Řešení

V rozhodovací verzi problémů je problém výroby celočíselného toku splňujícího všechny požadavky NP-kompletní,^[2] dokonce jen za dvě komodity a jednotkové kapacity (což dělá problém silně NP-kompletní v tomto případě).

Pokud jsou povoleny dílčí toky, lze problém vyřešit v polynomiálním čase až lineární programování,^[3] nebo skrz (obvykle mnohem rychleji) plně polynomiální schémata přibližování času.^[4]

Externí zdroje

Články Clifforda Steina o tomto problému: http://www.columbia.edu/~cs2035/papers/#mcf
Software řešící problém: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

Reference

^ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Toky sítě. Teorie, algoritmy a aplikace. Prentice Hall.
^ S. Even a A. Itai a A. Shamir (1976). "O složitosti časového plánu a problémech toku více akomodit". SIAM Journal on Computing. SIAM. 5 (4): 691–703. doi:10.1137/0205048.Dokonce, S .; Itai, A .; Shamir, A. (1975). "O složitosti časového plánu a problémech s multikomoditním tokem". 16. výroční sympozium o základech informatiky (SFCS 1975). 184–193. doi:10.1109 / SFCS.1975.21.
^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein (2009). "29". Úvod do algoritmů (3. vyd.). MIT Press a McGraw – Hill. str. 862. ISBN 978-0-262-03384-8.CS1 maint: více jmen: seznam autorů (odkaz)
^ George Karakostas (2002). „Rychlejší aproximační schémata pro problémy s tokem dílčích multikomunitních toků“. Sborník z třináctého ročníku sympozia ACM-SIAM o diskrétních algoritmech. str.166–173. ISBN 0-89871-513-X.

Doplnit: Jean-Patrice Netter, Flow Augmenting Meshings: prvotní typ přístupu k maximálnímu celočíselnému toku v multikomoditní síti, doktorská disertační práce Johns Hopkins University, 1971

[ahuja_et_al_1993-1] Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Toky sítě. Teorie, algoritmy a aplikace. Prentice Hall.

[EIS76-2] S. Even a A. Itai a A. Shamir (1976). "O složitosti časového plánu a problémech toku více akomodit". SIAM Journal on Computing. SIAM. 5 (4): 691–703. doi:10.1137/0205048.Dokonce, S .; Itai, A .; Shamir, A. (1975). "O složitosti časového plánu a problémech s multikomoditním tokem". 16. výroční sympozium o základech informatiky (SFCS 1975). 184–193. doi:10.1109 / SFCS.1975.21.

[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein (2009). "29". Úvod do algoritmů (3. vyd.). MIT Press a McGraw – Hill. str. 862. ISBN 978-0-262-03384-8.CS1 maint: více jmen: seznam autorů (odkaz)

[4] George Karakostas (2002). „Rychlejší aproximační schémata pro problémy s tokem dílčích multikomunitních toků“. Sborník z třináctého ročníku sympozia ACM-SIAM o diskrétních algoritmech. str.166–173. ISBN 0-89871-513-X.

[1]

[2]

[3]

[4]