Ich weiß, dass die Spaltengenerierung eine optimale Lösung bietet und mit anderen Heuristiken verwendet werden kann. Aber macht das einen exakten Algorithmus? Danke im Voraus.Spaltengenerierung ist exakter oder heuristischer Algorithmus?
Traditionelles CG arbeitet auf dem entspannten Problem. Obwohl es die optimale LP-Lösung findet, kann dies nicht direkt in eine optimale MIP-Lösung übersetzt werden. Bei einigen Problemen (z. B. 1d-Schneidmaterial) gibt es Hinweise darauf, dass diese Lücke gering ist, und wir wenden einfach die für das entspannte Problem gefundenen Spalten auf ein endgültiges MIP an, da dies eine gute, aber notwendigerweise optimale Lösung ist. Es ist also eine Heuristik.
Mit etwas Aufwand können Sie die Spaltengenerierung innerhalb eines Branch-and-Bound-Algorithmus verwenden (dies wird Branch-and-Price genannt). Dies ergibt bewährte optimale Lösungen.