Vortragsreihe »Felix-Klein-Kolloquium« / 25. April 2024, 17:15 – 18:30 Uhr
Erweiterte Teilproblemschleifung für das Lot-Typ Design Problem
Wir betrachten einen Modediscounter, der seine vielen Filialen mit ganzzahligen Vielfachen aus einer Menge verfügbarer Los-Typen beliefert. Das Lot-Type-Design-Problem (LDP) [Gaul et al. 2010] fragt: »Welche (ganzzahligen) Vielfachen von welchen (ganzzahligen) Lot-Typen (Größensortimenten) sollten an eine Menge von Filialen geliefert werden, um eine (fraktionale) erwartete Nachfrage so gut wie möglich zu erfüllen?«
Es gibt ein kompaktes LDP-Modell, dessen integrale Lücke jedoch so groß ist, dass es für die meisten praktischen Fälle nicht gelöst werden kann. Andererseits kann das engste bisher bekannte LDP-Modell [Gaul et al. 2010] Milliarden von Variablen haben. (Für 12 verschiedene Größen, die für Unterwäsche oder Kinderkleidung angemessen sind, gibt es 1.159.533.584 verschiedene Lostypen, wenn wir von höchstens 5 Artikeln jeder Größe und einer Gesamtzahl von Artikeln in einem Lostyp zwischen 12 und 30 ausgehen.) Daher kann das enge Modell nicht für alle Fälle statisch in einen Computer eingegeben werden.
Wir zeigen, wie das enge Modell, das als eine Dantzig-Wolfe-Zerlegung (eine Standardformulierung zur Straffung von ILP-Modellen) des kompakten Modells interpretiert werden kann, mit Augmented Subproblem Grinding gelöst werden kann, einer neuen Branch-and-Cut-and-Price-Variante, die für enge Modelle gut geeignet ist. Es erzwingt einen binären Branch-and-Price-Baum. Ein Zweig besteht aus einem einzigen vielversprechenden Teilproblem, das sofort gelöst (»abgeschliffen«) wird. Der andere Zweig wird durch eine neue Nebenbedingung (»erweitert«) verschärft, die alle Lösungen ausschließt, die nur aus bekannten Spalten bestehen (eine nicht standardisierte Reformulierung).
Die theoretische Kernkomponente ist die Identifizierung eines charakteristischen Hebens von dualen Variablen im reduzierten Hauptproblem für alle Nebenbedingungen, die mit neuen Variablen auftauchen würden. Rechenergebnisse auf realen Instanzen sowie auf randomisierten Stresstests zeigen, dass für das enge LDP-Modell Augmented Subproblem Grinding die Lösung im Durchschnitt um einen Faktor von mehr als 100 im Vergleich zur Lösung des statischen Modells beschleunigt und Instanzen (bis zu 9.867.114.720.320 Variablen) löst, die statisch überhaupt nicht gelöst werden können.
Referent:
Prof. Dr. Jörg Rambau, Universität Bayreuth