(Mixed) Integer Programming

• ``linear program'': lineares Ungleichungssystem mit Unbekannten aus $\mathbb {Q}$
• ``integer program'': lineares Ungleichungssystem, mit Unbekannten aus $\mathbb {Z}$
• ``mixed integer program'': lineares Ungleichungssystem, mit Unbekannten aus $\mathbb {Q}$ und $\mathbb {Z}$

LP ist in P (Ellipsoid-Verfahren), aber IP ist NP-vollständig:

• SAT ≤_P IP,
• jedes IP besitzt obere Schranke für Größe einer Lösung;

deswegen gibt es keinen effizienten Algorithmus (falls P ≠ NP)