
\begin{slide}{(Mixed) Integer Programming}

  \begin{itemize}\itemsep 0pt
  \item 
``linear program'': lineares Ungleichungssystem
mit Unbekannten aus $\QQ$
\item
``integer program'': lineares Ungleichungssystem,
mit Unbekannten aus $\ZZ$
\item
``mixed integer program'': lineares Ungleichungssystem,
mit Unbekannten aus $\QQ$ und $\ZZ$
  \end{itemize}

LP ist in P (Ellipsoid-Verfahren),
aber IP ist NP-vollständig:
\begin{itemize}\itemsep 0pt
\item SAT $\le_P$ IP,
\item jedes IP besitzt obere Schranke für 
  Größe einer Lösung;
\end{itemize}
deswegen gibt es keinen effizienten Algorithmus
(falls P $\neq$ NP)

\end{slide}
