¿Cuál es el nombre de esta red de flujo de problema?

Question

Suponga que tiene la siguiente red:

$s$ $t$ son nodos fuente y sumidero. $s$ necesita enviar $3$ unidades de flujo de a $A$ $2$ a $D$; $B$ necesita enviar $3$ unidades de flujo para el fregadero, y $C$ $2$ unidades de flujo. Las aristas entre los nodos azules tienen infinitas capacidades y un fijo costo.

Quiero encontrar una forma factible de flujo con costo mínimo. Aquí la solución es trivial: enviar $3$ unidades de flujo de$A$$B$$2$$D$%#%. Un sub-óptima solución sería enviar el $C$ unidades de flujo de $2$ a $A$, $B$ de $1$ a $A$, $C$ de$1$$D$$B$$1$%#%.

Mi pregunta: ¿hay un nombre para este problema? (es que no es un típico problema de flujo de costo mínimo, ya que los costos no son lineales). Es este problema está relacionado con el Árbol de Steiner problema (como queremos seleccionar un subconjunto de aristas entre la gráfica)? Estoy bastante seguro de que es, ver por ejemplo este artículo.

Answer 1

Su problema está relacionado con el mínimo de borde de flujo de costo del problema (MECF), que es un problema de decisión. Formalmente, se define de la siguiente manera:

Def. (MECF) Dado un presupuesto $P$ y un gráfico dirigido a $G = (V, E, c, p)$ donde $V$ (resp. $E$) es el conjunto de vértices (resp. los bordes), $c(e)$ es la capacidad de un borde de $e \in E$, e $p(e)$ es el costo por una arista $e$, comprobar si existe un máximo de $s,t$-flujo con el precio total no mayor que $P$, para una fuente $s$ y un lavabo $t$. Aquí, el precio de un flujo es la suma de los precios de los bordes en el flujo.