Duale Ungleichungen zur Stabilisierung von Column-Generation-Verfahren (StabCG)

• Antragsteller: Professor Dr. Stefan Irnich
• Fachliche Zuordnung: Accounting und Finance
• Förderung: Förderung von 2016 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 280866737

Viele Planungs- und Optimierungsverfahren basieren auf Modellen und Verfahren der gemischt-ganzzahligen Programmierung. Sie haben seit Mitte des letzten Jahrhunderts enorme Fortschritte erzielen können, einerseits getrieben durch eine gesteigerte Rechenleistung heutiger Computer, andererseits durch vielfältige methodische Errungenschaften in der gemischt-ganzzahligen Programmierung. Verfahren der Spaltengenerierung (engl.: Column Generation, CG) gehören zu den erfolgreichsten und wichtigsten Verfahren, um große Lineare Programme mit einer großen Anzahl an Variablen zu lösen. Das Einbetten von CG-Verfahren in einen Branch-and-Bound-Algorithmus ermöglicht zudem die Lösung von gemischt-ganzzahligen Programmen. Solche Verfahren werden üblicherweise als Branch-and-Price-Algorithmen bezeichnet. Viele erfolgreiche Branch-and-Price-Algorithmen finden sich beispielsweise in den Bereichen Tourenplanung, Personaleinsatzplanung, Pack- und Zuschnittprobleme, Reihenfolgeplanung und Graphenoptimierung. Die wichtigsten Nachteile von CG-Verfahren sind primär auf Instabilitäten im Bezug auf die Werte der Dualvariablen zurückzuführen. Bisherige Techniken zum Abschwächen der negativen Effekte kann man alle unter dem Begriff "numerische Verfahren der Stabilisierung" subsumieren. Valério de Carvalho (2005: INFORMS Journal on Computing, 17(2), 175-182) and Ben Amor u.a. (2006: Operations Research, 54(3), 454-463) haben für das Zuschnittproblem und das Behälter-Packproblem einen komplett anderen Weg zur Stabilisierung eingeschlagen. Sie nutzen Kenntnisse über Eigenschaften dual optimaler Lösungen zur Stabilisierung des CG-Prozesses. Jede gültige Ungleichung (engl.: dual optimal inequality, DOI) für das Polyeder der optimalen Duallösungen kann als zusätzliche Variable in das zugehörige primale CG-Modell eingefügt werden. Im Rahmen der Dissertation (Gschwind 2014: Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz) wurden aktuell eine Reihe von innovativen Konzepten entwickelt, die die bisherige Literatur zu stabilisierten CG-Verfahren mittels DOIs in verschiedener Hinsicht erweitert. Die übergeordnete Zielsetzung des Forschungsprojekts besteht darin, verbesserte, exakte Lösungsverfahren für verschiedene Probleme zu entwickeln, mit denen im Vergleich zum Stand der Forschung größere und schwierigere Probleminstanzen optimal gelöst werden können. Dies soll durch die Weiterentwicklung von Techniken zur Stabilisierung von CG-Verfahren mit DOIs erreicht werden. Dem zugrunde liegt die durch die bisherigen Erkenntnisse aus der Literatur und den eigenen Vorarbeiten gestützte Annahme, dass ein erfolgreiches Stabilisieren die CG-Verfahren für viele Probleme entscheidend verbessern kann.

• DFG-Verfahren: Sachbeihilfen