% Title:  lps
%
% Doc: /usr/zealand1/ney/cs45/lps.tex
% Original Author:     Neal Young neal.young@dartmouth.edu
% Created:             Thu May 15 1997
%

\documentclass[11pt]{article}

\usepackage{fullpage}

% Some useful definitions...
\newenvironment{lp}[2]{
\samepage
\renewcommand{\arraystretch}{1.3}
\begin{eqnarray*}
& & \mbox{#1\ } #2 \\
& & \mbox{subject to\ }\left\{ % } MATCHING
\begin{array}{rcl@{\hspace{0.2in}}l}}{
\end{array}\right.
\end{eqnarray*}
}

\newcommand{\R}{{\sf R\hspace*{-0.9ex}\rule{0.15ex}{1.5ex}\hspace*{0.9ex}}}

\begin{document}

\paragraph{Max flow.}
Given a flow network $G=(V,V\times V)$ with edge capacities
$c:V\times V\rightarrow \R$, source $s$, and sink $t$,
here is a linear program for the max-flow problem:
\begin{lp}{maximize}{f(t,s)}
  \sum_{v\in V} f(w,v) - \sum_{u\in V} f(u,w) & = & 0 & \forall w\in V \\
  f(u,v) & \le & c(u,v) & \forall u,v \in V, (u,v) \neq (t,s) \\
  f(u,v) & \ge & 0 & \forall u,v \in V.
\end{lp}
There is one variable $f(u,v)$ for each edge $(u,v)$ representing the flow on
the edge.  The ``artificial'' edge $(t,s)$ is there to simplify things a bit
--- it allows a simple expression for the value of the flow ($f(t,s)$)
and allows conservation to hold at all vertices.

Recall that if the capacities are integers,
then there is always a maximum flow that is integer-valued.

\paragraph{Shortest path.}
Given a graph $G=(V,V\times V)$ with edge weights
$w:V\times V\rightarrow \R$, source $s$, and sink $t$,
here is a linear program for the shortest $s-t$ path problem:
\begin{lp}{minimize}{\sum_{u,v} w(u,v)f(u,v)}
  \sum_{v\in V} f(w,v) - \sum_{u\in V} f(u,w) & = & 0 & \forall w\in V \\
  f(t,s) & = & 1 & \\
  f(u,v) & \ge & 0 & \forall u,v \in V.
\end{lp}
This represents a flow of one unit of substance from $s$ to $t$.  The way to
understand the relation to shortest paths is that any $s-t$ flow can be
decomposed into a collection of $s-t$ paths, each with some flow along
them (this takes some proof).  This means that the vertices of the polytope
defined by the linear program correspond to flows that represent paths.  Thus,
there is always an optimal solution corresponding to a single path (i.e. a
vertex).

\paragraph{Dual of max-flow.}
The dual of the max-flow linear program is the following:
\begin{lp}{minimize}{\sum_{(u,v)\ne (t,s)} c(u,v) \delta(u,v)}
  \delta(u,v) & \ge & \pi(u) - \pi(v) & \forall (u,v)\ne(t,s) \\
  \pi(s) - \pi(t) & \ge & 1 \\
  \delta(u,v) & \ge & 0.
\end{lp}
There is one variable $\pi(u)$ for each vertex $u$
and another variable $\delta(u,v)$ for each edge $(u,v)$ other than the
``artificial'' edge $(t,s)$.
To see the relation to max-cut, let $(S,T=V-S)$ be any $s-t$ cut, then set
$$\pi(u) = \cases{1 & for $u\in S$ \cr 0 & for $u\in T$}$$
and let 
$$\delta(u,v) = \cases{1 & for $(u,v)\in S\times T$ \cr 0 & otherwise.}$$
Then the cost of the solution is the capacity of the cut $(S,T)$.
Again, in this case, these solutions correspond to vertices of the polytope,
so that there is always an optimal solution of this form.

\paragraph{Dual of shortest path.}
The dual of the shortest-path linear program is equivalent to the following:
\begin{lp}{maximize}{\pi(t) - \pi(s)}
  \pi(v)-\pi(u) & \le & w(u,v)
\end{lp}
There is one variable $\pi(u)$ for each vertex $u$.
An interpretation of this linear program is that the graph is being embedded on
a line, with $\pi(u)$ representing the position of the vertex $u$ on the line,
subject to the constraints that for every edge $(u,v)$, there is a ``string''
preventing vertex $v$ from being put more than $w(u,v)$ units further along the
line than vertex $u$.

Dijskstra's shortest path algorithm has a nice interpretation this way: replace
each edge in the graph by a string of the appropriate length, then, starting
with all vertices in a pile on the table, gradually lift up the vertex $s$,
letting the other vertices be pulled down towards the table by gravity.  As $s$
lifts, the strings will cause the other vertices to lift too.  A vertex $u$
will start lifting when the strings along the shortest path from $s$ to $u$ are
all ``tight''.

Linear programming duality is often useful in designing algorithms for
combinatorial optimization problems.

\end{document}

% Local Variables:
% End:
