Problema de flujo de múltiples mercancías

El problema del flujo de múltiples productos básicos es un problema de flujo en red con múltiples productos básicos (demandas de flujo) entre diferentes nodos de origen y destino.

Dada una red de flujo${\displaystyle \,G(V,E)}$donde borde${\displaystyle (u,v)\in E}$tiene capacidad${\displaystyle \,c(u,v)}$. Hay${\displaystyle \,k}$productos básicos${\displaystyle K_{1},K_{2},\dots ,K_{k}}$, definido por${\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})}$, dónde${\displaystyle \,s_{i}}$y${\displaystyle \,t_{i}}$es la fuente y el sumidero de mercancías${\displaystyle \,i}$, y${\displaystyle \,d_{i}}$es su demanda. La variable${\displaystyle \,f_{i}(u,v)}$define la fracción de flujo${\displaystyle \,i}$a lo largo del borde${\displaystyle \,(u,v)}$, dónde${\displaystyle \,f_{i}(u,v)\in [0,1]}$en caso de que el flujo pueda dividirse entre múltiples rutas, y${\displaystyle \,f_{i}(u,v)\in \{0,1\}}$de lo contrario (es decir, "enrutamiento de ruta única"). Encuentre una asignación de todas las variables de flujo que satisfaga las siguientes cuatro restricciones:

(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 un flujo que ingresa a un nodo intermedio${\displaystyle u}$es lo mismo que sale del nodo.

${\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {cuando} \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 _{(s_{i},w)\in E}f_{i}(s_{i},w)-\sum _{(w,s_{i})\in E}f_{i}(w,s_{i})=1}$

(4) Conservación del flujo en el destino: Un flujo debe entrar completamente en su nodo sumidero.

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

El balanceo de carga es el intento de enrutar flujos de tal manera que la utilización${\displaystyle U(u,v)}$de todos los enlaces${\displaystyle (u,v)\in E}$es incluso, donde

${\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${\displaystyle \sum _{u,v\in V}(U(u,v))^{2}}$. Una linealización común de este problema es la minimización de la utilización máxima.${\displaystyle U_{max}}$, dónde

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

En el problema de flujo de múltiples productos básicos de costo mínimo , existe un costo${\displaystyle a(u,v)\cdot f(u,v)}$para enviar un flujo en${\displaystyle \,(u,v)}$. Luego debes minimizar

${\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 básicos , 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}}$

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

El enrutamiento y la asignación de longitud de onda (RWA) en la conmutación de ráfagas ópticas de una red óptica se abordarían mediante fórmulas de flujo multicommodity, si la red está equipada con conversión de longitud de onda en cada nodo.

La asignación de registros puede modelarse como un problema de flujo de múltiples productos básicos con costo mínimo entero: los valores producidos por las instrucciones son nodos fuente, los valores consumidos por las instrucciones son nodos sumidero y los registros, así como las ranuras de la pila, son aristas. ^{[ 2 ]}

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 solo dos productos y capacidades unitarias (lo que hace que el problema sea fuertemente NP-completo en este caso).

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

El flujo multicommodity se aplica en el enrutamiento superpuesto en la entrega de contenido. ^{[ 6 ]}

• 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/

Añadir: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a multi-commodity network, tesis doctoral, Universidad Johns Hopkins, 1971.