El problema del flujo de múltiples productos básicos es un problema de flujo de red con múltiples productos (demandas de flujo) entre diferentes nodos fuente y sumidero.
Definición
Dada una red de flujo , donde borde tiene capacidad . Existen materias primas , definido por , dónde y es la fuente y el sumidero de los productos básicos, y es su demanda. La variable define la fracción de flujo a lo largo del borde , dónde en caso de que el flujo se pueda dividir entre varias rutas, y 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 de enlace: la suma de todos los flujos enrutados a través de un enlace no excede su capacidad.
(2) Conservación del flujo en los nodos de tránsito: la cantidad de flujo que ingresa a un nodo intermedio. es el mismo que sale del nodo.
(3) Conservación del flujo en la fuente: un flujo debe salir de su nodo fuente por completo.
(4) Conservación del flujo en el destino: un flujo debe entrar completamente en su nodo sumidero.
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 es incluso, donde
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, dónde
En el problema del flujo de productos básicos de costo mínimo , hay un costo por enviar un flujo en . Entonces necesitas minimizar
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.
Relación con otros problemas
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 y un fregadero . Las variantes del problema de la 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]
Uso
La asignación de enrutamiento y longitud de onda (RWA) en la conmutación de ráfagas ópticas de la red óptica se abordaría mediante fórmulas de flujo de múltiples productos.
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 , [2] 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 se puede resolver en tiempo polinomial mediante programación lineal , [3] o mediante esquemas de aproximación de tiempo completamente polinomial (normalmente mucho más rápido) . [4]
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
- ↑ Ahuja, Ravindra K .; Magnanti, Thomas L .; Orlin, James B. (1993). Flujos de red. Teoría, algoritmos y aplicaciones . Prentice Hall.
- ^ S. Even y A. Itai y A. Shamir (1976). "Sobre la complejidad de los problemas de flujo de productos y horarios". Revista SIAM de Computación . SIAM. 5 (4): 691–703. doi : 10.1137 / 0205048 .Incluso, S .; Itai, A .; Shamir, A. (1975). "Sobre la complejidad de la tabla de tiempo y los problemas de flujo de múltiples productos básicos". 16º Simposio Anual sobre Fundamentos de las Ciencias de la Computación (SFCS 1975) . págs. 184-193. doi : 10.1109 / SFCS.1975.21 .
- ^ 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.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ George Karakostas (2002). "Esquemas de aproximación más rápidos para problemas de flujo fraccional de múltiples productos" . Actas del decimotercer simposio anual ACM-SIAM sobre algoritmos discretos . págs. 166-173 . ISBN 0-89871-513-X.
Agregue: Jean-Patrice Netter, Mallas de aumento de flujo: un tipo primordial de enfoque para el flujo de enteros máximo en una red de múltiples productos, tesis doctoral de la Universidad Johns Hopkins, 1971