polyhedra.tex

\chapter{Polyhedra and Integer Programming} 
\label{po:cha:polyhedra}


In this section we give definitions and fundamental facts about
polyhedra. An excellent reference for this topic is the book by
Schrijver~\cite{Schrijver86}.  A \emph{polyhedron} $P$ is a set of
vectors of the form $P=\{ x \in \setR^n \mid Ax \leq b\}$, for some matrix $A \in \setR^{m
  \times n}$ and some vector $b \in \setR^m$. We write $P(A,b)$.  The polyhedron
is \emph{rational} if both $A$ and $b$ can be chosen to be rational.

Recall that a  finite set $V\subseteq\setR^n$ is \emph{affinely independent} if for each $v\in
V$ one has $v\notin\affhull(V \textbackslash{} \{v\})$. This is equivalent to $(V - v) \setminus \{0\}$ being
linearly independent for each $v \in V$. The \emph{dimension} of $V$ is
 the size of the largest subset of $V$ which is affinely independent
 minus one:
\[ \dim(V) = \max\{ |U| - 1 \mid U \subseteq V \text{ is affinely independent} \} \]

\begin{example} 
\begin{itemize}
  \item $\dim(\setR^n) = n$
  \item $\dim(\{x\}) = 0$ for every $x\in\setR^n$
  \item $\dim(\emptyset) = -1$
\end{itemize}
\end{example}
Notice that $V\subseteq\setR^n$ is affinely independent if and only if $(V - v)
\setminus \{0\}$ is linearly independent for each $v \in V$.


\begin{definition}
\label{po:def:5}
An inequality $a^Tx\leq\beta$ is called an \emph{implicit equality} of
$Ax\leq b$ if each $x^* \in P(A,b)$ satisfies $a^Tx^* = \beta$. We denote the
subsystem  consisting of implicit equalities of $Ax\leq b$ by $A^=x\leq b^=$
and the subsystem consisting of the other inequalities by
$A^\leq x\leq b^\leq$. A constraint is \emph{redundant} if its removal from
$Ax\leq b$ does not change the set of feasible solution of $Ax\leq b$.  
\end{definition}

In the following, a vector $x$ satisfies $Ax < b$ if and only if
$a_i^T x < b_i$ for all $1\leq i\leq m$, where $a_1$,\ldots,$a_m$ are the rows of $A$.

\begin{lemma}
  \label{po:lem:3}
  Let $P(A,b)$ be a non-empty polyhedron.
  Then there exists an $x \in P(A,b)$ with $A^\leq x<b^\leq$. 
\end{lemma}
\begin{proof}
  Suppose that the inequalities in  $A^\leq x\leq b^\leq$ are $a_1^Tx\leq\beta_1
  ,\ldots,a_k^Tx\leq\beta_k$. For each $1\leq i\leq k$ there exists an $x_i \in P$ with
  $a_i^Tx_i<\beta_i$. Thus the point $x = 1/k (x_1+\cdots+x_k)$ is a point of
  $P(A,b)$ satisfying  $A^\leq x<b^\leq$. 
\end{proof}


\begin{lemma}
  \label{po:lem:2}
  Let $Ax\leq b$ be a system of inequalities. One has 
  \begin{displaymath}
    \affhull(P(A,b)) = \{ x \in \setR^n \mid A^=x = b^=\} = \{ x \in \setR^n \mid A^=x\leq b^=\}.
  \end{displaymath}
\end{lemma}
\begin{proof}
  Let $x_1,\ldots,x_t \in P(A,b)$ and suppose that $a^Tx\leq\beta$ is an
  implicit equality. Then since $a^Tx_i = \beta$ one has
  $a^T(\sum_{j=1}^t\lambda_ix_i) = \beta$. Therefore the inclusions $\subseteq$
  follow. 

  Suppose now that $x_0$ satisfies $A^=x\leq b^=$. Let $x_1 \in P(A,b)$
  with $A^\leq x_1<b^\leq$. If $x_0=x_1$ then $x_0 \in P(A,b) \subseteq
  \affhull(P(A,b))$.  Otherwise the line segment between $x_0$ and
  $x_1$ contains more than one point in $P$ and thus $x_0 \in
  \affhull(P)$. 
\end{proof}


\section{Decomposition theorem for polyhedra}





A nonempty set  $C\subseteq\setR^n$ is a \emph{cone} if $\lambda\, x + \mu\,y \in C$
for each $x,y\in C$ and $\lambda,\mu\in \setR_{\geq0}$. A cone  $C$ is \emph{polyhedral}
if $C = \{ x \in \setR^n \mid Ax\leq0\}$. A cone \emph{generated by} vectors
$x_1,\ldots,x_m \in \setR^n$ is a set of the form $C = \{ \sum_{i=1}^m \lambda_i x_i
\mid \lambda_i\in \setR_{\geq0}, \, i=1,\ldots,m\}$.   A point $x = \sum_{i=1}^m \lambda_i x_i$
with  $\lambda_i\in \setR_{\geq0}, \, i=1,\ldots,m$ is called a \emph{conic
  combination}   of the $x_1,\ldots,x_m$. The set of conic combinations of
$X$ is denoted by $\cone(X)$. 


\begin{theorem}[Farkas-Minkowsi-Weyl theorem]
  \label{po:thr:3}
  A convex cone is polyhedral if and only if it is finitely
  generated. 
\end{theorem}


\begin{proof}
  Suppose that $a_1,\ldots,a_m$ span $\setR^n$ and consider the cone $C = \{
  \sum_{i=1}^m \lambda_i a_i \mid \lambda_i\geq0, \, i=1,\ldots,m\}$.
  Let $b \notin C$.
  Then the system $A\lambda = b$, $\lambda \geq 0$ has no solution.
  By Theorem~\ref{conv:thr:12} (Farkas' lemma), this implies that there exists a $y\in\setR^n$
  such that $A^Ty \leq 0$ and $b^Ty > 0$.

  Suppose that the columns of $A$ which correspond to
  inequalities in $A^Ty\leq0$   that are satisfied  by $y$ with equality
  have rank $<n-1$.
  Denote these columns by $a_{i_1},\ldots,a_{i_k}$.  
  Then there exists a $v\neq0$ which is orthogonal to
  each of these columns and to $b$, i.e., $a_{i_j}^Tv = 0$ for each
  $j=1,\ldots,k$ and $b^Tv =0 $. 
  There also exists a column $a^*$ of $A$ which is not in the set
  $\{a_{i_1},\ldots,a_{i_k}\}$ such that $(a^*)^Tv>0$ since the columns of
  $A$ span $\setR^n$. Therefore there exists an $\epsilon>0$ such that 
  \begin{enumerate}[i)]
  \item $A^T(y + \epsilon \cdot v)\leq0$ 
  \item The subspace generated by the columns of $A$ which correspond
    to inequalities of $A^Tx\leq0$ which are satisfied by $y + \epsilon \cdot v$
    with equality strictly contains $\langle a_{i_1},\ldots,a_{i_k}\rangle$. 
  \end{enumerate}
  
  Notice that we have $b^Ty = b^T(y + \epsilon \cdot v)>0$. 

  Continuing this way, we obtain a solution of the form $y + u$ of
  $A^Tx\leq0$ such that one has $n-1$ linearly independent columns of $A$
  whose corresponding inequality in $A^Tx\leq0$ are satisfied with
  equality.   Thus we see that each $b$ which does
  not belong to $C$ can be separated from $C$ with an inequality of
  the form $c^Tx\leq0$  which
  is uniquely defined by $n-1$ linearly independent vectors from the set
  $a_1,\ldots,a_m$.  This shows that $C$ is polyhedral. 

  Suppose now that $a_1,\ldots,a_m$ do not span $\setR^n$. Then there  exist
  linearly independent vectors $d_1,\ldots,d_k$ such that each $d_i$ is
  orthogonal to each of the $a_1,\ldots,a_m$ and $a_1,\ldots,a_m,d_1,\ldots,d_k$
  spans $\setR^n$.   The cone generated by
  $a_1,\ldots,a_m,d_1,\ldots,d_k$ is polyhedral and thus of the form $Ax\leq0$
  with some matrix $A\in \setR^{m\times n}$. Suppose that  $\langle a_1,\ldots,a_m\rangle = \{x
  \in \setR^n \mid Ux = 0\}$.  Now $C = \{ x \in \setR^n \mid Ax\leq0, \, Ux = 0\}$
  and $C$ is polyhedral. 


  Now suppose that $C = \{ x \in \setR^n \mid a_1^Tx\leq0,\ldots,a_m^Tx\leq0\}$.
  The cone
  \[ C' := \cone(a_1,\ldots,a_m) = \{ \sum_{i=1}^m \lambda_i a_i \mid
  \lambda_i\geq0,\,i=1,\ldots,m\} \]
  is polyhedral and thus of the form $C' = \{ x
  \in \setR^n \mid b_1^Tx\leq0, \ldots,b_k^Tx\leq0\}$. Clearly,
  $\cone(b_1,\ldots,b_k)\subseteq C$  since $b_i^Ta_j\leq0$. Suppose now that $y \in
  C \textbackslash{} \cone(b_1,\ldots,b_k)$. Then, since $\cone(b_1,\ldots,b_k)$ is
  polyhedral, there exists a $w\in \setR^n$ with $w^Ty>0$ and $w^Tb_i\leq0$
  for each $i=1,\ldots,k$. From the latter we conclude that $w \in
  C'$. From $y \in C$ and $w \in C'$ we conclude $w^Ty\leq0$, which is a contradiction.
\end{proof}

A set of vectors $Q = \conv(X)$, where $X\subseteq\setR^n$ is finite is called a
\emph{polytope}. 

\begin{theorem}[Decomposition theorem for polyhedra]
  \label{po:thr:4}
  A set $P\subseteq\setR^n$ is a polyhedron if and only if $P = Q + C$ for some
  polytope $Q$ and a polyhedral cone $C$. 
\end{theorem}

\begin{proof}
  Suppose $P = \{ x \in \setR^n \mid Ax\leq b\}$ is a polyhedron. Consider the
  polyhedral cone 
  \begin{equation}
    \label{po:eq:6}
    \left\{\mat{x\\\lambda} \mid x \in \setR^n, \, \lambda \in \setR_{\geq0}; Ax -
      \lambda b\leq0\right\} 
  \end{equation}
  is generated by finitely many vectors $\mat{x_i\\\lambda_i}$,
  $i=1,\ldots,m$. By scaling with a positive number we may assume that
  each $\lambda_i\in \{0,1\}$.  Let $Q$ be the convex hull of the $x_i$ with
  $\lambda_i=1$ and let $C$ be the cone generated by the $x_i$ with
  $\lambda_i=0$. A point $x \in \setR^n$ is in $P$ if and only if $\mat{x\\1}$
  belongs to~\eqref{po:eq:6} and thus if and only if 
  \begin{displaymath}
    \mat{x\\1} \in
    \cone\left\{\mat{x_1\\\lambda_1},\ldots,\mat{x_m\\\lambda_m}\right\}. 
  \end{displaymath}
  Therefore $P = Q + C$. 


  Suppose now that $P = Q+C$ for some polytope $Q$ and a polyhedral
  cone $C$ with $Q = \conv(x_1,\ldots,x_m)$ and $C = \cone(y_1,\ldots,y_t)$. A
  vector $x_0$ is in $P$ if and only if 
  \begin{equation}
    \label{po:eq:7}
    \mat{x_0\\1} \in \cone\left\{\mat{x_1\\1},\ldots, \mat{x_m\\1},\mat{y_1\\0},\ldots,\mat{y_t\\0}     \right\}
  \end{equation}
By Theorem~\ref{po:thr:3} \eqref{po:eq:7} is equal to 
\begin{equation}
\label{po:eq:12}
  \left\{ \mat{x\\\lambda} \mid Ax - \lambda b \leq0\right\}
  \end{equation}
for some matrix $A$ and vector $b$.  Thus $x_0\in P$  if and only if
$Ax_0\leq b$ and thus $P$ is a polyhedron.

\end{proof}




\begin{figure}[htbp]
  \begin{center}
    %\resizebox{4cm}{4cm}{%
    \includegraphics{figures/PicPolyhedra1.pdf}
  %}
  \end{center}
  \caption{A polyhedron and its decomposition into $Q$ and $C$\label{po:fig:decomp}}
\end{figure}




Let $P = \{ x \in \setR^n \mid Ax\leq b\}$. The \emph{characteristic cone} is 
$\charcone(P) =\{ y \mid y+x \in P \text{ for all } x \in P\} = \{y \mid Ay
\leq0\}$. One has
\begin{enumerate}[i)]
\item $y \in \charcone(P)$ if and only if there exists an $x \in P$ such
  that $x + \lambda\,y \in P$ for all $\lambda\geq0$ 
