Heuristiken

Wie wir in Kapitel 5 gesehen haben, ist die Lösung eines ganzzahligen linearen Problems eine NP-schwere Aufgabe, so dass die vorgestellten exakten Verfahren im Allgemeinen einen exponentiellen Rechenaufwand besitzen. Aus diesem Grund greift man in vielen Anwendungen auf Heuristiken zurück, wenn der mit der Anwendung exakter Verfahren verbundene Rechenaufwand zu groß wird. Heuristiken sind demnach Verfahren zur Bestimmung eines guten, aber nicht notwendigerweise optimalen zulässigen Punktes eines Problems bei akzeptablem Aufwand. „Gut“ bedeutet in diesem Zusammenhang, dass der Zielfunktionswert des Punktes möglichst nahe am Optimalwert liegen soll. Der wesentliche Vorteil von Heuristiken liegt in ihrer meist polynomialen und damit relativ schnellen Rechengeschwindigkeit.