Max flow problem with piece-wise costs

Question

This question is a variant of a question I posted earlier and also fixes some typos in the earlier post (Complexity \ Reference request for variant of max flow problem). Some of the changes are highlighted in bold italics and the main difference is in the objective function shown in Eqn (\ref{Eq:1}).

In the standard max cost flow problem with arc capacities, the cost of using an arc is proportional to the flow through the arc. For example, if $f_{uv}$ is the flow through the arc $(u,v)$, then the cost of using this arc is given by $\mathbf{c}_{uv} f_{uv}$, where $\mathbf{c}_{uv}$ is some predefined non-negative number. So the objective we are interested in maximizing is $\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, where $E$ is the edges in the graph. You may assume that graph contains a source and a sink node, and all flows emanate from the source and drain into the sink node.

Consider the variant in which the cost associated with using any arc $(u,v)$ is instead given by the pointwise maximum of two linear functions:

$$\max{\left(\mathbf{c}_{uv}^{1} f_{uv} , \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)} \tag{1} \label{Eq:1}$$ where $\mathbf{b}_{uv}^{2} \leq 0$ is some predefined non-positive number, and $\mathbf{c}_{uv}^{1}, \mathbf{c}_{uv}^{2} \geq 0$ are pre-defined non-negative numbers. As before $f_{uv}$ is the flow through the arc $(u,v)$. As you can observe from Eqn (\ref{Eq:1}), there may exists some constant $\lambda \geq 0$ such that \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{ otherwise } \end{cases} \end{equation} From Eqn (\ref{Eq:2}), we can observe that the cost of using an arc (may) switch (to a different function) based on the flow through the arc if it exceeds the threshold $\lambda$.

1. Does the variant of the max flow problem (whose objective now is $\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)}$ admit a polynomial-time computable optimal solution?
2. If a maximum is not attainable, is there an efficient method to compute the supremum for the problem?
3. Are there any references that you can point me to?

P.S. I know that the variant I stated can be posed as a MILP, however, I am interested in learning about the structural results and complexity of this problem.

My previous question (Complexity \ Reference request for variant of max flow problem) was an attempt to simplify the problem posted here. I am reposting a new question since the earlier question contained mistakes in the description.

Answer 1

You can rewrite the maximum cost flow problem with objective $$\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)}$$ as a minimum cost flow problem with objective $$\underset{(u, v) \in E}{\sum} g_{uv}(f_{uv})$$ for the concave function $g_{uv}(f_{uv}) = -\max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$.

This problem is known as the minimum concave-cost network flow problem (MCCNFP), which is $\mathcal{NP}$-hard in general, according to this paper, for example. Of course it is still possible that your specific variant is easier.

There is a lot of literature on the MCCNFP, but it seems that modeling the problem as a MILP and testing whether it solves in reasonable time is the most straightforward start.