\item $P + \charcone(P)=P$
\item $P$ is bounded if and only if $\charcone(P)=\{0\}$. 
\item If the decomposition of $P$ is $P = Q +C$, then $C = \charcone(P)$. 
\end{enumerate}



The \emph{lineality space} of $P$ is defined as $\charcone(P) \cap -
\charcone(P)$. A polyhedron is \emph{pointed}, if its lineality space is
$\{0\}$.






\section{Faces}
\label{po:sec:faces}

An inequality $c^Tx\leq\delta$    is called \emph{valid} for $P$ if each $x
\in P$ satisfies $c^Tx\leq\delta$. If in addition $(c^Tx = \delta) \cap P \neq\emptyset$,
then $c^Tx\leq\delta$ is a \emph{supporting inequality} and $c^Tx = \delta$ is a
supporting hyperplane. 

A set $F\subseteq\setR^n$ is called a \emph{face} of $P$ if there exists a
valid inequality $c^Tx\leq\delta$ for $P$ with $F = P \cap (c^Tx = \delta)$. 


\begin{lemma}
  \label{po:lem:4}
  A set $\emptyset \neq F \subseteq \setR^n$ is a face of $P$
  if and only if $F = \{ x \in P \mid A'x = b'\}$ for a subset $A'x\leq b'$ of $Ax\leq b$.
\end{lemma}

\begin{proof}
  Suppose that $F = \{ x \in P \mid A'x = b'\}$. Consider the vector $c =
  1^TA'$ and $\delta = 1^Tb'$. The inequality $c^Tx\leq \delta$ is valid for
  $P$. It is satisfied with equality by each $x \in F$. If $x' \in P\textbackslash{}
  F$, then there exists an inequality $a^Tx\leq\beta$ of $A'x\leq b'$ such
  that $ a^Tx' < \beta$ and consequently $c^Tx'<\delta$. 

  On the other hand, if $c^Tx\leq\delta$ defines the face $F$,
  then by the linear programming duality
  \[ \max\{ c^Tx \mid Ax\leq b \} = \min\{ b^T\lambda \mid A^T\lambda = c, \lambda \geq 0 \} \]
  there exists a $\lambda \in \setR^m_{\geq 0}$ such that $c=\lambda^TA$ and $\delta = \lambda^Tb$.
  Let $A'x\leq b'$ be the
  subsystem of $Ax\leq b$ which corresponds to strictly positive entries
  in $Ax\leq b$. One has $F = \{ x \in P \mid A'x = b'\}$. 
\end{proof}





A \emph{facet} of $P$ is an inclusion-wise maximal face $F$ of $P$
with $F\neq P$.  An inequality $a^Tx\leq\beta$ of $Ax\leq b$ is called
\emph{redundant} if $P(A,b) = P(A',b')$, where $A'x\leq b'$ is the system
stemming from $Ax\leq b$ by deleting $a^Tx\leq\beta$.  A system $Ax\leq b$ is
irredundant if $Ax\leq b$ does not contain a redundant inequality.

\begin{lemma}
  \label{po:lem:1}
  Let $Ax\leq b$ be an irredundant system. 
  Then a set $F\subseteq P$ is a facet if and only if it is
  of the form $F = \{ x \in P \mid a^Tx = \beta\}$ for an
  inequality $a^Tx\leq\beta$ of $A^\leq x\leq b^\leq$. 
\end{lemma}


\begin{proof}
  Let $F$ be a facet of $P$. Then $F = \{x \in P \mid c^Tx\leq\delta\}$ for a valid
  inequality $c^Tx\leq\delta$ of $P$. There exists a $\lambda \in \setR_{\geq0}^m$ with
  $c=\lambda^TA$ and $\delta=\lambda^Tb$.  There exists an inequality  $a^Tx\leq\beta$ of
  $A^\leq x\leq b^\leq$ whose corresponding entry in $\lambda$ is strictly
  positive. Clearly $F\subseteq\{x \in P \mid a^Tx=\beta\}\subset P$. Since $F$ is an
  inclusion-wise maximal face one has $F = \{x \in P \mid a^Tx=\beta\}$. 
  
  Let $F$ be of the form $F = \{ x \in P \mid a^Tx = \beta\}$ for an inequality
  $a^Tx\leq\beta$ of $A^\leq x\leq b^\leq$.  Clearly $F \neq \emptyset$ since the system $Ax\leq b$ is
  irredundant. If $F$ is not a facet, then $F\subseteq F'=\{ x \in P \mid a'^Tx = \beta'\}$
  with another inequality $a'^Tx\leq\beta'$ of $A^\leq x\leq b^\leq$. Let $x^*\in \setR^n$ be a point with
  $a^Tx^*>\beta$ and which satisfies all other inequalities of $Ax\leq b$. Such an $x^*$
  exists, since $Ax\leq b$ is irredundant.  Let $\wt{x}\in P$ with
  $A^\leq\wt{x}<b^\leq$.  There exists   a point $\wb{x}$ on the
  line-segment $\wb{\wt{x}x^*}$ with   $a^T\wb{x}=\beta$.  This point is then
  also in $F'$ and thus $a'^Tx = \beta'$ follows. This shows that
  $a'^Tx^*>\beta'$
  and thus $a^Tx\leq\beta$ can be
  removed from the system.  This is a contradiction to 
   $Ax\leq b$ being irredundant.  
\end{proof}




\begin{lemma}
  \label{po:lem:5}
  A face $F$ of $P(A,b)$ is inclusion-wise minimal if and only if it
  is of the form $F = \{ x \in \setR^n \mid A'x=b'\}$ for some subsystem
    $A'x\leq b'$ of $Ax\leq b$. 
\end{lemma}


