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$.
- 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?
- If a maximum is not attainable, is there an efficient method to compute the supremum for the problem?
- 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.