\begin{slide}{Travelling Salesman als MIP}

(dieses Bsp. aus Papadimitriou und Steiglitz:\\
\emph{Combinatorial Optimization}, Prentice Hall 1982)

Travelling Salesman:
\begin{itemize}\itemsep 1pt
\item Instanz: Gewichte $w : \{1,\ldots,n\}^2\to \RR_{\ge 0} \cup \{+\infty\}$
  und Schranke $s\in R_{\ge 0}$
\item Lösung: Rundreise mit Gesamtkosten $\le s$ 
\end{itemize}

Ansatz zur Modellierung:
\begin{itemize}\itemsep 1pt
\item Variablen $x_{i,j} \in\{0,1\}$, Bedeutung: 
  $x_{i,j}=1 \iff$ Kante $(i,j)$ kommt in Rundreise vor
\item Zielfunktion?
\item Constraints --- reicht das: $\sum_i x_{i,j}=1, \sum_j x_{i,j} = 1$ ?
\end{itemize}

\end{slide}

\begin{slide}{Travelling Salesman als MIP (II)}

Miller, Tucker, Zemlin: \emph{Integer Programming Formulation
and Travelling Salesman Problem} JACM 7(1960) 326--329

\begin{itemize}
\item zusätzliche Variablen $u_1, \ldots, u_n \in \RR$
\item Constraints $C$: ~ $\forall 1\le i \neq j \le n: u_i -u_j+n x_{i,j} \le n-1$
\end{itemize}

Übung: beweise
\begin{itemize}
\item für jede Rundreise gibt es eine Belegung der $u_i$, 
  die $C$ erfüllt.
\item aus jeder Lösung von $C$ kann man eine Rundreise rekonstruieren.
\end{itemize}
Was ist die anschauliche Bedeutung der $u_i$?

\end{slide}