\begin{proof}
  Let $F$ be a minimal face of $P$ and let $A'x\leq b'$ a the subsystem
  of inequalities of $Ax\leq b$ with $F = \{ x \in P \mid A'x=b'\}$. Suppose that
  $F \subset \{x\in\setR^n  \mid A'x=b'\}$ and let $x_1 \in \setR^n \textbackslash{} P$ satisfy
  $A'x_1=b'$ and  $x_2 \in F$.  There exists ``a first''  inequality $a^Tx\leq\beta$ of
  $Ax\leq b$ which is ``hit'' by the line-segment  $\wb{x_2x_1}$. Let $x^* =
  \wb{x_2x_1}\cap(a^Tx=\beta)$. Then $x^*\in F$ and thus $F \cap (a^Tx=\beta) \neq
  \emptyset$. But $F \supset F \cap (a^Tx=\beta)$ since $a^Tx \leq\beta$ is not an inequality of
  $A'x\leq b'$. This is a contradiction to the minimality of $F$. 

  
  Suppose that $F$ is a face with $F = \{x \in \setR^n \mid A'x= b'\}
  = \{x \in P \mid A'x=b'\}$ for a subsystem $A'x\leq b'$ of $Ax\leq
  b$. Suppose that there exists a face $\wt{F}$ of $P$ with $\emptyset
  \subset \wt{F}\subset F$. By Lemma~\ref{po:lem:4} $\wt{F} = \{ x \in
  P \mid A'x=b', A^*x=b^*\}$, where $A^*x\leq b^*$ is a sub-system of
  $Ax\leq b$ which contains an inequality $a^Tx\leq\beta$ such that
  there exists an $x_1,x_2 \in F$ with $a^Tx_1<\beta$ and
  $a^Tx_2\leq\beta$.  The line $\ell(x_1,x_2) = \{ x_1 +
  \lambda(x_2-x_1) \mid \lambda \in \setR\}$ is contained in $F$ but
  is not contained in $a^Tx\leq\beta$. This shows that $F$ is not
  contained in $P$ which is a contradiction.
\end{proof}

Exercise~\ref{item:19} asks for a proof of the following corollary. 
\begin{corollary}
  \label{co:8}
  Let $F_1$ and $F_2$ be two inclusion-wise minimal faces of
  $P=\{x\in\setR^n\colon Ax \leq b\}$, then $\dim(F_1) = \dim(F_2)$.
\end{corollary}

We say that a polyhedron contains a line $\ell(x_1,x_2)$ with $x_1
\neq x_2 \in P$ if $\ell(x_1,x_2) = \{ x_1 + \lambda(x_2-x_1) \mid
\lambda \in \setR \}\subseteq P$. A \emph{vertex} of $P$ is a
$0$-dimensional face of $P$. An \emph{edge} of $P$ is a
$1$-dimensional face of $P$.






\begin{example}
Consider a linear program $\min\{c^Tx \colon Ax = b,\, x\geq0\}$. A basic
feasible solution  defined by the basis $B\subseteq\{1,\ldots,n\}$ is a vertex of
the polyhedron $P = \{x \in \setR^n \colon Ax = b,\, x\geq0\}$. This can be seen
as follows. The inequality $a^Tx\geq0$ is valid for $P$, where $a_B =
\mathbf{0}$ and $a_{\overline{B}} = \mathbf{1}$. The inequality is
satisfied with equality by a point $x^* \in P$ if and only if
$x^*_{\overline{B}} = \mathbf{0}$. Since the columns of $A_B$ are
linearly independent, as $B$ is a basis, the unique point which
satisfies $a^Tx\geq0$ with equality is the basic feasible solution  
\end{example}

In exercise~\label{item:18} you are asked to show that the simplex
method can be geometrically interpreted as a walk on the graph $G =
(V,E)$, where $V$ is the set of basic feasible solutions and $uv\in  E$
if and only if $\conv\{u,v\}$ is a $1$-dimensional face of the
polyhedron defined by the linear program. 



\subsection{Integer Programming}
\label{sec:integer-programming}

An \emph{integer program} is a problem of the form 
\begin{displaymath}
  \begin{array}{c}
    \max c^Tx \\
    Ax\leq b \\
    x \in \setZ^n,
  \end{array}
\end{displaymath}
where $A \in \setR^{m\times n}$ and $b \in \setR^m$. 




\begin{figure}[htbp]
  \begin{center}
   \includegraphics{figures/PicPolyhedra2.pdf}
\label{fig:inthull}
  \end{center}
  \caption{This picture illustrates a polyhedron $P$ an objective
    function vector $c$ and optimal points $u,v$ of the integer
    program and the relaxation respectively. }
\end{figure}



The difference to linear
programming is the \emph{integrality constraint} $x \in \setZ^n$. This
powerful constraint  allows to model discrete choices but, at the same
time, makes an integer program much more difficult to solve than a
linear program. In fact one can show that integer programming is
NP-hard, which means that it is \emph{in theory} computationally
intractable. However, integer programming has nowadays become an
important tool to solve difficult industrial optimization problems
efficiently. In this chapter, we characterize some integer programs
which are easy to solve, since the \emph{linear programming
  relaxation} $\max\{c^Tx \colon Ax\leq b\}$ yields already an optimal
integer solution. The following observation is crucial. 

\begin{theorem}
  \label{thr:14}
  Suppose that the optimum solution $x^*$ of the linear programming
  relaxation $\max\{c^Tx \colon Ax\leq b\}$  is integral, i.e., $x^* \in
  \setZ^n$, then $x^*$ is also an optimal solution to the integer
  programming problem $\max\{c^Tx \colon Ax\leq b, \, x \in \setZ^n\}$
\end{theorem}

Before we present an example for the power of integer programming we
recall the definition of an undirected graph. 

\begin{definition}[Undirected graph, matching] 
  An \emph{undirected graph} is a tuple $G = (V,E)$ where $V$ is a
  finite set, called the \emph{vertices} and $E\subseteq\binom{V}{2}$ is the
  set of \emph{edges} of $G$.  A \emph{matching} of $G$ is a subset
  $M\subseteq E$ such that for all $e_1\neq e_2\in M$ one has $e_1\cap e_2 = \emptyset$. 
\end{definition}


We are interested in the solution of the following problem, which is
called \emph{maximum weight matching} problem. Given a graph $G =
(V,E)$ and a weight function $w:E\to\setR$, compute a matching with
maximum weight $w(M) = \sum_{e \in M} w(e)$. 

For a vertex $v \in V$, the set $\delta(v) = \{e \in E \colon v \in e\}$ denotes
the \emph{incident} edges to $v$. 

The maximum weight matching problem  can now be modeled as an integer
program as follows. 
\begin{displaymath}
  \begin{array}{c}
    \max \sum_{e \in E} w(e) x(e) \\
    v \in V: \, \sum_{e \in \delta(v)} x(e)\leq1 \\
    e \in E:\, 0\leq x(e) \\
    x \in \setZ^{|E|}.
  \end{array}
