3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andrew Morgan Oct 2 '16 at 23:40
  • $\begingroup$ 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. $\endgroup$ – user164151 Oct 13 '16 at 6:38
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.