TY  - THES
A3  - Suhl, Leena
A3  - Fábián, Csaba I.
AB  - 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.
AU  - Wolf, Christian
DA  - 2014
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 18.12.2013
N1  - Paderborn, Univ., Diss., 2013
PB  - Veröffentlichungen der Universität
PY  - 2014
T2  - Department 3: Wirtschaftsinformatik
TI  - Advanced acceleration techniques for Nested Benders decomposition in stochastic programming
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-12700
Y2  - 2024-09-12T00:17:26
ER  -