\end{displaymath}

Clearly, if an integer vector $x \in \setZ^n$ satisfies the constraints
above, then this vector is the \emph{incidence vector}  of a matching of
$G$. In other words, the integral solutions to the constraints above
are the vectors $\{\chi^M \colon M \text{ matching of }G\}$, where $\chi^M(e)
= 1$ if $e \in M$ and $\chi^M(e)=0$ otherwise. 

  
\subsection{Integral Polyhedra}


In this section we derive sufficient conditions on an integer program
to be solved easily by an algorithm for linear programming. A central
notion is the one of an integral polyhedron. A rational polyhedron $P$
is called \emph{integral} if each minimal face  of $P$ contains an
integer point.  

\begin{theorem}
  \label{po:thr:5}
  Let $P = \{x \in \setR^n \mid Ax\leq b\}$  be a rational nonempty  polyhedron with
  vertices. $P$ is integral if and only if for all integral vectors $c
  \in \setZ^n$ with $\max\{c^Tx \mid x \in P\}<\infty$ one has $\max\{c^Tx \mid x
  \in P\} \in \setZ$. 
\end{theorem}

\begin{proof}
  Let $P$ be integral and $c \in \setZ^n$ with
  $\max\{c^Tx\mid x\in P\}=\delta<\infty$. Since the face    $F=\{x\in P\mid c^Tx=\delta\}$
  contains an integer point it follows   that $\delta\in\setZ$.  

  On the other hand let $x^*$ be a vertex of $P$ and assume that $x^*(i) \notin
  \setZ$. There exists a subsystem $A'x\leq b'$ of $Ax\leq b$ with $A'\in\setR^{n\times n}$,
  $A'$ nonsingular and $A'x^*=b'$. Let $a_1,\ldots,a_n$ be the rows of
  $A'$. Since $A'$ is invertible, there exists an integer vector $c \in
  \cone(a_1,\ldots,a_n)\cap\setZ^n$ such that $c\pm e_i \in
  \cone(a_1,\ldots,a_n)$. The point $x^*$ maximizes both $c^Tx$ and
  $(c+e_i)^Tx$. Clearly not both numbers $c^Tx^*$ and
  $(c+e_i)^Tx^*$ can be integral, which is a contradiction. 
\end{proof}



\begin{lemma}
  \label{po:lem:6}
  Let $A\in \setZ^{n\times n}$ be an integral and invertible matrix. One has
  $A^{-1}b \in \setZ^n$ for each $b \in \setZ^n$ if and only if $\det(A)=\pm 1$.
\end{lemma}


\begin{proof}
  Recall Cramer's rule which says $A^{-1} = 1/\det(A) \wt{A}$, where
  $\wt{A}$ is the adjoint matrix of $A$. Clearly $\wt{A}$ is
  integral. If $\det(A) = \pm 1$, then $A^{-1}$ is an integer matrix. 

  If $A^{-1}b$ is integral for each $b \in \setZ^n$, then $A^{-1}$ is an
  integer matrix. We have $1=\det(A\cdot A^{-1})=\det(A)\cdot\det(A^{-1})$.
  Since $A$ and $A^{-1}$ are integral it follows that $\det(A)$ and
  $\det(A^{-1})$ are integers. The only divisors of one in the integers
  are $\pm 1$. 
\end{proof}



A matrix $A \in \setZ^{m\times n}$ with $m\leq n$ is called \emph{unimodular} if
each $m\times m$ sub-matrix has determinant $0,\pm1$. 

\begin{theorem}
  \label{po:thr:14}
  Let $A \in \setZ^{m\times n}$ be an integral matrix of full row-rank. The
  polyhedron defined by $Ax=b, x\geq0$ is integral for each $b \in \setZ^m$
  if and only if $A$ is unimodular. 
\end{theorem}


