Enumerative Konzepte bei der Lösung ganzzahliger linearer Optimierungsprobleme

1. Problemstellung und Zielsetzung der Arbeit Ein Optimierungsverfahren wird eingesetzt, um unter Berücksichtigung von Nebenbedingungen (Restriktionen) die optimale Lösung eines Problems zu ermitteln. Als optimal gilt eine Lösung dann, wenn die gegebene Zielfunktion ihr absolutes Maximum beziehungsweise ihr absolutes Minimum erreicht hat. Nahezu jedes Problem lässt sich als Optimierungsproblem formulieren. Die Anwendungen in der Praxis sind zahlreich und vielfältig. Allein in der Produktionsprogrammplanung, bei der eine Zielfunktion wie Gewinn, Umsatz oder Deckungsbeitrag maximiert oder Kosten miniert werden soll, treten vielschichtige Problemstellungen auf. Die lineare ganzzahlige Optimierung stellt eine besondere Herausforderung dar. Ganzzahlige Optimierungsmodelle erfordern spezielle Lösungsmethoden. Praktische Probleme kommen dadurch sowie durch die hohe Komplexität und die große Anzahl an abzubildenden Variablen und Restriktionen im Modell schnell an die Grenze der Lösbarkeit. Durch große Fortschritte bezüglich Rechengeschwindigkeit und Speicherkapazitäten in den 90-iger Jahren können mittlerweile durchaus Probleme in praxisrelevanten Größenordnungen gelöst werden. Trotzdem hat dieses Forschungsgebiet durch seine methodischen Herausforderungen nicht an Reiz und Schwierigkeit verloren. Im Gegenteil lassen sich durch den Zuwachs an technischer Unterstützung im Bereich von Solver-Software einerseits weitere Felder mit großem Praxisbezug in Angriff nehmen, andererseits rücken durch die zunehmende Rechengeschwindigkeit moderner Prozessoren verfahrenstechnische Aspekte einer Einzel-enumeration von Werten in den Fokus dieser Arbeit, da Rechenzeiten hierfür nicht mehr die herkömmliche Bedeutung zugemessen werden muss. 2. Forschungsaufgaben Lösungsverfahren Ausgehend von der Klärung der Frage, was ganzzahlige lineare Optimierungsmodelle kennzeichnet, werden die gängigen Lösungsverfahren als Grundlage für enumerative Schnittebenenverfahren dargestellt. Anwendungsgebiete Als Voraussetzung für weitere Untersuchungen werden die Anwendungsgebiete der linearen Optimierung modelliert und für einzelne Zahlenbeispiele gelöst. Hieraus werden Anhaltspunkte für den Schwierigkeitsgrad der Lösung einzelner Problemstellungen erarbeitet, um das Feld der Anwendungsgebiete für weitere Untersuchungen einzugrenzen und darauf aufbauend im Rahmen dieser ausgewählten Anwendungen gezielt Beispiele für eine Analyse enumerativer Schnittebenenverfahren zu entwickeln. Enumerative Schnittebenenverfahren Enumerative Schnittebenenverfahren als Kombination aus Schnittebenenverfahren und einfachen enumerativen Verfahren stellen den zentralen Forschungsgegenstand dieser Arbeit dar. Ziel dabei ist, die Eignung und Leistungsfähigkeit dieser Ansätze zur Ermittlung der ganzzahligen Lösung eines linearen Optimierungsproblems aufzuzeigen. Schnittvariationen Abschließend wird der Frage nachgegangen, wie sich unterschiedliche Strategien hinsichtlich der Wahl der Schnitte im Hinblick auf die Anzahl der einzufügenden Schnitte einerseits und die Anzahl der zu enumerierenden Werte andererseits auswirken. Wenige, beziehungsweise ein tiefer Schnitt führen zu großen schnitterzeugenden Körpern und damit zu einem hohen Enumerationsaufwand. Im Gegensatz dazu führen viele flache Schnitte mit kleinen schnitterzeugenden Köpern zu einem geringen Enumerationsaufwand. Der Einfluss von Schnitttiefe und Schnittlage auf die Anzahl benötigter Schnitte und den Enumerationsaufwand wird untersucht.