Complexity \ Reference request for variant of max flow problem

Question

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 real 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 the arc $(u,v)$ is instead given by: \begin{cases} \mathbf{c}_{uv} f_{uv} + \mathbf{b}_{uv}, \text{ if } f_{uv} > 0,\\ 0, \text{ otherwise} \end{cases} where $\mathbf{b}_{uv}$ is some predefined positive number.

1. Does the variant of the max flow problem admit a polynomial-time solution?
2. If not, are there any references that you can point me to?

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

Answer 1

i would assume, that there doesn't even exist an optimal solution.

You want to have $\epsilon$-flow across every edge to collect all the cost $b_{uv}$. On the other hand you want to maximize the flow across the edges with the highest cost $c_{uv}$. This leads to pressure to have $\epsilon$ as small as possible, while still $\epsilon > 0$. Such an $\epsilon$ cannot exist.