\begin{proof}
  Suppose that $A$ is unimodular and $b$ is integral. The polyhedron
  $P = \{ x \in \setR^n \mid Ax=b, \, x\geq0\}$ does not contain a line and
  thus has vertices. A vertex $x^*$ is of the form  $x^*_B= A_B^{-1}b$
  and $x^*_{\wb{B}}=0$, where $B\subseteq\{1,\ldots,n\}$ is a basis. Since $A_B$
  is unimodular one has $x^* \in \setZ^n$. 

  If $A$ is not unimodular, then there exists a basis $B$ with
  $\det(A_B) \neq \pm1$. By Lemma~\ref{po:lem:6} there exists an integral $b
  \in \setZ^n$ with $(A_B)^{-1}b \notin \setZ^m$. Let $\lambda$ be the maximal
  absolute value of a component of $A_B^{-1}b$. Then $b' =  \lceil\lambda\rceil A_B \mathbf{1}
  +b$ is an integral vector with $ A_B^{-1}b' = \lceil\lambda\rceil \mathbf{1}+
  A_B^{-1}b \geq0$ and $A_B^{-1}b' \notin \setZ^m$.  The
  polyhedron $P = \{ x \in \setR^n \mid Ax = b', \, x\geq0\}$ has thus a fractional
  (non-integer) vertex.   
\end{proof}




An integral matrix $A \in \{0 , \pm 1\}^{m\times n}$ is called \emph{totally
  unimodular} if each of its square sub-matrices has determinant
$0,\pm1$. 

\begin{theorem}[Hoffman-Kruskal Theorem]
  \label{po:thr:16}
  Let $A\in \setZ^{m\times n}$ be an integral matrix. The polyhedron $P = \{ x
  \in \setR^n \mid Ax\leq b, \, x\geq0\}$ is integral for each integral $b \in
  \setZ^m$ if and only if $A$ is totally unimodular. 
\end{theorem}


\begin{proof}
  The polyhedron $P = \{ x  \in \setR^n \mid Ax\leq b, \, x\geq0\}$ is integral
  if and only if the polyhedron $Q = \{ z \in \setR^{n+m} \mid (A|I)z = b,
  \, z\geq0\}$ is integral. The assertion thus follows from
  Theorem~\ref{po:thr:14}. 
\end{proof}


If an integral polyhedron has vertices, then an optimal vertex
solution of a  linear program over this polyhedron is integral.  

\section{Applications of total unimodularity}

\subsubsection{Bipartite matching} 

% An undirected graph $G=(V,E)$ is a tuple, where $V$ is a finite set
% and $E$ is a set of unordered pairs of $V$. The set $V$ is called
% \emph{nodes} and the set $E$ are the \emph{edges} of $G$. We write
% $uv$ in short for the edge $\{u,v\}\subseteq V$. 

A graph is
\emph{bipartite}, if $V$ has a partition into sets $A$ and $B$ such
that each  edge $uv$ satisfies $u\in A$ and $v \in B$.
Recall that $\delta(v)$ is the set of edges incident to the vertex $v\in V$,
that is $\delta(v) = \{ e\in E \mid v\in e \}$.

A \emph{matching} of $G$ is a subset $M\subseteq E$ such that $e_1\cap e_2 = \emptyset$
holds for each $e_1\neq e_2\in M$. Let $c:E\longrightarrow\setR$ be a weight function. The
weight of a matching is defined as $c(M) = \sum_{e \in M}c(e)$.  The
\emph{weighted matching problem } is  defined as follows. Given a
graph $G = (V,E)$ and edge-weights $c:E\longrightarrow\setR$, compute a matching $M$
of $G$ with $c(M)$ maximal.


%We have already seen how to compute a maximum weight matching of a
%bipartite graph in polynomial time with a polynomial minimum cost
%network flow algorithm. We now take a different perspective. 
We now define
an \emph{integer program} for this problem and show that, for
bipartite graphs, an optimal vertex of the corresponding linear
program is integral. 


The idea is as follows. We have decision variables $x(e)$ for each
edge $e \in E$. We want to model the characteristic vectors $\chi^M\in
\{0,1\}^E$  of matchings, where $\chi^M(e)=1$ if  $e\in M$  and $\chi^M(e)=0$
otherwise. This is achieved with the following set of constraints. 
\begin{equation}
  \label{po:eq:3}
  \begin{array}{rcll}
    \sum_{e \in \delta(v)} x(e) &\leq&1, & \forall v \in V \\
    x(e) &\geq&0, & \forall e \in E. 
  \end{array}
\end{equation}

Clearly, the set of vectors $x \in \setZ^E$ which satisfy the
system~\eqref{po:eq:3} are exactly the characteristic vectors of
matchings of $G$. The matrix $A \in \{0,1\}^{V\times E}$ which is defined as 
\begin{displaymath}
  \label{po:sec:bipartite-matching}
  A(v,e) = 
  \begin{cases}
    1 & \text{ if } v \in e,\\
    0 & \text{ otherwise}
  \end{cases}
\end{displaymath}
is called \emph{node-edge incidence matrix} of $G$. 

\begin{lemma}
  \label{po:lem:9}
  If $G$ is bipartite, the node-edge incidence matrix of $G$ is
  totally unimodular. 
\end{lemma}

Lemma~\ref{po:lem:9} implies that each vertex of the polytope $P$ defined
by the inequalities~\eqref{po:eq:3} is integral. Thus an optimal vertex
of the linear program $\max\{c^Tx \mid x \in P\}$ corresponds to a
maximum weight matching. 



\begin{proof}[Proof of Lemma~\ref{po:lem:9}]
  Let  $G = (V,E)$ be a bipartite graph with bi-partition $V=V_1\cup V_2$. 
  
  Let $A'$ be a $k\times k$ sub-matrix of $A$. We are interested in the
  determinant of $A$. Clearly, we can assume that $A$ does not contain
  a column which contains only one $1$, since we simply consider the
  sub-matrix $A''$ of $A'$, which emerges from developing the
  determinant of $A'$ along this column. The determinant of $A'$ would
  be $\pm1\cdot \det(A'')$.
  
  Thus we can assume that each column contains exactly two ones. Now
  we can order the rows of $A'$ such that the first rows correspond to
  vertices of $V_1$ and then follow the rows corresponding to vertices
  in $V_2$. This re-ordering only affects the sign of the
  determinant. By summing up the rows of $A'$ in $V_1$ we obtain
  exactly the same row-vector as we get by summing up the rows of $A'$
  corresponding to $V_2$. This shows that $\det(A')=0$. 
\end{proof}



\subsubsection{Flows}

Let $G=(V,A)$ be a directed graph, see
chapter~\ref{cha:short-paths-graphs}.
The \emph{node-edge incidence matrix of a directed graph}
is a matrix $A \in \{0,\pm1\}^{V\times E}$ with 
\begin{equation}
  \label{po:eq:8}
  A(v,a) = 
  \begin{cases}
    1 & \text{ if } v \text{ is the starting-node of } a, \\
    -1 & \text{ if } v \text{ is the end-node of } a, \\
    0  & \text{ otherwise.}
  \end{cases}
\end{equation}


A \emph{feasible flow} $f$  of $G$ with capacities $u$ and in-out-flow $b$ is then
a solution $f \in \setR^A$ to the system $A\,f=b, \, 0\leq f\leq u$.  

\begin{lemma}
  \label{po:lem:10}
  The node-edge incidence matrix $A$ of a directed graph  is totally
  unimodular.  
\end{lemma}


\begin{proof}
  Let $A'$ be a $k\times k$ sub-matrix of $A$. Again, we can assume that in
  each column we have exactly one $1$ and one $-1$. Otherwise, we
  develop the determinant along a column which does not have this
  property.  But then, the $A'$ is singular, since adding up all rows
  of $A'$ yields the $0$-vector. 
\end{proof}
  

A consequence is that, if the $b$-vector and the capacities $u$ are
integral and an optimal flow exists, then there exists an integer
optimal flow. 
%We have seen that this follows from the cycle-cancelling
%algorithm, but total unimodularity gives another simple and elegant
%proof of this fact.  




\subsection{Further applications of polyhedral theory}
\label{po:sec:furth-appl-polyh}


\subsubsection{Doubly stochastic matrices}


A matrix $A \in \setR^{n\times n}$ is \emph{doubly stochastic} if it satisfies
the following linear constraints 
\begin{equation}
  \label{po:eq:9}
  \begin{array}{rcll}
    \sum_{i=1}^n A(i,j) & = & 1, & \forall j=1,\ldots,n\\
    \sum_{j=1}^n A(i,j) & = & 1, & \forall i=1,\ldots,n\\
    A(i,j)       & \geq & 0, & \forall 1 \leq i,j\leq n.
  \end{array}
\end{equation}

A permutation matrix is a matrix which contains exactly one $1$ per
row and column, where the other entries are all $0$. 

\begin{theorem}
  \label{po:thr:17}
  A matrix $A \in \setR^{n\times n}$ is doubly stochastic if and only if $A$ is
  a  convex combination  of permutation matrices. 
\end{theorem}

\begin{proof}
  Since a permutation matrix satisfies the constraints~\eqref{po:eq:9},
  then so does a convex combination of these constraints. 


  On the other hand it is enough to show that each vertex of the
  polytope defined by the system~\eqref{po:eq:9} is integral and thus a
  permutation matrix. However, the matrix defining the
  system~\eqref{po:eq:9}  is the node-edge incidence matrix of the
  complete bipartite graph having $2n$ vertices. Since such a matrix
  is totally unimodular, the theorem follows. 
\end{proof}





\subsection{The matching polytope}
\label{po:sec:matching-polytope}


We now come to a deeper theorem concerning the convex hull of
matchings. We mentioned several times in the course that the maximum
weight matching problem can be solved in polynomial time. We are now
going to show a theorem of Edmonds~\cite{Edmonds65b} which provides a
complete description of the matching polytope and present the
proof by Lov\'asz~\cite{Lovasz79}. 

Before we proceed let us inspect the symmetric difference $M_1\Delta M_2$
of two matchings of a graph $G$. If a vertex is adjacent to two edges
of $M_1\cup M_2$, then one of the two edges belongs to
$M_1$ and one belongs to $M_2$. Also, a vertex can never be adjacent
to three edges in $M_1 \cup M_2$. Edges which are both in $M_1$ and $M_2$
do not appear in the symmetric difference. We therefore have the
following lemma. 

\begin{lemma}
  \label{po:lem:11}
  The symmetric difference $M_1\Delta M_2$ of two matchings decomposes
  into node-disjoint  paths and cycles, where the edges on these paths
  and cycles alternate between $M_1$ and $M_2$. 
\end{lemma}



The \emph{Matching polytope} $P(G)$ of an undirected graph $G = (V,E)$
is the convex hull of incidence vectors  $\chi^M$ of matchings $M$ of
$G$. 


  
\begin{figure}[htbp]
  \centering 
   \includegraphics{figures/PicPolyhedra3.pdf}
  \caption{Triangle}
  \label{po:fig:triangle}
\end{figure}
  

The incidence vectors of matchings are exactly the $0/1$-vectors that
satisfy the following system of equations. 

\begin{equation}
\label{po:eq:10}
  \begin{array}{rcll}
     \sum_{e \in \delta(v)} x(e) & \leq &  1 & \forall v \in V\\
        x(e)& \geq & 0 &    \forall e \in E. 
  \end{array}
\end{equation}

However the triangle (Figure~\ref{po:fig:triangle}) shows that  the
corresponding polytope is not integral. The objective function $\max
\mathrm{1}^Tx$ has value $1.5$. However, one can show that a maximum
weight matching of an undirected graph can be computed in polynomial
time which is a result of Edmonds~\cite{Edmonds65}. 


The following (Figure~\ref{po:fig:edmonds}) is an illustration of an
Edmonds inequality. Suppose that $U$ is an odd subset of the nodes $V$
of $G$ and let $M$ be a matching of $G$. The number of edges of $M$
with both endpoints in $U$ is bounded from above by $\lfloor|U|/2\rfloor$. 

Thus the following inequality is valid for the integer points of the
polyhedron defined by~\eqref{po:eq:10}. 

\begin{equation}
  \label{po:eq:11}
  \sum_{e \in E(U)} x(e) \leq\lfloor|U|/2\rfloor,\quad \quad \text{ for each } U\subseteq V,
  \quad |U| \equiv 1 \pmod{2}. 
\end{equation}


\begin{figure}[htbp]    
  \begin{center}
 \includegraphics{figures/PicPolyhedra4.pdf}
\end{center}
\caption{Edmonds inequality.}
  \label{po:fig:edmonds}
\end{figure}


The goal of this lecture is a proof of the following theorem. 

\begin{theorem}[Edmonds 65]
\label{po:thr:18}
  The matching polytope is described by the following inequalities:
  \begin{enumerate}[i)]
  \item $x(e) \geq0$ for each $e \in E$,
  \item $\sum_{e \in \delta(v)} x(e) \leq 1$ for each $v \in V$,
  \item $\sum_{e \in E(U)} x(e) \leq \lfloor |U|  /2 \rfloor$ for each $U\subseteq V$
    %\fromSlide*{2}{ Gomory Cut!} 
  \end{enumerate}
\end{theorem}


\begin{lemma}
\label{po:lem:11}
  Let $G=(V,E)$ be connected and 
  let $w:E\longrightarrow\setR_{>0}$ be a weight-function.  Denote the set of maximum
  weight matchings of $G$ w.r.t. $w$ by $\eM(w)$. Then one of the following statements
  must be true:
  \begin{enumerate}[i)]
  \item $\exists\,v \in V$ such that $\delta(v) \cap M \neq \emptyset$ for each $M \in \eM(w)$
  \item $|M| =   \lfloor|V| /2\rfloor$ for each $M \in \eM(w)$ and $|V|$ is odd.
  \end{enumerate}
