Details

Autor(en) / Beteiligte

• Wolf, Christian
• Suhl, Leena
• Fábián, Csaba I

Titel

Advanced acceleration techniques for Nested Benders decomposition in stochastic programming : = Fortgeschrittene Beschleunigungstechniken für die Nested Benders Dekomposition in stochastischer Programmierung [Elektronische Ressource]

Erscheinungsjahr

2014

Link zum Volltext

• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)
• Volltext

  kostenfrei

Link zu anderen Inhalten

• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 18.12.2013
• Paderborn, Univ., Diss., 2013
• Open Access
• ger: Reale Optimierungsprobleme werden oft von Unsicherheiten beeinflusst. Diese Probleme können mithilfe stochastischer Programmierung modelliert und gelöst werden. Das deterministische Äquivalent mehrstufiger Probleme mit Kompensation kann leicht unlösbar werden, wenn Lösungsmethoden eingesetzt werden, die die spezielle Struktur von stochastischen Programmen ignorieren. Spezialisierte Dekompositionsmethoden, die es erlauben stochastische Programme in angemessener Zeit zu lösen, sind deshalb von großer Bedeutung. Diese Arbeit präsentiert fortgeschrittene Beschleunigungstechniken für die Nested Benders Dekomposition. Alle Beschleunigungstechniken werden auf einer großen und vielfältigen Menge von Testinstanzen evaluiert um ihre generelle Anwendbarkeit zu zeigen. Die Aggregation von Cuts erlaubt es die Anzahl an Iterationen gegen die Laufzeit des Masterproblems einzutauschen. Cuts zu konsolidieren hilft dabei die laufzeitverlängernden Effekte der Cut Proliferation zu reduzieren. Durch die Benutzung der Manhattan- oder der Unendlichdistanz anstelle der euklidischen Distanz wird das Projektionsproblem der Level Dekompositionsmethode zu einem linearen Programm. Die Genauigkeit-auf-Nachfrage Technik wird erweitert und auf die Benders und Level Dekomposition angewendet. Die thread-basierte Parallelisierung des Algorithmus reduziert die Rechenzeit mit einem guten Beschleunigungsfaktor. Die Kombination der Genauigkeit-auf-Nachfrage Technik mit Level Dekomposition und einem moderaten Cut Aggregationslevel führt zu einem substantiell verbesserten Algorithmus. Desweiteren wird eine Modellierungssprache für lineare Programme für stochastische Programme erweitert. Das erlaubt es den parallelen Nested Benders Solver zum Lösen von Problemen zu benutzen, die entweder mit der Modellierungsumgebung erstellt werden oder im SMPS Format vorliegen.
• eng: Real world optimization problems are often subject to uncertainty. These problems can be modeled and solved with stochastic programming, a mathematical programming technique.Deterministic equivalent formulations of multi-stage recourse problems can easily become unsolvable by solution techniques that do not take the special structure of stochastic programs into account. Specialized decomposition methods, which allow to solve stochastic problems in a reasonable time frame, are therefore important. This work presents advanced acceleration techniques for Nested Benders decomposition. All acceleration techniques are evaluated on a large and diverse test set to show their general applicability.Cut aggregation allows to trade off the number of iterations against the time to solve the master problem. Consolidating optimality cuts is a valid approach to reduce the runtime extending effects of cut proliferation. The projection problem in Level decomposition can be solved with a linear programming solver due to the usage of the manhattan or infinity distance instead of the euclidean distance. On-demand accuracy is extended and applied to both Benders and Level decomposition. Thread-based parallelization of the algorithm reduces the computing time with a good speed-up factor.The combination of on-demand accuracy with level decomposition and a modest level of cut aggregation leads to a substantially improved algorithm. Furthermore, a modeling language for linear programs is extended with the capability to model stochastic programs. This allows to use the parallelized Nested Benders solver to solve both problems modeled with this modeling environment and problems in SMPS format.