4
$\begingroup$

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

  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.

$\endgroup$
3
$\begingroup$

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.

There is a lot of literature on the MCCNFP, but it seems that modeling the problem as a MILP and testing whether it solves in reasonable time is the most straightforward start.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I believe he wants to solve a mincost flow and not a maxcost flow. The maximum of two linear functions us convex, and within a minimization this can be modeled by adding a continuous variable zuv for each arc and constraints zuv ≥ f1, zuv ≥ f2. Total unimodularity would be lost though $\endgroup$ – Claudio Contardo Aug 19 at 1:34
  • 1
    $\begingroup$ I agree that min cost flow with this objective would be easier. You might even be able to maintain unimodularity by defining parallel arcs with appropriate weights. But also based on batwing's comments on the other question, it seems that max cost flow is of interest here. $\endgroup$ – Kevin Dalmeijer Aug 19 at 2:00

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.