\end{lemma}


\begin{proof}
Suppose both $i)$ and $ii)$ do not hold.
Then there exists ${ M}\in \eM(w)$ leaving two exposed nodes $u$ and
$v$.  Choose $ M$ such that the  minimum  distance between   two exposed nodes
  $u,v$ is  minimized. 


Now let $t$ be on shortest path from $u$ to $v$. The vertex $t$ cannot
be exposed. 
\begin{figure}[htbp]
  \centering
    \begin{center}    
    \includegraphics{figures/PicPolyhedra5.pdf}
  \end{center}
  \caption{Shortest path between $u$ and $v$. }
  \label{po:fig:short}
\end{figure}


 Let ${ M'} \in \eM(w)$ leave $t$ exposed. 
 Both $u$ and $v$ are covered by  ${ M'}$ because the distance to
 $u$ or $v$ from $t$ is smaller than the distance of $u$ to $v$. 
 
 Consider the symmetric difference ${ M} \triangle { M'}$ which  decomposes into
 node disjoint paths and   cycles. 
The  nodes $u, \, v$ and $t$ have degree one in ${M}\triangle{ M'}$. Let 
$P$ be a  path with endpoint $t$ in ${ M}\triangle{ M'}$


\begin{figure}
  \centering
    
\includegraphics{figures/PicPolyhedra6.pdf}
\caption{Swapping colors. }\label{fig:2}
\end{figure}




 If we swap colors on $P$, see Figure~\ref{fig:2}, we obtain matchings  ${\wt{M}}$ and
 ${\wt{M'}}$ with 
 $w({ M}) + w({ M'}) = w({ \wt{M}})+w({  \wt{M'}}) $ and thus
 ${ \wt{M}} \in \eM(w)$.  

 The node $t$ is exposed in ${\wt{M}}$ and $u$ or $v$ is exposed  in
  ${\wt{M}}$. This is a  
contradiction to $u$ and $v$ being shortest distance exposed
  vertices 


\end{proof}



\begin{proof}[Proof of Theorem~\ref{po:thr:18}]

Let $w^Tx\leq\beta$ be a \emph{facet} of $P(G)$, we need to show that this
facet it is of the form
  \begin{enumerate}[i)]
  \item $x(e)\geq0$ for some $e \in E$\label{po:item:1}
  \item $\sum_{e \in \delta(v)} x(e)\leq1$  for some $v \in V$\label{po:item:2}
  \item $\sum_{e \in E(U)} x(e)\leq \lfloor|U|/2\rfloor$ for some $U \in P_{odd}$\label{po:item:3}
  \end{enumerate}
  
  
  To do so, we use the following method: One of the inequalities
  \ref{po:item:1}), \ref{po:item:2}), \ref{po:item:3}) is satisfied with
  equality by each $\chi^M, \,M \in \eM(w)$. This establishes the claim
  since the matching polytope is full-dimensional and a facet is a
  maximal face. 

  




  If $w(e)<0$ for some $e \in E$, then each $M \in \eM(w)$
  satisfies $e \notin M$ and thus satisfies $x(e)\geq0$ with equality. 

  Thus we can assume that  $w\geq0$. 
  
  Let $G^*=(V^*,E^*)$ be the graph induced by edges $e$ with $w(e)>0$.  Each $M
  \in \eM(w)$ contains maximum weight matching $M^* = M \cap E^*$ of
  $G^*$ w.r.t.  $w^*$. 

  If $G^*$ is not \emph{connected }, suppose that
  $V^*=V_1\cup V_2$, where $V_1\cap V_2 = \emptyset$ and $V_1,V_2 \neq\emptyset$ and there
  is no edge connecting $V_1$ and $V_2$, then
  $w^Tx\leq\beta$ can be written as the sum of $w_1^Tx\leq\beta_1$ and
  $w_2^Tx\leq\beta_2$, where $\beta_i$ is the maximum weight of a matching in
  $V_i$ w.r.t. $w_i$, $i=1,2$, see Figure~\ref{blobs}. This would also contradict the fact
  that $w^Tx\leq\beta$ is a facet, since it would follow from the previous
  inequalities and thus would  be a redundant
  inequality.
    
  \begin{figure}
    \centering
  
        
    \includegraphics{figures/PicPolyhedra7.pdf}
    \caption{$G^*$ is connected. }\label{blobs}
  \end{figure}
   
      Now we can use Lemma~\ref{po:lem:11} for $G^*$. 
      
      \begin{enumerate}[i)]
      \item $\exists v$ such that $\delta(v) \cap M = \emptyset$ for each $M \in
        \eM(w)$. This means that each $M$ in $\eM(w)$ satisfies
        \begin{displaymath}
          \sum_{e \in          \delta(v)} x(e)\leq1 \quad \text{ {with equality}}
         \end{displaymath}
      \item $|M\cap E^*| =   \lfloor|V^*| /2\rfloor$ for each $M \in \eM(w)$ and $|V^*|$
        is odd. This means that each $M$ in $\eM(w)$ satisfies
        \begin{displaymath}
           \sum_{e \in E(V^*)          } x(e)\leq \lfloor|V^*|/2\rfloor \quad \text{
             {with equality}} 
        \end{displaymath}
      \end{enumerate}

    \end{proof}


\subsection*{Exercises}

\begin{enumerate}
\item 
  Each nonempty  polyhedron $P\subseteq\setR^n$ can be represented as $ P = L + Q$,
  where  $L\subseteq\setR^n$ is a linear space and $Q\subseteq\setR^n$ is a pointed
  polyhedron.   \label{po:ex:1}
\item Let $P\subset\setR^n$ be a polytope and $f:\setR^n\to\setR^m$ a linear map.
  \begin{enumerate}[i)]
  \item Show that $f(P)$ is a polytope.
  \item Let $y\in\setR^m$ be a vertex of $f(P)$. Show that there is a vertex $x\in\setR^n$ of $P$
    such that $f(x) = y$.
  \end{enumerate}
