3
$\begingroup$

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.

$\endgroup$
4

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.