Problema de flujo de costo mínimo

El problema del flujo de costo mínimo ( MCFP , por sus siglas en inglés ) es un problema de optimización y decisión que busca la forma más económica de enviar una determinada cantidad de flujo a través de una red de transporte . Una aplicación típica de este problema consiste en encontrar la mejor ruta de entrega desde una fábrica a un almacén, donde la red vial tiene cierta capacidad y un costo asociado. El problema del flujo de costo mínimo es uno de los más fundamentales entre todos los problemas de flujo y circulación, ya que la mayoría de los demás problemas de este tipo pueden formularse como un problema de flujo de costo mínimo y, además, puede resolverse de manera eficiente utilizando el algoritmo simplex de red .

Una red de flujo es un grafo dirigido.${\displaystyle G=(V,E)}$con un vértice de origen${\displaystyle s\in V}$y un vértice de sumidero${\displaystyle t\in V}$donde cada borde${\displaystyle (u,v)\in E}$tiene capacidad${\displaystyle c(u,v)>0}$, fluir${\displaystyle f(u,v)}$y costo${\displaystyle a(u,v)}$, con la mayoría de los algoritmos de flujo de costo mínimo admitiendo bordes con costos negativos. El costo de enviar este flujo a lo largo de un borde${\displaystyle (u,v)}$es${\displaystyle f(u,v)\cdot a(u,v)}$El problema requiere una cantidad de flujo${\displaystyle d}$ser enviado desde la fuente${\displaystyle s}$hundirse${\displaystyle t}$.

La definición del problema consiste en minimizar el coste total del flujo a través de todas las aristas:

${\displaystyle \sum _{(u,v)\in E}a(u,v)\cdot f(u,v)}$

con las restricciones

Una variante de este problema consiste en encontrar un flujo máximo, pero con el menor coste entre las soluciones de flujo máximo. Esto podría denominarse problema de flujo máximo de coste mínimo y resulta útil para encontrar emparejamientos máximos de coste mínimo .

Con algunas soluciones, encontrar el flujo máximo de costo mínimo es sencillo. Si no, se puede encontrar el flujo máximo realizando una búsqueda binaria en${\displaystyle d}$.

Un problema relacionado es el problema de circulación de costo mínimo , que puede utilizarse para resolver el problema de flujo de costo mínimo. El problema de circulación de costo mínimo no tiene origen ni destino; en su lugar, tiene costos y límites inferiores y superiores en cada arista, y busca cantidades de flujo dentro de los límites dados que equilibren el flujo en cada vértice y minimicen la suma sobre las aristas del costo multiplicado por el flujo. Cualquier instancia de flujo de costo mínimo puede convertirse en una instancia de circulación de costo mínimo estableciendo el límite inferior de todas las aristas a cero y luego agregando una arista desde el destino.${\displaystyle t}$a la fuente${\displaystyle s}$, con capacidad${\displaystyle c(t,s)=d}$y límite inferior${\displaystyle l(t,s)=d}$, forzando el flujo total de${\displaystyle s}$a${\displaystyle t}$también ser${\displaystyle d}$.

Los siguientes problemas son casos especiales del problema del flujo de costo mínimo (proporcionamos breves esbozos de cada reducción aplicable, por turno): ^{[ 1 ]}

• Problema de la ruta más corta (fuente única). Se requiere que una solución factible al problema del flujo de costo mínimo envíe una unidad de flujo desde una fuente designada.${\displaystyle s}$a un fregadero designado${\displaystyle t}$. Otorgar capacidad infinita a todas las aristas.
• Problema de flujo máximo . Elija una demanda grande.${\displaystyle d}$(lo suficientemente grande como para exceder el flujo máximo; por ejemplo, la suma de las capacidades que salen del vértice de origen) Establezca los costos de todas las aristas en la instancia de flujo máximo en cero e introduzca una nueva arista desde el origen hasta el sumidero con costo unitario y capacidad${\displaystyle d}$.
• Problema de asignación . Supongamos que cada conjunto de partición en la bipartición tiene${\displaystyle n}$vértices, y denotamos la bipartición por${\displaystyle (X,Y)}$. Dar cada uno${\displaystyle x\in X}$suministrar${\displaystyle 1/n}$y dar cada uno${\displaystyle y\in Y}$demanda${\displaystyle 1/n}$Cada arista debe tener capacidad unitaria.

El problema del flujo de coste mínimo se puede resolver mediante programación lineal , ya que optimizamos una función lineal y todas las restricciones son lineales.

Aparte de eso, existen muchos algoritmos combinatorios. ^{[ 1 ]} Algunos de ellos son generalizaciones de algoritmos de flujo máximo , otros utilizan enfoques completamente diferentes.

Algoritmos fundamentales bien conocidos (tienen muchas variaciones):

• Cancelación de ciclos : un método primal general. ^{[ 2 ]}
• Cancelación de corte : un método dual general. ^{[ 3 ] [ 4 ]}
• Cancelación de ciclo medio mínimo : un algoritmo simple fuertemente polinomial . ^{[ 5 ]}
• Ruta más corta sucesiva y escalado de capacidad : métodos duales, que pueden considerarse como la generalización del algoritmo de Ford-Fulkerson . ^{[ 6 ]}
• Escalado de costos : un enfoque primal-dual, que puede considerarse como la generalización del algoritmo push-relabel . ^{[ 7 ]}
• Algoritmo simplex de red : una versión especializada del método simplex de programación lineal . ^{[ 8 ]}
• Algoritmo desequilibrado por DR Fulkerson

• LEMON (biblioteca de C++)
• Kit de programación lineal GNU
• Problema de flujo de red

• Librería LEMON C++ con varios algoritmos de circulación de flujo máximo y coste mínimo.
• La biblioteca del proyecto MCFClass C++ con algunos algoritmos de flujo de costo mínimo y de ruta más corta.