# Max flow problem with piece-wise costs

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 $$$$\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}$$$$ 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.

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.