Konstruktionsheuristiken

Mit Konstruktionsheuristiken können ein guter zulässiger Punkt (hoher Zielfunktionswert) konstruiert werden. Nun könnte man auf die Idee kommen, Konstruktionsheuristiken wären überflüssig, da man ja im Normalfall immer mindestens einen zulässigen Punkt kennt und diesen dann durch eine Verbesserungsheuristik einfach schrittweise optimieren könnte. Tatsächlich spart man sich mit einer Konstruktionsheuristik aber einige Iterationen bei der Verbesserungsheuristik, da die Konstruktionsheuristik schon einen relativ guten Wert liefert. Darüber hinaus kann es natürlich auch vorkommen, dass man den Punkt den die Konstruktionsheuristik liefert gar nicht anschließend verbessern möchte. Nimmt man beispielsweise das Branch-and-Bound-Verfahren, so kann man die erste untere Schranke beim Start des Verfahren durch eine Konstruktionsheuristik bestimmen. Damit können schon viele Probleme ausgelotet werden, was wiederum dem Aufwand des Verfahrens zu Gute kommt.

Mögliche Konstruktionsheuristiken:

  • Zufallsverfahren: Variablen werden zufällig belegt, wobei immer noch geprüft werden muss ob die Belegung auch zulässig ist.
  • Greedy-Verfahren: Variablen werden schrittweise belegt, wobei in jedem Schritt darauf geachtet wird, dass sich die Zielfunktion so weit wie möglich verbessert, die Zulässigkeit gleichzeitig aber nicht verletzt wird.
  • Vorausschauende Verfahren: Ähnlich wie Greedy, allerdings werden die Auswirkungen der Wahl der Belegung der Variable abgeschätzt. Damit ist der Aufwand höher als bei Greedy-Verfahren, dafür ist aber oft auch die ermittelte zulässige Punkt besser.