Problema fluxului multi-marfă - Multi-commodity flow problem

Problema fluxului de multi-marfă este un flux de rețea problemă cu mai multe produse de bază (flux cereri) între diferite noduri sursă și chiuvetă.

Definiție

Având în vedere o rețea de flux , unde marginea are capacitate . Există mărfuri , definite de , unde și este sursa și chiuveta mărfii , și este cererea sa. Variabila definește fracția fluxului de -a lungul marginii , în cazul în care fluxul poate fi împărțit între mai multe căi și altfel (adică „rutare cu o singură cale”). Găsiți o alocare a tuturor variabilelor de flux care îndeplinește următoarele patru constrângeri: ${\ displaystyle \, G (V, E)}$ ${\ displaystyle (u, v) \ în 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) \ în [0,1]}$ ${\ displaystyle \, f_ {i} (u, v) \ in \ {0,1 \}}$

(1) Capacitatea legăturii: suma tuturor fluxurilor direcționate pe o legătură nu depășește capacitatea acesteia.

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

(2) Conservarea fluxului pe nodurile de tranzit: Cantitatea de debit care intră într-un nod intermediar este aceeași care iese din nod. ${\ 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) Conservarea fluxului la sursă: un flux trebuie să părăsească nodul sursă complet.

{\ 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) Conservarea fluxului la destinație: un flux trebuie să intre complet în nodul chiuvetei sale.

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

Probleme de optimizare corespunzătoare

Echilibrarea sarcinii este încercarea de a direcționa fluxurile astfel încât utilizarea tuturor legăturilor să fie uniformă, unde ${\ displaystyle U (u, v)}$ ${\ displaystyle (u, v) \ în E}$

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

Problema poate fi rezolvată de ex. Prin minimizare . O liniarizare obișnuită a acestei probleme este minimizarea utilizării maxime , unde ${\ displaystyle \ sum _ {u, v \ in V} (U (u, v)) ^ {2}}$ ${\ displaystyle U_ {max}}$

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

În problema costului minim al fluxului multimaterial , există un cost pentru trimiterea unui flux . Apoi, trebuie să minimizați ${\ displaystyle a (u, v) \ cdot f (u, v)}$ ${\ displaystyle \, (u, v)}$

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

În problema fluxului maxim multi-marfă , cererea fiecărei mărfuri nu este fixă, iar debitul total este maximizat prin maximizarea sumei tuturor cererilor ${\ displaystyle \ sum _ {i = 1} ^ {k} d_ {i}}$

Relația cu alte probleme

Varianta costului minim al problemei fluxului cu mai multe mărfuri este o generalizare a problemei fluxului costului minim (în care există doar o singură sursă și o singură chiuvetă . Variantele problemei de circulație sunt generalizări ale tuturor problemelor de flux. Adică, orice problemă de flux poate fi privit ca o anumită problemă de circulație. ${\ displaystyle s}$ ${\ displaystyle t}$

Utilizare

De rutare și de atribuire lungime de undă (AFR) în comutare explozie optică de rețea optică ar fi abordată prin formule de flux multi-mărfuri.

Soluții

În versiunea de decizie a problemelor, problema producerii unui flux întreg care să satisfacă toate cerințele este NP-completă , chiar și pentru doar două mărfuri și capacități unitare (făcând problema puternic NP-completă în acest caz).

Dacă sunt permise fluxuri fracționate, problema poate fi rezolvată în timp polinomial prin programare liniară sau prin scheme de aproximare a timpului complet polinomiale (de obicei mult mai rapide) .

Resurse externe

Lucrări de Clifford Stein despre această problemă: http://www.columbia.edu/~cs2035/papers/#mcf
Software-ul rezolvă problema: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

Referințe

^ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Fluxuri de rețea. Teorie, algoritmi și aplicații . Prentice Hall.
^ S. Even și A. Itai și A. Shamir (1976). „Despre complexitatea orarului și a problemelor legate de fluxul multicomercial”. SIAM Journal on Computing . SIAM. 5 (4): 691-703. doi : 10.1137 / 0205048 . Chiar, S .; Itai, A .; Shamir, A. (1975). „Despre complexitatea tabelului de timp și a problemelor legate de fluxul multi-marfă”. Al 16-lea Simpozion Anual privind Bazele Informaticii (SFCS 1975) . pp. 184–193. doi : 10.1109 / SFCS.1975.21 .
^ Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein (2009). „29”. Introducere în algoritmi (ediția a 3-a). MIT Press și McGraw – Hill. p. 862. ISBN 978-0-262-03384-8 . CS1 maint: mai multe nume: lista autorilor ( link )
^ George Karakostas (2002). „Scheme de aproximare mai rapide pentru problemele de flux fracțional multicomercial” . Lucrările celui de-al treisprezecelea simpozion anual ACM-SIAM pe algoritmi discreți . pp. 166–173 . ISBN 0-89871-513-X .

Adăugați: Jean-Patrice Netter, Flow Augmenting Meshings: un tip primar de abordare a debitului maxim maxim într-o rețea muti-marfă, disertație doctorat Universitatea Johns Hopkins, 1971

[ahuja_et_al_1993-1] Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Fluxuri de rețea. Teorie, algoritmi și aplicații . Prentice Hall.

[EIS76-2] S. Even și A. Itai și A. Shamir (1976). „Despre complexitatea orarului și a problemelor legate de fluxul multicomercial”. SIAM Journal on Computing . SIAM. 5 (4): 691-703. doi : 10.1137 / 0205048 . Chiar, S .; Itai, A .; Shamir, A. (1975). „Despre complexitatea tabelului de timp și a problemelor legate de fluxul multi-marfă”. Al 16-lea Simpozion Anual privind Bazele Informaticii (SFCS 1975) . pp. 184–193. doi : 10.1109 / SFCS.1975.21 .

[3] Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest și Clifford Stein (2009). „29”. Introducere în algoritmi (ediția a 3-a). MIT Press și McGraw – Hill. p. 862. ISBN 978-0-262-03384-8 . CS1 maint: mai multe nume: lista autorilor ( link )

[4] George Karakostas (2002). „Scheme de aproximare mai rapide pentru problemele de flux fracțional multicomercial” . Lucrările celui de-al treisprezecelea simpozion anual ACM-SIAM pe algoritmi discreți . pp. 166–173 . ISBN 0-89871-513-X .

Languages

In other projects