Problema de flujo de múltiples productos

Problema de flujo de red (matemáticas)

El problema del flujo de múltiples productos es un problema de flujo de red con múltiples productos (demanda de flujo) entre diferentes nodos fuente y sumidero.

Definición

Dada una red de flujo , donde el borde tiene capacidad . Hay mercancías , definidas por , donde y es la fuente y el sumidero de la mercancía , y es su demanda. La variable define la fracción de flujo a lo largo del borde , en caso de que el flujo se pueda dividir entre múltiples rutas, y en caso contrario (es decir, "enrutamiento de ruta única"). Encuentre una asignación de todas las variables de flujo que satisfaga las siguientes cuatro restricciones: ${\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) Capacidad del enlace: la suma de todos los flujos enrutados a través de un enlace no excede su capacidad.

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

(2) Conservación del flujo en los nodos de tránsito: la cantidad de flujo que ingresa a un nodo intermedio es la misma que sale del nodo. ${\displaystyle u}$

${\displaystyle \forall i\in \{1,\ldots ,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) Conservación del flujo en la fuente: un flujo debe salir completamente de su nodo fuente.

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{w\in V}f_{i}(s_{i},w)-\sum _{w\in V}f_{i}(w,s_{i})=1}$

(4) Conservación del flujo en el destino: un flujo debe ingresar completamente a su nodo sumidero.

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

Problemas de optimización correspondientes.

El equilibrio de carga es el intento de enrutar los flujos de manera que la utilización de todos los enlaces sea uniforme, donde ${\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)}}}$

El problema se puede resolver, por ejemplo, minimizando . Una linealización común de este problema es la minimización de la utilización máxima , donde ${\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)}$

En el problema de flujo de múltiples productos de costo mínimo , existe un costo por enviar un flujo . Entonces necesitas 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)\cdot d_{i}\right)}$

En el problema del flujo máximo de múltiples productos , la demanda de cada producto no es fija y el rendimiento total se maximiza maximizando la suma de todas las demandas. ${\displaystyle \sum _{i=1}^{k}d_{i}}$

Relación con otros problemas

La variante de costo mínimo del problema del flujo de múltiples productos es una generalización del problema del flujo de costo mínimo (en el que hay simplemente una fuente y un sumidero ). Las variantes del problema de circulación son generalizaciones de todos los problemas de flujo. Es decir, cualquier problema de flujo puede verse como un problema de circulación particular. ^[1] ${\displaystyle s}$ ${\displaystyle t}$

Uso

El enrutamiento y la asignación de longitud de onda (RWA) en la conmutación de ráfagas ópticas de la red óptica se abordarían mediante fórmulas de flujo de múltiples productos.

La asignación de registros se puede modelar como un problema de flujo de múltiples productos de costo mínimo entero: los valores producidos por las instrucciones son nodos fuente, los valores consumidos por las instrucciones son nodos receptores y los registros, así como las ranuras de la pila, son bordes. ^[2]

Soluciones

En la versión de decisión de los problemas, el problema de producir un flujo entero que satisfaga todas las demandas es NP-completo , ^[3] incluso para sólo dos bienes y capacidades unitarias (lo que hace que el problema sea fuertemente NP-completo en este caso).

Si se permiten flujos fraccionarios, el problema se puede resolver en tiempo polinomial mediante programación lineal , ^[4] o mediante esquemas de aproximación de tiempo totalmente polinomial (normalmente mucho más rápidos) . ^[5]

Aplicaciones

El flujo de múltiples productos se aplica en el enrutamiento superpuesto en la entrega de contenido. ^[6]

Recursos externos

• Artículos de Clifford Stein sobre este problema: http://www.columbia.edu/~cs2035/papers/#mcf
• Software que resuelve el problema: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

Referencias

1. Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Flujos de red. Teoría, algoritmos y aplicaciones . Prentice Hall.
2. Koes, David Ryan (2009). "Hacia un compilador con más principios: revisión de la asignación de registros y la selección de instrucciones" (Doctor). Universidad de Carnegie mellon. S2CID  26416771.
3. S. Even y A. Itai y A. Shamir (1976). "Sobre la complejidad de los problemas de horarios y flujos de múltiples productos". Revista SIAM de Computación . 5 (4). SIAM: 691–703. doi :10.1137/0205048.Incluso, S.; Itaí, A.; Shamir, A. (1975). "Sobre la complejidad de los horarios y los problemas de flujo de múltiples productos". 16º Simposio Anual sobre Fundamentos de la Informática (SFCS 1975) . págs. 184-193. doi :10.1109/SFCS.1975.21. S2CID  18449466.
4. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2009). "29". Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. pag. 862.ISBN​ 978-0-262-03384-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
5. George Karakostas (2002). "Esquemas de aproximación más rápidos para problemas de flujo fraccionario de múltiples productos". Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos . págs. 166-173. ISBN 0-89871-513-X.
6. Nuggets algorítmicos en la entrega de contenido sigcomm.org

Agregar: Jean-Patrice Netter, Mallas de aumento de flujo: un tipo primario de enfoque para el flujo entero máximo en una red de múltiples productos, tesis doctoral Universidad Johns Hopkins, 1971