<p>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 &amp; \text{if }(i,j)\in\pi\text{ and }p=p(i,j),\\ 0 &amp; \text{otherwise.}\end{cases}$$
For the $l$- and $z$-variables you do the following. </p>

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

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

<p>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 &amp; \text{for } q=p(i,j')\\ 
0 &amp; \text{for } q\neq p(i,j')
\end{cases}$$
$$l_{iq}=
\begin{cases}
m &amp; \text{for } q=p(j,i)\\ 
0 &amp; \text{for } q\neq p(j,i)
\end{cases}$$  </p>

<p>And LP duality tells you that this is optimal.</p>

CC BY-SA 3.0
2016-10-17T01:54:43.657Z
2016-10-17T01:54:43.657Z
Thomas Kalinowski
<p>Consider this problem:</p>

<p>$$
\begin{align}
\min_{y,z,l \geq 0} \quad &amp; g(y,z,l) :=
\sum_{(i,j)\in E} \sum_p (-w_{ijp}) y_{ijp} &amp;  \\
\textrm{s.t.} \quad &amp; \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} &amp; \forall i \in I, p\in P \\
               &amp; \sum_p (z_{ip} - l_{ip}) = 0 &amp; \forall i\in I
\end{align}
$$</p>

<p>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).<br>
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.</p>

<p>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\}$.</p>

<p>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.</p>

<p>Does anyone recognize this problem or have an idea for a clever heuristic?</p>

CC BY-SA 3.0
2016-10-02T23:40:38.603Z
It might help if you give a conceptual summary of what your problem is solving. If I'm understanding it right, you have a typical multicommodity flow problem, but there are no capacity constraints anywhere, each commodity has to have one unit sent from $1$ to $n$, and one can freely trade commodities 1-for-1 at each vertex. Is that right? If it is, a good strategy is to decide, for each edge, what kind of commodity is going to go across it. Since we can freely trade commodities at vertices, there's nothing stopping us from always shipping the most cost-effective commodity along each edge.
Andrew Morgan
CC BY-SA 3.0
2016-10-13T06:38:11.767Z
Thank you Andrew. This is actually the dual of a primal that arises in the domain of stochastic scheduling. I don't have a meaningful interpretation for the dual (presented here). However, I'll think about your response. You seem to have noticed the trading 1-for-1 property that I hadn't. I'll try to come up with something clever, also based on your feedback, and I'll report my findings.
user164151
<shortest-path><multicommodity-flow>
Anyone recognize this as a special type of multi-commodity flow problem?
user164151
# Anyone recognize this as a special type of multi-commodity flow problem?

(Asked by: username_0 on 2016-10-01)

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?

**Tags:** shortest-path, multicommodity-flow

> **Comments:**
> **username_1**: It might help if you give a conceptual summary of what your problem is solving. If I'm understanding it right, you have a typical multicommodity flow problem, but there are no capacity constraints anywhere, each commodity has to have one unit sent from $1$ to $n$, and one can freely trade commodities 1-for-1 at each vertex. Is that right? If it is, a good strategy is to decide, for each edge, what kind of commodity is going to go across it. Since we can freely trade commodities at vertices, there's nothing stopping us from always shipping the most cost-effective commodity along each edge.  
> **username_0**: Thank you Andrew. This is actually the dual of a primal that arises in the domain of stochastic scheduling. I don't have a meaningful interpretation for the dual (presented here). However, I'll think about your response. You seem to have noticed the trading 1-for-1 property that I hadn't. I'll try to come up with something clever, also based on your feedback, and I'll report my findings.  

---

## 1 answers

### Answer by username_2 on 2016-10-17. Score: 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.


---

