I encountered a specific type of network flow problem, and I want to know if this type of problem has already been studied before. However, I have been unable to find relevant literature because I don't know what to call it.
The problem considers a layered directed acyclic graph $G=(V,A)$ with a root node $r$ and a sink node $t$. The arc set related to each layer has a non-empty subset of arcs with label 1. To give an example of such a graph, consider the following example graph. In this example, each row of nodes constitutes a layer, all arcs are directed away from $r$ towards $t$, and the labeled arcs in each layer are drawn full while all unlabeled arcs are drawn dashed.
The problem I intend to solve is finding a minimum $r-t$ flow such that, in each layer, exactly one labeled arc has a nonzero flow, and this flow has a value of 1. On our example graph, we would have the following minimum flow. Here, all arcs colored green have a flow of 1 going through them unless indicated otherwise with another number (2 or 3).
To solve this problem, I use the following integer programming formulation:
\begin{align} & \min \sum_{a \in \delta^+(r)} y(a) & \nonumber \\ \text{s.t.} & \sum_{a = (u,v)|L(u) = j, \ell(a)=1} y(a) = 1 & \forall~j \in N \label{cons:nfm_onearcs}\\ & \sum_{a \in \delta^- (u)} y(a) - \sum_{a \in \delta^+ (u)} y(a) = 0 & \forall~ u \in V \setminus \{r, t\} \label{cons:nfm_flowconservation}\\ & y(a) \in \{0,1,...,n\} &\forall~a \in A \label{cons:nfm_integrality} \end{align} where:
- y(a) is an integer variable modelling the flow through arc $a$
- $\delta^+(v)$ is the set of outgoing arcs of a node $v$. Likewise, $\delta^-(v)$ is the set of incoming arcs.
- $L(v)$ is the layer of a node $v$, and $N$ denotes the set of layers.
- $\ell(a)$ denotes the label of an arc $a$ (either 0 or 1)
The second set of constraints are flow-balance constraints, the first set of constraints enforces that, in each layer, only one labeled arc has a flow of 1 (along with the integrality constraints). The formulation minimizes the overall flow through the network by minimizing the flow through the outgoing arcs of the root node.
I would like to know if this problem or similar problems have already been studied. I would call this a minimum flow problem on a layered graph with set covering constraints (as the first set of constraints can also be rewritten to a set covering constraint, i.e. $\geq 1$ constraints). However, I have not been able to find literature on this problem using this terminology or similar phrasing. Therefore, I want to know: what search terms could I use to find more about this problem?
Thanks in advance for your help! If anything is unclear, please indicate it so I can try to refine my post :)