1
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ Hint on the first question: The constraint matrix is of size $|V| \times |E|$ and has exactly 2 nonzero entries in each column. $\endgroup$
    – p.s.
    Jul 10 '14 at 3:39
  • $\begingroup$ @p.s. Thanks for your help. I know the conditions for total unimodularity, so it makes sense then that the matrix will be total unimodular. But could you please tell me how you know that and how a regular column of the matrix looks like? I can sort of guess that you got that because of the first and 3rd constraint (the nonzeros), but I'm not sure how exactly. $\endgroup$
    – dreamer
    Jul 10 '14 at 8:12
  • $\begingroup$ There are $|V|$ rows because there is a constraint for each vertex. There are $|E|$ columns because there is a variable for each edge. Each edge appears in in 2 constraint equations (corresponding to the vertices it connects), so those give you the nonzero entries for a column. $\endgroup$
    – p.s.
    Jul 10 '14 at 19:15
  • $\begingroup$ @p.s. Thanks, that makes sense :) $\endgroup$
    – dreamer
    Jul 10 '14 at 19:22
  • $\begingroup$ @p.s. Sorry for bothering you again but I still don't fully understand it. Could you give an explicit example of how a column/ the matrix looks like? Say that we consider the column of the edge $x_{pq}$. Then where do I put a one and where do I put a $-1$ in that column? Thanks again for your help. $\endgroup$
    – dreamer
    Jul 11 '14 at 9:47
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks a lot for your help! One question that I have: how does one get the two constraints \begin{align*} & 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\\ \end{align*} in the dual problem? $\endgroup$
    – dreamer
    Jul 12 '14 at 8:44
  • $\begingroup$ Recall that each constraint corresponds to a a vertex and each column in the primal corresponds to an edge. So in the dual each constraint will correspond to an edge and each variable will correspond to a vertex. The right hand side of the constraint is the coefficient corresponding to that column in the primal objective. So the constraint will be of the form $\sum_{v \in V} d_v y_v \geq c_{uv}$, for each edge $(u,v) \in E$. But each primal column only has a 1 or a -1 for the tail and head of the edge, and 0 for every other vertex. This is how the first constraint is obtained. $\endgroup$
    – wonko
    Jul 14 '14 at 14:13
  • $\begingroup$ The non-negativity of the dual variables follows from the fact that the corresponding primal constraints are equalities. If you're having trouble with this, I strongly suggest that you review linear programming duality. $\endgroup$
    – wonko
    Jul 14 '14 at 14:15

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.