(Mixed) Integer Programming

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

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

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

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