Anyone recognize this as a special type of multi-commodity flow problem?

Question

Consider this problem:

$$ \begin{align} \min_{y,z,l \geq 0} \quad & g(y,z,l) := \sum_{(i,j)\in E} \sum_p (-w_{ijp}) y_{ijp} & \\ \textrm{s.t.} \quad & \left( \sum_{(i,j)\in E} y_{ijp} + l_{ip} \right)- \left( \sum_{(j,i)\in E} y_{jip} + z_{ip} \right)= \begin{cases} +1 \quad i=1 \\ -1 \quad i=n \\ 0 \qquad i\neq 1,n \end{cases} & \forall i \in I, p\in P \\ & \sum_p (z_{ip} - l_{ip}) = 0 & \forall i\in I \end{align} $$

Sets $I=\{1,\ldots,n\}$ and $P=\{1,\ldots,m\}$ correspond to $n$ nodes and $m$ commodities. Set $E \subseteq I\times I$ corresponds to the arcs of a directed acyclic graph where node $1$ is the source (no predecessors) and node $n$ is the sink (no successors).
Sending $y_{ijp}$ units of commodity $p$ from node $i$ to $j$ costs $-w_{ijp}y_{ijp}$, with all $w_{ijp}$ positive. Note that all commodities have $1$ as the source and $n$ as the sink.

If you ignore the $z_{ip}$ and $l_{ip}$ variables the problem becomes a set of $m$ independent shortest-path problems. Specifically, let $C = \{(y,z,l)\}$ denote the class of all solutions with $z_{ip} = l_{ip}$ for all $i, p$. Then, the best $(y,z,l) \in C$ can be found by solving $m$ independent shortest-path problems, i.e. by assigning $y_{ijp} \in \{0,1\}$.

It is this remark that makes me hope that we are dealing with a special-case of multicommodity flow that can be solved more efficiently. But I haven't found anything in the literature.

Does anyone recognize this problem or have an idea for a clever heuristic?

Answer 1

I think you can solve this as a single shortest path problem with respect to arc weights $$\overline{w}_{ij}=\min\{-w_{ijp}\ :\ p\in\{1,\ldots,m\}\}.$$ For every arc $(i,j)$ fix some $p(i,j)\in\{1,\ldots,m\}$ with $-w_{ijp(i,j)}=\overline{w}_{ij}$. If you have a shortest path $\pi$ with respect to $\overline{w}$, you can put $$y_{ijp}=\begin{cases} m & \text{if }(i,j)\in\pi\text{ and }p=p(i,j),\\ 0 & \text{otherwise.}\end{cases}$$ For the $l$- and $z$-variables you do the following.

If $(1,j)\in\pi$ is the arc leaving 1 then $$z_{1q}=\begin{cases}m-1 & \text{for } q=p(1,j)\\ 0 & \text{for } q\neq p(1,j)\end{cases}$$ $$l_{1q}=\begin{cases}1 & \text{for } q\neq p(1,j)\\ 0 & \text{for } q= p(1,j)\end{cases}$$

If $(i,n)\in\pi$ is the arc entering $n$ then $$z_{nq}=\begin{cases}0 & \text{for } q=p(i,n)\\ 1 & \text{for } q\neq p(i,n)\end{cases}$$ $$l_{1q}=\begin{cases}0 & \text{for } q\neq p(i,n)\\ m-1 & \text{for } q= p(i,n)\end{cases}$$

If $(j,i)$, $(i,j')$ are two consecutive arcs of $\pi$ then you put $l_{ip}=z_{ip}=0$ if $p(j,i)=p(i,j')$, and otherwise $$z_{iq}= \begin{cases} m & \text{for } q=p(i,j')\\ 0 & \text{for } q\neq p(i,j') \end{cases}$$ $$l_{iq}= \begin{cases} m & \text{for } q=p(j,i)\\ 0 & \text{for } q\neq p(j,i) \end{cases}$$

And LP duality tells you that this is optimal.