Spaltengenerierung

Spaltengenerierung oder verzögerte Spaltengenerierung ist ein effizienter Algorithmus zum Lösen großer linearer Programme.

Die übergeordnete Idee ist, dass viele lineare Programme zu groß sind, um alle Variablen explizit zu berücksichtigen. Die Prämisse ist, dass die meisten Variablen nicht basisch sind und in der optimalen Lösung einen Wert von Null annehmen. Aus diesem Grund muss bei der Lösung des Problems theoretisch nur eine Teilmenge von Variablen berücksichtigt werden. Die Spaltengenerierung nutzt diese Idee, um nur die Variablen zu generieren, die das Potenzial haben, die Zielfunktion zu verbessern, dh Variablen mit negativen reduzierten Kosten zu finden (unter der Annahme, dass das Problem ohne Verlust der Allgemeinheit ein Minimierungsproblem ist).

Das zu lösende Problem ist in zwei Probleme aufgeteilt: das Hauptproblem und das Unterproblem. Das Hauptproblem ist das ursprüngliche Problem, bei dem nur eine Teilmenge von Variablen berücksichtigt wird. Das Unterproblem ist ein neues Problem, das erstellt wird, um eine neue Variable zu identifizieren. Die Zielfunktion des Teilproblems sind die reduzierten Kosten der neuen Variablen in Bezug auf die aktuellen Doppelvariablen, und die Einschränkungen erfordern, dass die Variable den natürlich vorkommenden Einschränkungen gehorcht.

Der Prozess funktioniert wie folgt. Das Hauptproblem ist gelöst — aus dieser Lösung können wir doppelte Preise für jede der Einschränkungen im Hauptproblem erhalten. Diese Information wird dann in der Zielfunktion des Teilproblems verwendet. Das Teilproblem ist gelöst. Wenn der objektive Wert des Teilproblems negativ ist, wurde eine Variable mit negativen reduzierten Kosten identifiziert. Diese Variable wird dann dem Masterproblem hinzugefügt, und das Masterproblem wird erneut gelöst. Durch erneutes Lösen des Hauptproblems wird ein neuer Satz von Doppelwerten generiert, und der Vorgang wird wiederholt, bis keine negativen Variablen mit reduzierten Kosten mehr identifiziert werden. Das Teilproblem gibt eine Lösung mit nicht negativen reduzierten Kosten zurück, wir können daraus schließen, dass die Lösung des Masterproblems optimal ist.

In vielen Fällen können dadurch große lineare Programme gelöst werden, die zuvor als unlösbar galten. Das klassische Beispiel für ein Problem, bei dem dies erfolgreich angewendet wird, ist das Schneidstoffproblem. Eine besondere Technik in der linearen Programmierung, die diese Art von Ansatz verwendet, ist der Dantzig-Wolfe-Zersetzungsalgorithmus. Darüber hinaus wurde die Spaltengenerierung auf viele Probleme wie Besatzungsplanung, Fahrzeugrouting und das Problem des kapazitierten p-Medians angewendet.

Dieser Artikel zur angewandten Mathematik ist ein Stummel. Sie können Wikipedia helfen, indem Sie es erweitern.