The IP formulation of the shortest path problem looks as follows:
\begin{align*}
\min & \sum_{u,v \in A} c_{uv} x_{uv}\\
\text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} – \sum_{v \in V^{-}(s)}x_{vs} = 1\\
& \sum_{v \in V^{+}(u)} x_{uv} – \sum_{v \in V^{-}(u)}x_{vu} = 0 \quad \text{ for each } u \in V\setminus\{s,t\}\\
& \sum_{v \in V^{+}(t)} x_{tv} – \sum_{v \in V^{-}(t)}x_{vt} = -1\\
& x_{uv} \in \mathbb{N} \quad \text{ for each } (u,v) \in A
\end{align*}
Now I actually have 2 questions:
First of all, my book indicates that the constraint matrix is totally unimodular for this problem. I know the definition of total unimodularity, but is there an easy way with the summations here to what the constraint matrix would look like (if I could construct the matrix, I think I could show that it is totally unimodular).
My second question is as follows. My book states that the corresponding dual problem to the problem above is:
\begin{align*}
\max & \ y_t\\
\text{s.t. } & y_v – y_u \leq c_{uv} \quad \text{ for each } (u,v) \in E\\
& y_u \geq 0 \quad \text{ for each } u \in V\\
& y_s = 0
\end{align*}
I know in general how one can construct dual problems, but I didn't succeed in getting to this one here. Could anyone please show me how it's done?
Thanks in advance!
Best Answer
p.s. has really already answered your question. But anyway. There is one constraint for each vertex in the graph. The first summation on the left hand side is for arcs going out of the vertex, while the second summation is for arcs coming in. The sets $V^+(u)$ and $V^-(u)$ represent the forward and backward stars at the vertex $u$ respectively.
So what does this all mean? Imagine the constraints are written as $A x = b$. Then the coefficient $A_{ij}$ is 1 if arc $j$ has its head at node $i$, -1 if arc $j$ has its tail at node $i$ and 0 if arc $j$ is not incident on node $i$. At this point it should be easy to see that $A$ is in fact that the incidence matrix of the graph (or the transpose depending on notation).
For the second question, the formulation for the dual you've given is in fact a reformulation of the standard dual construction. Consider the $y$ variables as negatives of the dual variables. Note also that the objective function in the usual dual would actually be $y_t - y_s$. But the dual is in fact under constrained, which is why fixing $y_s = 0$ works. You can in fact fix $y_s$ to anything you want, and keep the objective function as $y_t - y_s$ and obtain a valid dual.