Problema di flusso multi-merce - Multi-commodity flow problem

Il problema del flusso multi-merce è un problema del flusso di rete con più merci (richieste di flusso) tra diversi nodi sorgente e sink.

Definizione

Data una rete di flusso , in cui edge ha capacità . Ci sono merci , definite da , dove ed è la fonte e il pozzo di merce , ed è la sua domanda. La variabile definisce la frazione del flusso lungo il bordo , dove nel caso in cui il flusso può essere suddiviso tra più percorsi, e in altro modo (cioè "percorso a percorso singolo"). Trova un'assegnazione di tutte le variabili di flusso che soddisfi i seguenti quattro vincoli: ${\ 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) Capacità del collegamento: la somma di tutti i flussi instradati su un collegamento non supera la sua capacità.

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

(2) Conservazione del flusso sui nodi di transito: la quantità di flusso che entra in un nodo intermedio è la stessa che esce dal nodo. ${\ 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 {quando} \ quad u \ neq s_ {i}, t_ {i}}

(3) Conservazione del flusso alla sorgente: un flusso deve uscire completamente dal suo nodo sorgente.

{\ 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) Conservazione del flusso a destinazione: un flusso deve entrare completamente nel suo nodo sink.

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

Problemi di ottimizzazione corrispondenti

Il bilanciamento del carico è il tentativo di instradare i flussi in modo tale che l'utilizzo di tutti i collegamenti sia uniforme, dove ${\ 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)} }}

Il problema può essere risolto, ad esempio, minimizzando . Una linearizzazione comune di questo problema è la minimizzazione del massimo utilizzo , dove ${\ Displaystyle \ sum _ {u, v \ in V} (U (u, v)) ^ {2}}$ ${\ displaystyle U_ {max}}$

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

Nel problema del flusso multi-merce a costo minimo , c'è un costo per l'invio di un flusso . È quindi necessario ridurre al minimo ${\ 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)}

Nel problema del flusso massimo multi-merce , la domanda di ciascuna merce non è fissa e il rendimento totale è massimizzato massimizzando la somma di tutte le richieste ${\ displaystyle \ sum _ {i = 1} ^ {k} d_ {i}}$

Relazione con altri problemi

La variante del costo minimo del problema del flusso multi-merce è una generalizzazione del problema del flusso del costo minimo (in cui vi è solo una sorgente e un pozzo . Le varianti del problema della circolazione sono generalizzazioni di tutti i problemi di flusso. Ovvero, qualsiasi problema di flusso può essere visto come un particolare problema di circolazione. ${\ displaystyle s}$ ${\ displaystyle t}$

Utilizzo

Routing e assegnazione di lunghezza d'onda (RWA) in commutazione raffica ottica di rete ottica verrebbe raggiunto tramite formule flusso multi-materie prime.

Soluzioni

Nella versione decisionale dei problemi, il problema di produrre un flusso intero che soddisfi tutte le richieste è NP-completo , anche solo per due merci e capacità unitarie (rendendo il problema fortemente NP-completo in questo caso).

Se sono consentiti flussi frazionari, il problema può essere risolto in tempo polinomiale attraverso la programmazione lineare , o attraverso schemi di approssimazione temporale completamente polinomiali (tipicamente molto più veloci) .

Risorse esterne

Articoli di Clifford Stein su questo problema: http://www.columbia.edu/~cs2035/papers/#mcf
Software che risolve il problema: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

Riferimenti

^ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Flussi di rete. Teoria, algoritmi e applicazioni . Prentice Hall.
^ S. Even e A. Itai e A. Shamir (1976). "Sulla complessità degli orari e dei problemi di flusso di più prodotti". SIAM Journal on Computing . SIAM. 5 (4): 691–703. doi : 10.1137 / 0205048 . Anche, S .; Itai, A .; Shamir, A. (1975). "Sulla complessità degli orari e sui problemi di flusso multi-merce". 16 ° simposio annuale sui fondamenti dell'informatica (SFCS 1975) . pp. 184–193. doi : 10.1109 / SFCS.1975.21 .
^ Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein (2009). "29". Introduzione agli algoritmi (3a ed.). MIT Press e McGraw – Hill. p. 862. ISBN 978-0-262-03384-8 . Manutenzione CS1: più nomi: elenco autori ( collegamento )
^ George Karakostas (2002). "Schemi di approssimazione più veloci per problemi di flusso multimateriale frazionario" . Atti del tredicesimo simposio annuale ACM-SIAM sugli algoritmi discreti . pp. 166–173 . ISBN 0-89871-513-X .

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

[ahuja_et_al_1993-1] Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Flussi di rete. Teoria, algoritmi e applicazioni . Prentice Hall.

[EIS76-2] S. Even e A. Itai e A. Shamir (1976). "Sulla complessità degli orari e dei problemi di flusso di più prodotti". SIAM Journal on Computing . SIAM. 5 (4): 691–703. doi : 10.1137 / 0205048 . Anche, S .; Itai, A .; Shamir, A. (1975). "Sulla complessità degli orari e sui problemi di flusso multi-merce". 16 ° simposio annuale sui fondamenti dell'informatica (SFCS 1975) . pp. 184–193. doi : 10.1109 / SFCS.1975.21 .

[3] Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein (2009). "29". Introduzione agli algoritmi (3a ed.). MIT Press e McGraw – Hill. p. 862. ISBN 978-0-262-03384-8 . Manutenzione CS1: più nomi: elenco autori ( collegamento )

[4] George Karakostas (2002). "Schemi di approssimazione più veloci per problemi di flusso multimateriale frazionario" . Atti del tredicesimo simposio annuale ACM-SIAM sugli algoritmi discreti . pp. 166–173 . ISBN 0-89871-513-X .

Languages

In other projects