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.

  • 1
    $\begingroup$ 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)? $\endgroup$ – Kevin Dalmeijer Aug 18 at 0:54
  • $\begingroup$ @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. $\endgroup$ – batwing Aug 18 at 1:51
  • $\begingroup$ You want to maximize cost? Are there any demand constraints on the nodes? Do you have a source node and a sink node? $\endgroup$ – RobPratt Aug 18 at 2:00
  • $\begingroup$ @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. $\endgroup$ – batwing Aug 18 at 2:10
  • $\begingroup$ In this case, the standard form would be to multiply all weights by -1 and state it as an equivalent min-cost flow problem. $\endgroup$ – Kevin Dalmeijer Aug 18 at 12:17

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.

| improve this answer | |
  • 1
    $\begingroup$ 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. $\endgroup$ – Kevin Dalmeijer Aug 18 at 12:20
  • $\begingroup$ 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? $\endgroup$ – batwing Aug 18 at 15:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.