6

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.

batwing
  • 1,458
  • 6
  • 15
  • 1
    Is your objective to maximize the sum of the weighted flows, or are you looking for the weighted minimum-cost solution given that the unweighted flow is equal to the maximum (a min-cost max-flow problem)? – Kevin Dalmeijer Aug 18 '20 at 00:54
  • @KevinDalmeijer - The OP should have read max cost flow. So yes, I am interested in maximizing the sum of weighted flows, where the weights for the edges are provided in the $\mathbf{c}$ vector. – batwing Aug 18 '20 at 01:51
  • You want to maximize cost? Are there any demand constraints on the nodes? Do you have a source node and a sink node? – RobPratt Aug 18 '20 at 02:00
  • @RobPratt - Just the simplest case where we have a source and a sink node, and we want to find the flow from source to sink that costs the most. I will clarify this in the OP as well. – batwing Aug 18 '20 at 02:10
  • In this case, the standard form would be to multiply all weights by -1 and state it as an equivalent min-cost flow problem. – Kevin Dalmeijer Aug 18 '20 at 12:17

1 Answers1

4

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.

PSLP
  • 2,401
  • 9
  • 33
  • 1
    I agree. The goal is to maximize an objective function that is not upper semi-continuous, which is going to lead to problems except in trivial cases. – Kevin Dalmeijer Aug 18 '20 at 12:20
  • Yes, I think that is a great point. I think a max may not exist, but a supremum will exist though. Is there an efficient procedure to compute the sup value? – batwing Aug 18 '20 at 15:05