Glossar · approach
Spaltengenerierung
Großskalen-Optimierungsmethode, die mögliche Entscheidungen (Spalten) bei Bedarf erzeugt, statt alle vorab aufzuzählen.
Column GenerationVerzögerte Spaltengenerierung
Spaltengenerierung (column generation) ist die Methode der Wahl, wenn es nicht praktikabel ist, jede mögliche Entscheidung (z. B. jedes Schnittmuster, jede Fahrzeugtour) im Voraus aufzulisten. Sie startet mit einer kleinen Initialmenge, löst das Problem, fragt dann mathematisch 'gibt es eine neue Entscheidung, die die Lösung verbessern würde' und fügt sie gegebenenfalls hinzu. 1961 von Gilmore und Gomory für das Zuschnittproblem entwickelt, ist sie heute das Arbeitspferd für großskalige Probleme wie Tourenplanung (VRP), Crew Scheduling und Lufttraffic-Zuordnung.
Örnek
Eine Näherei hat theoretisch Millionen möglicher Schnittmuster. Spaltengenerierung listet sie nicht alle auf — sie findet verbessernde Muster eines nach dem anderen und liefert in praktischer Zeit eine nahezu optimale Lösung.