Flow with edge-weight restrictions

Question

I am given a graph $G=(V,E)$ undirected and two vertices, the source vertex $s$ and the target vertex $t$. Additionally, each edge comes with a capacity $c(e)$ (non-negative) and a set of weight functions $w_1(e),...,w_k(e)$. To simplify things, assume these weight functions are non-negative as well. I am also given a set of upper bounds $l_1 ,...,l_k$.

The weight of a set of edges under any $w_i$ is additive. Denote $\tilde{E}$ as the set of edges (from the original graph) with positive flow (not back edges with the reverse flow, and not edges with a flow of zero). I would like to find the maximal flow between $s$ and $t$ such that $w_i (\tilde{E} ) \leq l_i$ for all indices $i$.

In other words, I am trying to find a flow under constraints for the edges that are being used.

I'm assuming this problem, as described, might be too hard to tackle. In this case, some assumptions can be made:

1. $c(e) = 1$ for all edges.
2. The goal is to find a flow $|f| > 1$, but it does not have to be maximal, only non-trivial.

If this is still too hard, we can assume that $k=1$ and, for an edge, there is only the capacity and the weight. (I'm interested in the case of several weight functions, but if that approach is too hard, also a single weight function, and perhaps that idea can be generalized).

Answer 1

If $k=1$ and $c(e)=1$ for all edges $e$, then this looks equivalent to the minimum cost flow problem -- specifically, to finding an integral minimum cost flow. I believe combinatorial methods for the minimum cost flow problem are guaranteed to output an integral solution (if one exists).

If $k>1$, this reminds me of multi commodity flow which is NP-hard. You might check whether the proof of NP-hardness for (integral) multi commodity flow can be adjusted to apply to your problem as well.

If I had to solve it in practice, I would start by formulating it as an integer linear program and applying an ILP solver. In particular, you could introduce a zero-or-one variable $x_e$ for each edge $e$, with intention that if $x_e=0$ then the flow through $e$ is 0, and if $x_e=1$ then the flow through $e$ is non-zero. Assuming you are interested in integral flows (which you didn't actually state), then you can enforce this with the linear inequalities $f_e \ge x_e$ and $f_e \le M x_e$ where $M$ is a sufficiently large constant. Then add the flow conservation equations and minimize your objective function (which is a linear function of the $x$'s), and you should be good to go.