Flomvareproblem - Multi-commodity flow problem

Den flervareflyt problem er et nettstrømnings problem med flere varer (strømningsbehov) mellom forskjellige kilde- og vask noder.

Definisjon

Gitt et strømningsnettverk , der edge har kapasitet . Det er varer , definert av , hvor og er kilden og vasken til varen , og er dens krav. Variabelen definerer brøkdel av strømning langs kant , der i tilfelle flyt kan deles mellom flere baner, og ellers (dvs. "enkelveirute"). Finn en oppgave av alle flytvariabler som tilfredsstiller følgende fire begrensninger: ${\ displaystyle \, G (V, E)}$ ${\ displaystyle (u, v) \ i E}$ ${\ displaystyle \, c (u, v)}$ ${\ displaystyle \, k}$ ${\ displaystyle K_ {1}, K_ {2}, \ prikker, 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) \ i [0,1]}$ ${\ displaystyle \, f_ {i} (u, v) \ in \ {0,1 \}}$

(1) Koblingskapasitet: Summen av alle strømmer som er rutet over en lenke, overstiger ikke kapasiteten.

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

(2) Strømningsbevaring på transittnoder: Mengden av en strøm som går inn i en mellomnode er den samme som kommer ut av noden. ${\ displaystyle u}$

{\ displaystyle \ forall i \ i K: \, \ sum _ {w \ in V} f_ {i} (u, w) - \ sum _ {w \ in V} f_ {i} (w, u) = 0 \ quad \ mathrm {når} \ quad u \ neq s_ {i}, t_ {i}}

(3) Strømningsbevaring ved kilden: En strøm må gå ut av kildekoden.

{\ 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) Strømningskonservering på destinasjonen: En strømning må komme helt inn i sin vaskeknute.

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

Tilsvarende optimaliseringsproblemer

Lastbalansering er forsøket på å rute strømmer slik at bruken av alle koblinger er jevn, hvor ${\ displaystyle U (u, v)}$ ${\ displaystyle (u, v) \ i E}$

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

Problemet kan løses f.eks. Ved å minimere . En vanlig linearisering av dette problemet er minimering av maksimal utnyttelse , hvor ${\ displaystyle \ sum _ {u, v \ in V} (U (u, v)) ^ {2}}$ ${\ displaystyle U_ {max}}$

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

I det minimale kostnadsproblemet med flere varer , er det en kostnad å sende en strøm videre . Du må da minimere ${\ displaystyle a (u, v) \ cdot f (u, v)}$ ${\ displaystyle \, (u, v)}$

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

I det maksimale strømvareproblemet med flere varer er ikke behovet for hver vare løst, og den totale gjennomstrømningen maksimeres ved å maksimere summen av alle krav ${\ displaystyle \ sum _ {i = 1} ^ {k} d_ {i}}$

Forhold til andre problemer

Minimumskostnadsvarianten av strømvareproblemet med flere varer er en generalisering av minimumskostnadsproblemet (der det bare er en kilde og en vask . Varianter av sirkulasjonsproblemet er generaliseringer av alle strømningsproblemer. kan sees på som et spesielt sirkulasjonsproblem. ${\ displaystyle s}$ ${\ displaystyle t}$

Bruk

Ruting og bølgelengdetildeling (RWA) i optisk burst-bytte av optisk nettverk vil bli kontaktet via formler for flere varer.

Løsninger

I beslutningsversjonen av problemer er problemet med å produsere et heltallstrøm som tilfredsstiller alle krav NP-komplett , selv for bare to varer og enhetskapasiteter (noe som gjør problemet sterkt NP-komplett i dette tilfellet).

Hvis brøkdelstrømmer er tillatt, kan problemet løses i polynomial tid gjennom lineær programmering , eller gjennom (vanligvis mye raskere) tidsplaner for tilnærming av fullpolynom .

Eksterne ressurser

Papirer av Clifford Stein om dette problemet: http://www.columbia.edu/~cs2035/papers/#mcf
Programvare som løser problemet: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

Referanser

^ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Nettverksflyter. Teori, algoritmer og applikasjoner . Prentice Hall.
^ S. Even og A. Itai og A. Shamir (1976). "Om kompleksiteten av rutetabeller og flerspredningsproblemer". SIAM Journal on Computing . SIAM. 5 (4): 691–703. doi : 10.1137 / 0205048 . Even, S .; Itai, A .; Shamir, A. (1975). "Om kompleksiteten i rutetabellene for problemer med flere varer". 16. årlige symposium om grunnlag for datalogi (SFCS 1975) . s. 184–193. doi : 10.1109 / SFCS.1975.21 .
^ Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein (2009). "29". Introduksjon til algoritmer (3. utgave). MIT Press og McGraw – Hill. s. 862. ISBN 978-0-262-03384-8 . CS1 maint: flere navn: forfatterliste ( lenke )
^ George Karakostas (2002). "Raskere tilnærmingsskjemaer for brøkdelte flerspredningsproblemer" . Forløp av det trettende årlige ACM-SIAM-symposiet om diskrete algoritmer . s. 166–173 . ISBN 0-89871-513-X .

Legg til: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a muti-commodity network, Ph.D. avhandling Johns Hopkins University, 1971

[ahuja_et_al_1993-1] Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Nettverksflyter. Teori, algoritmer og applikasjoner . Prentice Hall.

[EIS76-2] S. Even og A. Itai og A. Shamir (1976). "Om kompleksiteten av rutetabeller og flerspredningsproblemer". SIAM Journal on Computing . SIAM. 5 (4): 691–703. doi : 10.1137 / 0205048 . Even, S .; Itai, A .; Shamir, A. (1975). "Om kompleksiteten i rutetabellene for problemer med flere varer". 16. årlige symposium om grunnlag for datalogi (SFCS 1975) . s. 184–193. doi : 10.1109 / SFCS.1975.21 .

[3] Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein (2009). "29". Introduksjon til algoritmer (3. utgave). MIT Press og McGraw – Hill. s. 862. ISBN 978-0-262-03384-8 . CS1 maint: flere navn: forfatterliste ( lenke )

[4] George Karakostas (2002). "Raskere tilnærmingsskjemaer for brøkdelte flerspredningsproblemer" . Forløp av det trettende årlige ACM-SIAM-symposiet om diskrete algoritmer . s. 166–173 . ISBN 0-89871-513-X .

Languages

In other projects