Problema de flujo de costo mínimo

El problema de flujo de costo mínimo (MCFP) es un problema de optimización y decisión para encontrar la forma más económica posible de enviar una cierta cantidad de flujo a través de una red de flujo. Una aplicación típica de este problema implica encontrar la mejor ruta de entrega desde una fábrica a un almacén donde la red de carreteras tiene cierta capacidad y costo asociado. El problema de flujo de costo mínimo es uno de los más fundamentales entre todos los problemas de flujo y circulación porque la mayoría de los demás problemas de este tipo se pueden plantear como un problema de flujo de costo mínimo y también se puede resolver de manera eficiente utilizando el algoritmo símplex de red.

Una red de flujo es un gráfico dirigido ${\displaystyle G=(V,E)}$ con un vertex fuente ${\displaystyle s\in V}$ y un vértice de fregadero ${\displaystyle t\in V}$, donde cada borde ${\displaystyle (u,v)\in E}$ capacidad ${\displaystyle c(u,v)}$, flujo ${\displaystyle f(u,v)}$ y gastos ${\displaystyle a(u,v)}$, con la mayoría de algoritmos de flujo de coste mínimo que soportan 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}$ para ser enviado desde la fuente ${\displaystyle s}$ para hundirse ${\displaystyle t}$.

La definición del problema es minimizar el costo total del flujo en todos los bordes:

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

con las restricciones

Limitaciones de la capacidad:	${\displaystyle \,f(u,v)\leq c(u,v)}$
Simetría de Skew:	${\displaystyle \,f(u,v)=-f(v,u)}$
Conservación del flujo:	${\displaystyle \,\sum _{w\in V}f(u,w)=0{\text{ for all }u\neq s,t}$
Flujo obligatorio:	${\displaystyle \,\sum _{w\in V}f(s,w)=d{\text{ and }\sum _{w\in V}f(w,t)=d}$

Una variación de este problema consiste en encontrar un flujo que sea máximo, pero que tenga el menor costo entre las soluciones de flujo máximo. Esto podría llamarse un problema de flujo máximo y costo mínimo y es útil para encontrar correspondencias máximas de costo mínimo.

Con algunas soluciones, encontrar el flujo máximo de costes mínimos 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 mínimo de circulación de costos, que se puede utilizar para resolver el flujo mínimo de costos. El problema de la circulación de costes mínimos no tiene fuente ni sumidero; en cambio tiene costos y límites inferiores y superiores en cada borde, y busca cantidades de flujo dentro de los límites dados que equilibran el flujo en cada vértice y minimizan la suma sobre los bordes del flujo de tiempos de coste. Cualquier instancia de flujo de coste mínimo se puede convertir en una instancia de circulación de costes mínimos estableciendo el límite inferior en todos los bordes a cero, y luego haciendo un borde extra del lavabo ${\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}$ y también ${\displaystyle d}$.

Los siguientes problemas son casos especiales del problema del flujo de costo mínimo (incluimos breves bosquejos de cada reducción aplicable, por turno):

• Problema de ruta más corto (fuente individual). Exigir que una solución viable al problema del flujo mínimo de costos envíe una unidad de flujo de una fuente designada ${\displaystyle s}$ a un sumidero designado ${\displaystyle t}$. Dar todos los bordes capacidad infinita.
• Problema de flujo máximo. Elija una gran demanda ${\displaystyle d}$ ( lo suficientemente grande como para superar el flujo máximo; por ejemplo, la suma de capacidades fuera del vértice fuente) Establecer los costos de todos los bordes en la instancia de flujo máximo a cero, e introducir un nuevo borde de fuente a fregadero con costo unitario y capacidad ${\displaystyle d}$.
• Problema de asignación. Supongamos que cada partito establecido en la bipartición tiene ${\displaystyle n}$ vertices, y denota la bipartición por ${\displaystyle (X,Y)}$. Dar cada uno ${\displaystyle x\in X}$ Suministro ${\displaystyle 1/n}$ y dar cada uno ${\displaystyle y\in Y}$ demanda ${\displaystyle 1/n}$. Cada borde es tener capacidad unitaria.

El problema del flujo de costo 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. Algunos de ellos son generalizaciones de algoritmos de flujo máximo, mientras que otros utilizan enfoques completamente diferentes.

Algoritmos fundamentales conocidos (tienen muchas variantes):

• Ciclo cancelando: un método primal general.
• Cancelación de corte: un método dual general.
• Ciclo mínimo medio de cancelación: un simple algoritmo polinomio fuerte.
• Sendero más corto y ampliación de la capacidad: métodos duales, que se pueden ver como la generalización del algoritmo Ford-Fulkerson.
• Escala de costos: un enfoque primario-dual, que se puede ver como la generalización del algoritmo de la etiqueta de empuje.
• algoritmo de red simplex: una versión especializada del método lineal de programación simplex.
• algoritmo fuera de kilter por D. R. Fulkerson

Dado un grafo bipartito G = (A ∪ B, E), el objetivo es encontrar la correspondencia de cardinalidad máxima en G que tenga un costo mínimo. Sea w: E → R una función de peso en los bordes de E. El problema de correspondencia bipartita de peso mínimo o problema de asignación es encontrar una correspondencia perfecta M ⊆ E cuyo peso total se minimice. La idea es reducir este problema a un problema de flujo de red.

Sea G′ = (V′ = A ∪ B, E′ = E). Asignamos la capacidad de todas las aristas en E′ a 1. Agregamos un vértice fuente s y lo conectamos a todos los vértices en A′ y agregamos un vértice sumidero t y conectamos todos los vértices dentro del grupo B′ a este vértice. La capacidad de todas las nuevas aristas es 1 y sus costos son 0. Se demuestra que existe una correspondencia bipartita perfecta de peso mínimo en G si y solo si existe un flujo de costo mínimo en G′.

• LEMON (C+)
• GNU Linear Programming Kit
• Problema de flujo de red

• Biblioteca LEMON C++ con varios algoritmos de flujo máximo y circulación mínima
• La biblioteca de proyectos MCFClass C++ con un flujo mínimo de costes y algoritmos de trayectoria más cortos