Problema de flujo máximo con costos por pieza
Esta pregunta es una variante de una pregunta que publiqué anteriormente y también corrige algunos errores tipográficos en la publicación anterior ( Solicitud de complejidad \ Referencia para la variante del problema de flujo máximo ). Algunos de los cambios están resaltados en negrita y cursiva y la principal diferencia está en la función objetivo que se muestra en la ecuación (\ ref {Eq: 1}).
En el problema de flujo de costo máximo estándar con capacidades de arco, el costo de usar un arco es proporcional al flujo a través del arco. Por ejemplo, si$f_{uv}$ es el flujo a través del arco $(u,v)$, entonces el costo de usar este arco viene dado por $\mathbf{c}_{uv} f_{uv}$, dónde $\mathbf{c}_{uv}$es un número no negativo predefinido . Entonces, el objetivo que nos interesa maximizar es$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, dónde $E$son los bordes en el gráfico. Puede suponer que el gráfico contiene una fuente y un nodo receptor, y que todos los flujos emanan de la fuente y drenan hacia el nodo receptor.
Considere la variante en la que el costo asociado con el uso de cualquier arco $(u,v)$ en cambio, viene dado por el máximo puntual de dos funciones lineales:
$$\max{\left(\mathbf{c}_{uv}^{1} f_{uv} , \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)} \tag{1} \label{Eq:1}$$ dónde $\mathbf{b}_{uv}^{2} \leq 0$ es un número no positivo predefinido, y $\mathbf{c}_{uv}^{1}, \mathbf{c}_{uv}^{2} \geq 0$son números no negativos predefinidos . Como antes$f_{uv}$ es el flujo a través del arco $(u,v)$. Como puede observar en Eqn (\ ref {Eq: 1}), puede existir alguna constante$\lambda \geq 0$tal que \ begin {ecuación} \ tag {2} \ label {Eq: 2} \ begin {cases} \ mathbf {c} _ {uv} ^ {1} f_ {uv} \ geq \ mathbf {c} _ { uv} ^ {2} f_ {uv} + \ mathbf {b} _ {uv} ^ {2}, \ text {if} f_ {uv} \ leq \ lambda \\ \ mathbf {c} _ {uv} ^ {1} f_ {uv} \ leq \ mathbf {c} _ {uv} ^ {2} f_ {uv} + \ mathbf {b} _ {uv} ^ {2}, \ text {de lo contrario} \ end {cases } \ end {ecuación} De la ecuación (\ ref {ecuación: 2}), podemos observar que el costo de usar un arco (puede) cambiar (a una función diferente) basado en el flujo a través del arco si excede el umbral$\lambda$.
- ¿La variante del problema de flujo máximo (cuyo objetivo ahora es $\underset{(u, v) \in E}{\sum} \max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$ admitir una solución óptima computable en tiempo polinomial?
- Si no se puede alcanzar un máximo, ¿existe un método eficaz para calcular el superior del problema?
- ¿Hay alguna referencia que pueda señalarme?
PD: Sé que la variante que mencioné puede plantearse como un MILP, sin embargo, estoy interesado en conocer los resultados estructurales y la complejidad de este problema.
Mi pregunta anterior ( Complejidad \ Solicitud de referencia para la variante del problema de flujo máximo ) fue un intento de simplificar el problema publicado aquí. Estoy volviendo a publicar una nueva pregunta ya que la pregunta anterior contenía errores en la descripción.
Respuestas
Puede reescribir el problema de flujo de costo máximo con objetivo $$\underset{(u, v) \in E}{\sum} \max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$$ como un problema de flujo de costo mínimo con objetivo $$\underset{(u, v) \in E}{\sum} g_{uv}(f_{uv})$$ para la función cóncava $g_{uv}(f_{uv}) = -\max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$.
Este problema se conoce como el problema de flujo de red de costo cóncavo mínimo (MCCNFP), que es$\mathcal{NP}$-Duro en general, según este artículo , por ejemplo. Por supuesto, aún es posible que su variante específica sea más fácil.
Hay mucha literatura sobre el MCCNFP, pero parece que modelar el problema como un MILP y probar si se resuelve en un tiempo razonable es el comienzo más sencillo.