[Solved]: Linear programming formulation of cheapest k-edge path between two nodes

Problem Detail: 

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges.

Here is my attempt using a flow network: \begin{align} \min \sum_{(i,j) \in E} c_{ij}x_{ij} \end{align} \begin{align} \sum_{j \in V} x_{ji} - \sum_{j \in V} x_{ij} &= \begin{cases} -1,& \text{if } i = s\\ 1, & \text{if } i = t\\ 0, & \text{otherwise}\\ \end{cases} && \forall i \in V\\ \sum_{(i,j) \in E} x_{ij} &= k &&\\ x_{ij} &\geq 0 && \forall (i,j) \in E\\ \end{align}

However, this doesn't eliminate cycles which are disjoint from the $s$-$t$ path. I can use subtour elimination constraints like in the Miller Tucker Zemlin formulation of the Travelling Salesman Problem but this enforces a simple path making the problem harder than it should be.

Any ideas on alternative formulations?

Update: This is part of a slightly bigger formulation here, where $z$ is a slack variable which scalarizes multiple objectives with a rectified-linear function:

\begin{align} \min \sum_{k \in K} z_{k} \end{align} \begin{align} \sum_{(i,j) \in E} c^{k}_{ij}x_{ij} - z_{k} &\leq 1 && \forall k \in K\\ \sum_{j \in V} x_{ji} - \sum_{j \in V} x_{ij} &= \begin{cases} -1,& \text{if } i = s\\ 1, & \text{if } i = t\\ 0, & \text{otherwise}\\ \end{cases} && \forall i \in V\\ x_{ij} &\geq 0 && \forall (i,j) \in E\\ \end{align}

Solutions are integral when solving with a linear program, but suggestions for more efficient algorithms would be appreciated.

Asked By : bravetang8

Answered By : D.W.

The simplest way to compute the shortest path from $s$ to $t$ that traverses exactly $k$ edges is by increasing the size of the graph $k$-fold.

In particular, make $k$ copies of the vertices and $k-1$ copies of the edges, where for each edge $(u,v)$ in the original graph, we add an edge from the $i$th copy of $u$ to the $i+1$th copy of $v$ (for all $i$). Now look for the shortest path from the 1st copy of $s$ to the $k$th copy of $t$ using a standard algorithm (e.g., Dijkstra's algorithm). The running time will be $O(kn+km\lg(kn))$.

Only you can determine whether this kind of formulation will be compatible with your additional constraints and objective function (since you haven't told us what they are), but this kind of modification to the graph is a general approach for this sort of problem that is pretty flexible and might meet your needs.

You could presumably also combine this with your network flow / LP formulation. Now there will be no cycles that can show up, as the resulting graph is acyclic (a dag). I don't know if that will meet your needs.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37237

 Ask a Question

 Download Related Notes/Documents