\item 
  Let $A \in \setR^{m\times n}$ and $b \in \setR^m$ and consider the polyhedron
  $P = P(A,b)$. Show that $\dim(P) = n - \rank(A^=)$.   \label{po:ex:2}
\item 
  \begin{enumerate}[i)]
  \item 
  Show that the dimension of each minimal face of a polyhedron $P$ is
  equal to $n - \rank(A)$. 
  \item
  Show that a polyhedron has a vertex if and only if the polyhedron
  does not contain a line. 
\end{enumerate}   \label{po:ex:3}
\item Show that the affine  dimension of the minimal faces of a 
  polyhedron $P = \{x \in \setR^n \colon Ax\leq b\}$ is invariant. \label{item:19}
\item 
  In this exercise you can assume that a linear program $\max\{c^Tx \mid
  Ax\leq b \}$ can be solved in polynomial time. Suppose that $P(A,b)$
  has vertices and that the linear program is bounded. Show how to
  compute an optimal \emph{vertex} solution of the linear
  program in polynomial time.    \label{po:ex:4}
\item  Let $P = \{x \in \setR^n \colon Ax = b, \, x\geq0\}$ be a polyhedron,
  where $A \in \setR^{m\times n}$ has full row-rank. Let $B_1,B_2$ be two bases
  such that $|B_1\cap B_2| = m-1$ and suppose that the associated basic
  solutions $x^*_1$ and $x^*_2$ are feasible. Show that, if
  $x_1\neq x_2$, then   $\conv\{x_1^*,x_2^*\}$ is a $1$-dimensional face
  of $P$. \label{item:18} 
\end{enumerate}





\bibliographystyle{abbrv}

\bibliography{mybib,papers,books,my_publications}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "lecture"
%%% End: