Problema di flusso massimo con costi a pezzo

Question

Questa domanda è una variante di una domanda che ho postato in precedenza e corregge anche alcuni errori di battitura nel post precedente ( Complexity \ Reference request for variant of max flow problem ). Alcuni dei cambiamenti sono evidenziati in grassetto corsivo e la differenza principale è nella funzione obiettivo mostrata in Eqn (\ ref {Eq: 1}).

Nel problema del flusso di costo massimo standard con capacità dell'arco, il costo dell'utilizzo di un arco è proporzionale al flusso attraverso l'arco. Ad esempio, se$f_{uv}$ è il flusso attraverso l'arco $(u,v)$, quindi il costo dell'utilizzo di questo arco è dato da $\mathbf{c}_{uv} f_{uv}$, dove $\mathbf{c}_{uv}$è un numero non negativo predefinito . Quindi l'obiettivo che ci interessa massimizzare è$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, dove $E$sono i bordi nel grafico. Si può presumere che il grafico contenga una sorgente e un nodo sink e che tutti i flussi provengano dall'origine e drenino nel nodo sink.

Considera la variante in cui il costo associato all'uso di qualsiasi arco $(u,v)$ è invece dato dal massimo puntuale di due funzioni lineari:

$$\max{\left(\mathbf{c}_{uv}^{1} f_{uv} , \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)} \tag{1} \label{Eq:1}$$ dove $\mathbf{b}_{uv}^{2} \leq 0$ è un numero non positivo predefinito e $\mathbf{c}_{uv}^{1}, \mathbf{c}_{uv}^{2} \geq 0$sono numeri non negativi predefiniti . Come prima$f_{uv}$ è il flusso attraverso l'arco $(u,v)$. Come puoi osservare da Eqn (\ ref {Eq: 1}), potrebbe esistere qualche costante$\lambda \geq 0$tale che \ begin {equation} \ 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 {altrimenti} \ end {case } \ end {equation} Da Eqn (\ ref {Eq: 2}), possiamo osservare che il costo dell'uso di un arco (può) passare (a una funzione diversa) in base al flusso attraverso l'arco se supera la soglia$\lambda$.

1. La variante del problema del flusso massimo (il cui obiettivo ora è $\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)}$ ammettere una soluzione ottima calcolabile in tempo polinomiale?
2. Se non è possibile raggiungere un massimo, esiste un metodo efficiente per calcolare l'estremo superiore del problema?
3. Ci sono riferimenti a cui puoi indicarmi?

PS So che la variante che ho dichiarato può essere presentata come MILP, tuttavia, sono interessato a conoscere i risultati strutturali e la complessità di questo problema.

La mia domanda precedente ( Complessità \ Richiesta di riferimento per la variante del problema del flusso massimo ) era un tentativo di semplificare il problema pubblicato qui. Sto ripubblicando una nuova domanda poiché la domanda precedente conteneva errori nella descrizione.

Answer 1

È possibile riscrivere il problema del flusso di costo massimo con obiettivo $$\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)}$$ come problema di flusso di costo minimo con obiettivo $$\underset{(u, v) \in E}{\sum} g_{uv}(f_{uv})$$ per la funzione concava $g_{uv}(f_{uv}) = -\max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$.

Questo problema è noto come MCCNFP ( minimum concave-cost network flow problem ), ovvero$\mathcal{NP}$-duro in generale, secondo questo articolo , per esempio. Ovviamente è ancora possibile che la tua variante specifica sia più semplice.

C'è molta letteratura sul MCCNFP, ma sembra che modellare il problema come MILP e verificare se si risolve in un tempo ragionevole sia l'inizio più semplice.