Multicommodity Network Flows Pavel Troubil pavel@ics.muni.cz Seminář PV177, 21. dubna 2010 Pavel Troubil Multicommodity Network Flows Značení, předpoklady Síť G = (N, A) Hrana (i, j) spojuje vrcholy i, j Ohodnocení hran ­ omezení kapacity toku či toků Celočíselné, nezáporné Hrany jsou orientované uij ­ (souhrnná) kapacita hrany xij ­ (souhrnný) tok na hraně cij ­ cena jednotkového toku na hraně Pavel Troubil Multicommodity Network Flows Maximální tok Aplikace: toky v reálných sítích, plánování paralelních strojů, . . . Zdrojový vrchol s, stokový vrchol t Objektivní funkce: max v jOUT(i) xij - jIN(i) xij = v, pro i = s -v, pro i = t 0 jinak 0 xij uij Několik polynomiálních algoritmů pro řešení Pavel Troubil Multicommodity Network Flows Nejlevnější tok Rozdíly vůči maximálnímu toku Kapacita toku pevně dána Vrcholy mají dáno, kolik toku nabízejí či poptávají Hodnota toku b(i) bi > 0 zdroj < 0 stok = 0 jinak Více zdrojových a stokových vrcholů Hranám jsou krom kapcity přiřazeny ceny Hledáme nejlevnější tok Aplikace Pavel Troubil Multicommodity Network Flows Formulace problému Objektivní funkce max (i,j)A cij xij Omezení jOUT(i) xij - jIN(i) xji = b(i) 0 xij uij Pavel Troubil Multicommodity Network Flows Nejlevnější tok ­ předpoklady Celočíselné zadání Ceny hran, nabídka/poptávka, kapacita Optimální celočíselné řešení Korektní zadání Nulový součet toků ve zdrojích a stocích iN b(i) = 0 Existence přípustného toku Nezáporné ceny hran Neubírá na obecnosti Pavel Troubil Multicommodity Network Flows Residuální síť Definice Residuální síť G(x) vztažena k síti G a toku x Každá hrana (i, j) A nahrazena dvěma novými: (i, j) o ceně cij a kapacitě rij = uij - xij (j, j) o ceně cji = -cij a kapacitě rij = xij Zahrnuje pouze hrany s pozitivní kapacitou Pavel Troubil Multicommodity Network Flows Residuální síť a optimální tok Optimální residuální síť neobsahuje cyklus negativní ceny Odstranění takového cyklu by přineslo zlepšení hodnoty objektivní funkce Neobsahuje-li residuální síť negativní cyklus, pak je tok optimální Pavel Troubil Multicommodity Network Flows Cycle-canceling algoritmus V každém kroku splňuje omezení Tok není vždy optimální Algoritmus Najdi přípustný tok x while Residuální síť obsahuje cyklus negativní ceny do Najdi cyklus W negativní ceny Najdi nejmenší kapacitu hrany rmin v cyklu W Přidej tok velikosti rmin do cyklu W end while Pavel Troubil Multicommodity Network Flows Cycle-canceling ­ příklad 1 2 4 3 (2,4) (3,3) (2,2) (1,5) (1,2) b(1)=4 b(4)=-4 3 3 0 1 1 1 2 4 3 (2,1) (-3,3) (2,1) (1,4) (1,2) (-2,3) (-2,1) (-1,1) 1 2 4 3 (2,2) (3,3) (1,1) (-1,2) (-2,2) (-2,2) (-1,4) 1 2 4 3 (2,1) (-3,1) (2,1) (1,2) (-1,2) (-2,3) (-2,1) (-1,3) (3,2) Pavel Troubil Multicommodity Network Flows Potenciál vrcholu Definice Reálné číslo (i) příslušné vrcholu Konkrétní interpretace závislá na problému/algoritmu Využití Redukovaná cena hrany c ij = cij + (i) - (j) Výpočet v některých algoritmech Specifikace optimálních řešení Dokazování správnosti algoritmů Pavel Troubil Multicommodity Network Flows Potenciál vrcholu ­ příklad Nejkratší cesty z jednoho vrcholu d(i) ­ vzdálenost vrcholu i od počátečního Poteciál (i) = d(i) V optimálním řešení pro všechny hrany platí: cd ij = cij + d(i) - d(j) 0 Pro hrany optimálních cest platí cd ij = 0 Pavel Troubil Multicommodity Network Flows Successive Shortest Path Rozdíly vůči Cycle-canceling Nezachovává spojitý tok Porušuje omezení daná b(i) Nalezený tok je stále optimální Pseudotok Tok, který nesplňuje podmínky zachování hmoty e(i) = b(i) - jIN(i) xji - jOUT(i) xij Přebytek (e(i) > 0) nebo nedostatek (e(i) < 0) toku na vrcholu Pavel Troubil Multicommodity Network Flows Successive Shortest Path Pro každý vrchol udržuje hodnoty e(i), (i) Množiny E, D vrcholů s přebytky a nedostatky x 0, 0 e(i) b(i) Inicializuj množiny E, D while E = do Vyber k E, l D Najdi v G(x) nejkratší cesty ke všem vrcholům z k s použitím redukovaných cen (i) (i) - d(i) min{e(k), -e(l), min{rij : (i, j) P}} Přidej tok po cestě P Aktualizuj G(x), E, D a redukované ceny end while Pavel Troubil Multicommodity Network Flows Successive Shortest Path Udržování optimality řešení Umožňuje hledat nejkratší cesty v residuální síti Význam potenciálu v algoritmu Zachování nezáporných cen hran v grafu Residuální síť ­ přidává hrany (j, i) s cenou -cij Mají-li na nejkratší cestě hrany cenu 0, nevznikají v residuální sítí záporně ohodnocené hrany Pavel Troubil Multicommodity Network Flows Successive Shortest Path ­ příklad 1 2 4 3 (2,4) (3,3) (2,2) (1,5) (1,2)(4,0) (-4,0) (0,0) (0,0) 1 2 4 3 (0,4) (2,3) (0,2) (0,5) (1,2)(4,0) (-4,-3) (0,-2) (0,-2) 1 2 4 3 (0,4) (2,3) (0,2) (0,3) (1,2)(2,0) (-2,-3) (0,-2) (0,-2) (0,2) Pavel Troubil Multicommodity Network Flows Successive Shortest Path ­ příklad 1 2 4 3 (0,4) (1,3) (1,2) (0,3) (0,2)(2,0) (-2,-4) (0,-2) (0,-3) (0,2) 1 2 4 3 (0,2) (1,3) (1,2) (0,1) (0,2)(0,0) (0,-4) (0,-2) (0,-3) (0,4) (0,2) Pavel Troubil Multicommodity Network Flows Multicommodity flows Namísto jednoho toku několik Každý definuje zvlášt zdroje a stoky Nezávislé komodity lze rozdělit na více problémů nejmenších toků Lépe reprezentuje reálné směrovací problémy Doprava, distribuce zboží, komunikační/počítačové sítě Náročnější na řešení Pavel Troubil Multicommodity Network Flows Definice problému Značení K komodit 1, . . . , k xk ij - hodnota toku komodity k na hraně (i, j) ck ij - cena toku komodity k na hraně (i, j) Objektivní funkce 1kK ck xk Pavel Troubil Multicommodity Network Flows Definice problému Omezení (i, j) A : 1kK xk ij uij k {1, . . . , K} : Mxk = bk (i, j) A, k {1, . . . , K} : 0 xk ij uk ij Pavel Troubil Multicommodity Network Flows Předpoklady Homogenita komodit Každá komodita zabírá stejný "prostor" Nepředpokládáme zahlcení Cena hrany nezávisí na jejím zatížení (Ne)dělitelnost komodit Výsledek nemusí být celočíselný Pavel Troubil Multicommodity Network Flows Lagrangeovská relaxace Price-directive decomposition Obecně Převod omezení do objektivní funkce Porušení omezení se lineárně promítne do jejího zhoršení (a naopak) Konkrétně pro multicommodity flows Price-directive decomposition Objektivní funkce min 1kK ck xk + (i,j)A wij ( 1kK xk ij - uij ) Pavel Troubil Multicommodity Network Flows Reformulace problému Objektivní funkce min 1kK (i,j)A (ck ij + wij )xk ij - ( (i,j)A wij uij ) Omezení k {1, . . . , K} : Mxk = bk (i, j) A, k {1, . . . , K} : xij 0 Pavel Troubil Multicommodity Network Flows Nezávislé nejlevnější toky Každé omezení se týká pouze jedné komodity Postup řešení Řešení jednotlivých nejlevnějších toků Pevná hodnota Lagrangeových koeficientů w Úprava Lagrangeových koeficientů podle vzorce wq+1 ij = max {0, wq ij + q( 1kK yk ij - uij )} Koeficienty jsou vždy nezáporné Koeficient q = 1/q určuje míru změny Lagrangeových koeficientů Pavel Troubil Multicommodity Network Flows Příklad 21 3 4 5 6 (1,5) (5,-) (5,-) (1,10) (1,-) (1,-) (5,-) 2 toky: 12 ­ 10 jednotek, 34 ­ 20 jednotek w0 12 = w0 34 = 0 Pavel Troubil Multicommodity Network Flows Příklad 21 3 4 5 6 (6,5) (5,-) (5,-) (11,10) (1,-) (1,-) (5,-) w1 12 = 5, w1 34 = 10 Pavel Troubil Multicommodity Network Flows Příklad 21 3 4 5 6 (11,5) (5,-) (5,-) (1,10) (1,-) (1,-) (5,-) w2 12 = 10, w2 34 = 0 Pavel Troubil Multicommodity Network Flows Grafy Pavel Troubil Multicommodity Network Flows Grafy Pavel Troubil Multicommodity Network Flows Zhodnocení Výhody Využívá struktury problému založené na síťových tocích Výpočetně jednoduché úpravy koeficientů Nevýhody Malé kroky pomalá konvergence Konvergence Lagrangeových koeficientů nemusí znamenat konvergenci optimálních řešení podproblému k optimálnímu řešení hlavního problému Optimální řešení podproblému nemusí znamenat přípustné řešení hlavního problému Pavel Troubil Multicommodity Network Flows Resource-directive decomposition Namísto využití cen pro dekompozici alokuje kapacitu hran jednotlivým komoditám Každé komoditě alokováno rk ij uk ij z celkové kapacity hrany (i, j) Resource-directive problem z = min 1kK ck xk (i, j) A : 1kK rk ij uij k {1, . . . , K} : Mxk = bk (i, j) A, k {1, . . . , K} : 0 xk ij rk ij Pavel Troubil Multicommodity Network Flows Ekvivalence RDP a MCF Řešení RDP je řešením MCF Je-li (x, r) přípustné řešení RDP, pak x je přípustné řešení MCF se stejnou hodnotou objektivní funkce. Řešení MCF je řešením RDP Je-li x přípustné řešení MCF, pak (x, r = x) je přípustné řešení RDP se stejnou hodnotou objektivní funkce. Pavel Troubil Multicommodity Network Flows Výběr hodnot r a x Neprovádí se současně Postup výběru Nejprve fixace hodnot rk ij Na jejich základě hledání nejlevnějších toků xk ij Pavel Troubil Multicommodity Network Flows Resource-allocation problem z(r) je optimální hodnota objektivní funkce RDP pro pevně dané r Resource-allocation problem min z(r) Omezení (i, j) A : 1kK rk ij uij (i, j) A, k {1, . . . , K} : 0 rk ij uk ij Ekvivalentní resource-directive problemu Pavel Troubil Multicommodity Network Flows Dekompozice na nejlevnější toky Jsou-li alokovány zdroje pro všechny komodity, stačí vyřešit K problémů nejlevnějšího toku: min ck xk k {1, . . . , K} : Mxk = bk (i, j) A, k {1, . . . , K} : 0 xk ij rk ij Pavel Troubil Multicommodity Network Flows Hledání optima funkce z(r) Řešení multicommodity flow převedeno na problém s jednoduchou strukturou omezení, ale komplexní objektivní funkcí Funkce z(r) je konvexní a po částech lineární Možné postupy řešení Heuristika ­ výměna alokací mezi hranami Hledání lepších řešení posunem v prostoru proměnných Jak najít správný směr a délku posunu Není-li nalezené řešení přípustné, jak je najít? Pavel Troubil Multicommodity Network Flows