In einigen Optimierungsproblemen ergibt sich das Problem, dass mindestens ein Parameter des Optimierungsmodells einer Unsicherheit unterliegt. Ist eine grobe Abschätzung des Ausmaßes der Unsicherheit möglich, dann kann diese z.B. anhand von vordefinierten Szenarien im Optimierungsmodell berücksichtigt werden. Die wesentliche Schwäche dieser Vorgehensweise besteht darin, dass die so entstehenden Optimierungsprobleme typischerweise sehr viele Variablen und Nebenbedingungen besitzen, weshalb die Lösung viel Zeit beansprucht. Spaltenbasierende Lösungsverfahren (engl. Column Generation) bieten das Potential, derart große Probleme schneller zu lösen als gängige Standardverfahren wie Branch and Cut, allerdings setzen sie den Einsatz von Dekompositionsmethoden voraus, welche die Struktur der Optimierungsprobleme verändern.

 

In dieser Arbeit wurden mit der „separaten“ und der „kombinierten“ Dekompositionsmethode zwei neuartige Verfahren hinsichtlich ihrer Eignung in der Praxis untersucht. Die Methoden wurden jeweils auf eine mit Unsicherheit behaftete Variante des Rucksackproblems und des Warehouse Location Problems angewendet. Das zur Lösung notwendige spaltenbasierte Verfahren wurde unter Verwendung von CPLEX anhand eines Java-Programms implementiert. Zur Identifizierung von Einflussfaktoren wurden viele unterschiedliche Instanzen erzeugt, die sich sowohl in der Problemgröße als auch in der Parametergenerierung unterscheiden.

 

Die Untersuchung ergab einerseits, dass ein spaltenbasiertes Verfahren unter Verwendung der neuen Dekompositionsmethoden schneller die optimale Lösung finden kann als das Branch and Cut Verfahren. Andererseits konnte jedoch gezeigt werden, dass eine Anwendbarkeit der Dekompositionsmethoden nicht immer gegeben ist und dass die Laufzeitreduzierung nicht bei allen Problemen realisiert werden kann. Da aktuell noch unklar ist, bei welchen Problemen die vorgestellten Verfahren zu besonders schnellen Lösungen führen, ist ein Einsatz nur bei bereits näher untersuchten Problemen sinnvoll.