Problema de fluxo de multi-commodity - Multi-commodity flow problem

O problema de fluxo de múltiplas mercadorias é um problema de fluxo de rede com múltiplas mercadorias (demandas de fluxo) entre diferentes nós de origem e destino.

Definição

Dada uma rede de fluxo , onde a borda tem capacidade . Existem commodities , definidas por , onde e é a fonte e sumidouro de commodities , e é sua demanda. A variável define a fração do fluxo ao longo da borda , onde no caso o fluxo pode ser dividido entre vários caminhos, e de outra forma (ou seja, "roteamento de caminho único"). Encontre uma atribuição de todas as variáveis de fluxo que satisfaça as quatro restrições a seguir: ${\ 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) Capacidade do link: A soma de todos os fluxos roteados por um link não excede sua capacidade.

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

(2) Conservação de fluxo em nós de trânsito: A quantidade de um fluxo que entra em um nó intermediário é a mesma que sai do nó. ${\ 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) Conservação de fluxo na fonte: Um fluxo deve sair completamente de seu nó de origem.

{\ 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) Conservação de fluxo no destino: Um fluxo deve entrar completamente em seu nó sumidouro.

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

Problemas de otimização correspondentes

O balanceamento de carga é a tentativa de rotear os fluxos de forma que a utilização de todos os links seja uniforme, onde ${\ 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)} }}

O problema pode ser resolvido, por exemplo, minimizando . Uma linearização comum deste problema é a minimização da utilização máxima , onde ${\ 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)}

No problema de fluxo de commodities de custo mínimo , há um custo para enviar um fluxo . Você então precisa minimizar ${\ 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)}

No problema de fluxo de multi-commodity máximo , a demanda de cada mercadoria não é fixa e o rendimento total é maximizado ao maximizar a soma de todas as demandas ${\ displaystyle \ sum _ {i = 1} ^ {k} d_ {i}}$

Relação com outros problemas

A variante de custo mínimo do problema de fluxo de múltiplas mercadorias é uma generalização do problema de fluxo de custo mínimo (em que há apenas uma fonte e um sumidouro . As variantes do problema de circulação são generalizações de todos os problemas de fluxo. Ou seja, qualquer problema de fluxo pode ser visto como um problema particular de circulação. ${\ displaystyle s}$ ${\ displaystyle t}$

Uso

O roteamento e a atribuição de comprimento de onda (RWA) na comutação de rajada óptica da rede óptica seriam abordados por meio de fórmulas de fluxo de commodities múltiplas.

Soluções

Na versão de decisão dos problemas, o problema de produzir um fluxo inteiro satisfazendo todas as demandas é NP-completo , mesmo para apenas duas mercadorias e capacidades unitárias (tornando o problema fortemente NP-completo neste caso).

Se fluxos fracionários são permitidos, o problema pode ser resolvido em tempo polinomial por meio de programação linear ou por meio de esquemas de aproximação de tempo totalmente polinomial (normalmente muito mais rápido) .

Fontes externas

Artigos de Clifford Stein sobre este problema: http://www.columbia.edu/~cs2035/papers/#mcf
Software resolvendo o problema: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

Referências

^ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Fluxos de rede. Teoria, algoritmos e aplicações . Prentice Hall.
^ S. Even e A. Itai e A. Shamir (1976). "Sobre a complexidade dos problemas de fluxo de horários e multicommodidades". SIAM Journal on Computing . SIAM. 5 (4): 691–703. doi : 10.1137 / 0205048 . Even, S .; Itai, A .; Shamir, A. (1975). “Sobre a complexidade do cronograma e os problemas de fluxo de commodities”. 16º Simpósio Anual sobre Fundamentos de Ciência da Computação (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". Introdução aos Algoritmos (3ª ed.). MIT Press e McGraw-Hill. p. 862. ISBN 978-0-262-03384-8 . CS1 maint: vários nomes: lista de autores ( link )
^ George Karakostas (2002). "Esquemas de aproximação mais rápidos para problemas de fluxo fracionário de multicommodidades" . Anais do décimo terceiro simpósio anual ACM-SIAM sobre algoritmos discretos . pp. 166–173 . ISBN 0-89871-513-X .

Adicionar: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a muti-commodity network, dissertação de doutorado Johns Hopkins University, 1971

[ahuja_et_al_1993-1] Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Fluxos de rede. Teoria, algoritmos e aplicações . Prentice Hall.

[EIS76-2] S. Even e A. Itai e A. Shamir (1976). "Sobre a complexidade dos problemas de fluxo de horários e multicommodidades". SIAM Journal on Computing . SIAM. 5 (4): 691–703. doi : 10.1137 / 0205048 . Even, S .; Itai, A .; Shamir, A. (1975). “Sobre a complexidade do cronograma e os problemas de fluxo de commodities”. 16º Simpósio Anual sobre Fundamentos de Ciência da Computação (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". Introdução aos Algoritmos (3ª ed.). MIT Press e McGraw-Hill. p. 862. ISBN 978-0-262-03384-8 . CS1 maint: vários nomes: lista de autores ( link )

[4] George Karakostas (2002). "Esquemas de aproximação mais rápidos para problemas de fluxo fracionário de multicommodidades" . Anais do décimo terceiro simpósio anual ACM-SIAM sobre algoritmos discretos . pp. 166–173 . ISBN 0-89871-513-X .

Languages

In other projects