# Flow problem with flow demands

Recently I found a subproblem in a project I am working with. This problem is a sort of flow variant, as you will see. And I am looking for literature-related articles and also fast approaches for tackling the problem. In this variant we have a flow network $$(D, c, s, t)$$, where:

• $$D(V, A)$$ is a digraph, where:
• $$(s, i) \in A \quad \forall i \in V \backslash \{s, t\}$$, i.e. there is an arc from the source node $$s$$ to each node in the digraph, excepting the target node $$t$$; And
• $$(i, t) \in A \quad \forall i \in V \backslash \{s, t\}$$, i.e. there is an arc from each node, excepting the source $$s$$, to the target node $$t$$.
• $$c: A \rightarrow \mathbb{N}$$ is the arc capacity function;
• $$s \in V$$ is the source node; And
• $$t \in V$$ is the target node.

And we also have

• $$d: V \rightarrow \mathbb{N}$$ a function stating the flow demand of each node; And
• $$F \in \mathbb{N}$$ which represents the initial flow at the source node $$s$$.

A feasible solution for an instance $$((D, c, s, t), d, F)$$ of this flow variant is given by $$f: A \rightarrow \mathbb{N}$$, such that:

1. $$\sum_{a \in \delta^{-}(i)} f_a = \sum_{a \in \delta^{+}(i)} f_a = d_i$$ $$\forall i \in V \backslash \{s, t\}$$, i.e. the entering flow, the leaving flow, and the flow demand of a given node are the same, excepting for the $$s$$ and $$t$$ nodes;
2. $$\sum_{a \in \delta^{+}(s)} f_a \leqslant F$$, i.e. the flow sent by the source $$s$$ is at most $$F$$; And
3. $$f_a \leqslant c_a$$, i.e. the flow sent in a given arc is limited by the arc capacity.

This flow variant is a decision problem that concerns finding a feasible $$f$$ for a given instance $$((D, c, s, t), d, F)$$. As far as I concern, this problem is a sort of max-flow with integer and mandatory flows - flows that must assume integral measures and must satisfy the nodes' flow demands.

Of course, we could design CP and IP models for solving the problem. However, for the purpose this problem is being used for, fast algorithms are required, once this problem is embedded as a subproblem of a global algorithm. Thus, I would like to know if someone has some related literature references, and also algorithms suggestions, even if relying on mathematical programming models.

• Most modern solvers are pretty fast unless your dimensions are in hundreds of thousands. You may not need any binary variable if that's the issue. If flow needs to be integer then need to fine-tune integrality gap parameter that most solvers allow access to. Jan 18 at 22:55
• You can still model it as a flow problem by making copies of the existing nodes and introducing new arcs with fixed flow. Since it's a flow problem, if the data is integer, then the solution will be integral. Jan 19 at 0:23
• Thanks for the answer. @mtanneau could you please elaborate on this strategy of making copies and adding new arcs? Jan 19 at 9:45
• Thanks for the answers, everyone. I found out that this problem is a max-flow with lower bounds, follows source: cs.stackexchange.com/questions/125331/…. Also, follows alternative sources: (cp-algorithms.com/graph/…), (courses.engr.illinois.edu/cs573/fa2010/notes/18-maxflowext.pdf), and (cs.uu.nl/docs/vakken/an/an-maxflow-2016.pdf). Jan 19 at 23:35