Heuristik

Eine Heuristik ist eine Klasse von Algorithmen, die in Polynomialzeit Lösungen vertretbarer Qualität liefert, ohne Optimalität zu garantieren. Der systematische Gebrauch des Begriffs in der OR setzte sich in den 1960er-1970er Jahren nach Polyas *How to Solve It* (1945) und dem Aufkommen NP-schwerer Probleme durch. Heuristiken zerfallen in zwei Hauptfamilien: (1) konstruktive Heuristiken bauen eine Lösung schrittweise aus dem Leeren auf — Beispiele sind Christofides (1976) für TSP, Nearest Neighbor, das Clarke-Wright-Savings-Verfahren, gierige Kanteneinfügung beim Travelling Salesman und LPT/SPT-Prioritätsregeln im Scheduling; (2) Verbesserungsheuristiken verfeinern eine bestehende Lösung durch kleine Nachbarschaftsschritte — 2-opt, k-opt und Lin-Kernighan (1973) sind kanonische Beispiele. Bewertet werden Heuristiken auf drei Achsen: Lösungsqualität (Lücke zur unteren Schranke), Laufzeit und Implementierungsaufwand. Einige Heuristiken gehören zur Klasse der Approximationsalgorithmen mit bewiesener konstanter Gütegarantie (z. B. Christofides 1,5-Approximation für metrisches TSP); andere sind nur empirisch stark. Praktisch dienen Heuristiken als Warm-Start für MIP-Solver, Erzeuger primaler Schranken oder direkte Produktivlösung. Silver, Vidal und de Werra (1980) und Reeves (1993) sind klassische Referenzen. Metaheuristiken (#053) bilden den Dachrahmen über den Heuristiken.