An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices

Diese Arbeit stellt einen neuartigen hybriden dynamischen Programmieralgorithmus vor, der das Losgrößenproblem mit einem einzigen All-Units-Rabatt und nicht-steigenden Preisen in $O(n\log n)$ Zeit löst und damit den bisherigen $O(n^2)$-Algorithmus verbessert.

Das Wesentliche

Hier ist eine einfache Erklärung der Forschung von Kleitos Papadopoulos, als würde man sie einem Freund beim Kaffee erzählen – ohne komplizierte Formeln, aber mit ein paar guten Bildern.

Das große Problem: Der clevere Tankstellen-Besuch

Stell dir vor, du planst eine lange Reise mit deinem Auto von Punkt A nach Punkt Z. Unterwegs gibt es viele Tankstellen. Dein Ziel ist es, so wenig Geld wie möglich für den gesamten Trip auszugeben, aber du musst sicherstellen, dass du nie leerläufst.

Dabei gibt es ein paar Regeln:

1. Der Preis schwankt: Manchmal ist Benzin an einer Station teuer, manchmal billig.
2. Der Mengenrabatt: An manchen Stationen bekommst du einen Rabatt, wenn du eine bestimmte Mindestmenge (sagen wir, 100 Liter) kaufst. Wenn du nur 10 Liter kaufst, zahlst du den vollen Preis.
3. Der Tank ist begrenzt: Dein Kofferraum (der Tank) ist nicht unendlich groß. Du kannst nicht einfach 10.000 Liter kaufen, nur weil es billig ist.
4. Die Preise werden günstiger: Das ist der spezielle Fall in diesem Papier: Die Benzinpreise werden im Laufe der Reise immer gleich bleiben oder sogar sinken. Sie werden nie plötzlich wieder teurer.

Das alte Problem: Warum es vorher so langsam war

Früher haben Computer versucht, für jeden einzelnen Liter, den du im Tank haben könntest, eine separate Rechnung zu machen.

• "Was kostet es, wenn ich 0 Liter habe?"
• "Was kostet es, wenn ich 1 Liter habe?"
• "Was kostet es, wenn ich 2 Liter habe?"
• ... bis hin zum vollen Tank.

Wenn du 1.000 Stationen hast und der Tank 1.000 Liter fasst, muss der Computer Millionen von Berechnungen durchführen. Das ist wie wenn du für jeden einzelnen Schritt auf einer Wanderung eine neue Landkarte zeichnest. Es funktioniert, aber es dauert ewig. Das alte Verfahren brauchte so viel Zeit, dass es bei großen Reisen unpraktisch wurde (die Komplexität war $O(n^2)$).

Die neue Lösung: Der "Zauber-Trick" mit den Gruppen

Der Autor hat entdeckt, dass man nicht jeden einzelnen Liter einzeln betrachten muss. Stattdessen kann man den Tank in Gruppen einteilen, die sich alle gleich verhalten.

Stell dir vor, du hast eine Reihe von Freunden, die alle den gleichen Weg gehen.

• Die alte Methode: Du fragst jeden einzelnen Freund: "Wie viel kostet es, wenn du genau 50 Schritte machst?"
• Die neue Methode: Du sagst: "Hey, alle Freunde in dieser Gruppe (z. B. zwischen 40 und 60 Litern) haben denselben Preis pro Liter und denselben Rabatt-Status. Ich brauche nur die Rechnung für den ersten Freund in der Gruppe und eine einfache Formel, um den Rest zu berechnen."

Der Autor nennt diese Gruppen "Segmente".

• Ein Segment ist wie ein Zauberstab, der eine ganze Strecke des Tanks abdeckt.
• Anstatt Millionen von Datenpunkten zu speichern, speichert der Computer nur ein paar dieser Zauberstäbe (die Segmente) und die Formel, wie man den Rest daraus ableitet.

Wie der Algorithmus funktioniert (Die Reise)

Der Algorithmus fährt Station für Station durch und macht drei Dinge:

1. Der Große Schnitt (Bulk-Update):
   Wenn eine Station kommt, an der du den Rabatt bekommst, wenn du genug kaufst, "fütterst" du alle Segmente, die noch nicht weit genug gereist sind, automatisch mit dem Rabatt. Stell dir vor, du gibst allen Freunden in der Gruppe gleichzeitig einen Gutschein. Das geht blitzschnell, weil du es nur einmal für die ganze Gruppe sagst.

2. Das Aufräumen (Dominanz):
   Manchmal gibt es zwei Gruppen, die fast das Gleiche tun, aber eine ist etwas teurer. Der Algorithmus schaut sich die "Endpunkte" der Gruppen an. Wenn Gruppe A an einem bestimmten Punkt billiger ist als Gruppe B, und die Preise für Gruppe A danach auch noch besser oder gleich bleiben, dann ist Gruppe B komplett nutzlos.

   • Die Analogie: Wenn du zwei Lieferdienste hast und Lieferant A immer schneller und billiger ist als Lieferant B, dann stellst du Lieferant B einfach ein. Du musst nicht mehr für ihn rechnen. Der Algorithmus löscht diese "schlechten" Gruppen sofort aus dem Gedächtnis.

3. Die intelligente Suche (MV-Schwellenwerte):
   Der Algorithmus benutzt eine Art "Wächter" (einen sogenannten Schwellenwert). Er fragt sich: "Ist der aktuelle Benzinpreis niedrig genug, damit Gruppe A besser ist als Gruppe B?"

   • Wenn ja -> Gruppe B wird gelöscht.
   • Wenn nein -> Beide bleiben, aber wir prüfen die nächste Grenze.
     Da die Preise nur sinken oder gleich bleiben, muss man diese Prüfung nur sehr selten machen.

Warum ist das so schnell?

Stell dir vor, du hast einen Berg von Papierstapeln (die alten Berechnungen).

• Die alte Methode musste jedes einzelne Blatt einzeln durchzählen.
• Die neue Methode nimmt den Stapel, sortiert ihn in wenige dicke Blöcke und wirft die unnötigen Blöcke sofort weg.

Durch die cleveren Regeln (dass die Preise nicht steigen) und die Tatsache, dass man ganze Gruppen auf einmal löschen kann, wächst die Rechenzeit nicht quadratisch (wie bei einem Quadrat), sondern nur noch logarithmisch (wie bei einem Suchbaum).

Vereinfacht gesagt:

• Alt: 100 Stationen = 10.000 Rechenschritte.
• Neu: 100 Stationen = ca. 600 Rechenschritte.
• Bei 1 Million Stationen ist der Unterschied gigantisch: Die alte Methode würde Jahre brauchen, die neue nur Sekunden.

Das Ergebnis

Dieses Papier zeigt, wie man mit einem sehr cleveren mathematischen Trick (dem "Segment-Management" und dem "Dominanz-Auflösen") ein riesiges Problem löst, das Unternehmen jeden Tag haben: Wie bestelle ich Waren so, dass ich den Rabatt bekomme, aber nicht zu viel auf Lager habe, und dabei den geringsten Preis zahle?

Es ist wie ein Super-Planer für den Einkauf, der nicht nur schaut, was heute billig ist, sondern weiß, dass morgen vielleicht noch billiger ist, und trotzdem genau die richtige Menge kauft, um den Rabatt zu sichern, ohne den Keller vollzustopfen. Und das alles in einer Geschwindigkeit, die für riesige Lieferketten perfekt ist.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papiers auf Deutsch:

Titel: Ein $O(n \log n)$-Algorithmus für die Losgrößenplanung mit einem einzelnen Einzelstück-Mengenrabatt und nicht-steigenden Preisen

Autor: Kleitos Papadopoulos
Datum: Oktober 2025 (veröffentlicht im März 2026)

---

1. Problemstellung

Das Papier adressiert das Single-Item Lot Sizing Problem (Losgrößenplanung für ein einzelnes Produkt) unter spezifischen Bedingungen:

• Zeithorizont: $n$ Perioden (Stationen).
• Nachfrage: Eine bekannte Nachfrage $d_t$ muss in jeder Periode erfüllt werden.
• Kostenstruktur:
  • Mengenrabatt (All-Units Discount): Es gibt einen Schwellenwert $Q$. Wenn die Bestellmenge $x_t < Q$ ist, gilt der Preis $p_{1,t}$. Wenn $x_t \ge Q$, gilt ein verbilligter Preis $p_{2,t} \le p_{1,t}$ für alle bestellten Einheiten.
  • Nicht-steigende Preise: Die Preise über den Zeitverlauf sind monoton fallend ($p_{1,t} \ge p_{1,t+1}$ und $p_{2,t} \ge p_{2,t+1}$).
  • Lagerkosten: Lineare Lagerhaltungskosten $h_t$ pro Einheit am Ende der Periode.
  • Kapazität: Es gibt eine Obergrenze $B(t)$ für den Lagerbestand.
• Ziel: Minimierung der Gesamtkosten (Beschaffung + Lagerhaltung) unter Einhaltung der Nachfrage und Kapazitätsbeschränkungen.

Das Problem wird auch durch eine Analogie zur Tankstellen-Problemstellung veranschaulicht, wobei Perioden Tankstellen, Nachfrage die Distanz und Lagerbestand der Kraftstoffvorrat im Tank darstellen.

---

2. Methodik und Algorithmus

Der Kern der Arbeit ist die Entwicklung eines hybriden dynamischen Programmieransatzes, der die Komplexität von $O(n^2)$ auf $O(n \log n)$ reduziert.

A. Zustandsrepräsentation und Segmente

Statt jeden einzelnen Lagerbestandszustand explizit zu speichern, nutzt der Algorithmus eine kompakte Darstellung:

• Zustands-Segmente (State-Segments): Der Lösungsraum wird in Segmente unterteilt. Ein Segment besteht aus einem expliziten "Anker"-Zustand (einem bestimmten Lagerbestand und dessen minimalen Kosten) und einer linearen Gleichung.
• Implizite Zustände: Alle anderen Zustände innerhalb eines Segments können durch die lineare Gleichung des Ankers generiert werden. Dies reduziert den Speicherbedarf und die Anzahl der zu verarbeitenden Punkte drastisch.
• Approximative Lösungsmenge: Die Menge der optimalen Zustände $S(i)$ für eine Station $i$ wird als "2Q-approximative Lösungsmenge" gespeichert. Es wird bewiesen, dass Zustände mit einem Lagerbestand größer als $2Q$ für die Konstruktion optimaler Lösungen in der nächsten Periode nicht notwendig sind (Lemma 5.2).

B. Dominanz und MV-Schwellenwerte

Um Segmente zu cullieren (zu entfernen), werden strukturelle Eigenschaften genutzt:

• Dominanz: Ein Segment $S_1$ dominiert ein benachbartes Segment $S_2$, wenn $S_1$ an einem bestimmten Prüfpunkt (Checkpoint) strikt günstigere Kosten liefert und aufgrund der Preisstruktur (nicht-steigende Preise) auch für alle folgenden Punkte im Bereich von $S_2$ günstiger bleibt.
• MV-Schwellenwerte (Minimum Value Thresholds): Für jedes benachbarte Segmentpaar wird ein kritischer Preiswert ($MV$) berechnet. Wenn der aktuelle Marktpreis unter diesem Schwellenwert fällt, wird das rechte (dominierte) Segment entfernt.
  • Es werden zwei Arten von MVs unterschieden: Regular MV (an der Grenze zwischen Segmenten) und Terminus MV (am Ende eines Segments, wo ein Rabatt endet).

C. Der Algorithmus (Pro Station)

Der Algorithmus verarbeitet jede Station $i$ schrittweise unter Verwendung eines augmentierten balancierten Binärsuchbaums (BST), der die Segmente nach ihrem Endpunkt (Terminus) sortiert hält:

1. Individual Updates (Pruning): Vergleich des aktuellen Preises ($p_{1,i}$ oder $p_{2,i}$) mit den gespeicherten MV-Schwellenwerten. Wenn der Preis niedrig genug ist, werden dominierte Nachbarn entfernt.
2. Splitting: Der Baum wird an der Stelle $d(i, i+1)$ (Nachfrage zur nächsten Station) geschnitten. Segmente, die die nächste Station nicht erreichen können, werden in eine Menge $X$ (nicht-reichend) und die restlichen in $R$ (reichend) getrennt.
3. Bulk Updates: Allen Segmenten in $X$ wird virtuell ein Block von $Q$ Einheiten zum Rabattpreis $p_{2,i}$ hinzugefügt (Lazy-Tagging). Dies simuliert den Erwerb des Rabatts für alle, die gezwungen sind, an Station $i$ zu kaufen.
4. Line-Merge: Die Menge $X$ (mit Rabatt) wird mit dem relevanten Teil von $R$ (im Bereich $[Q, 2Q]$) fusioniert. Dabei werden überflüssige Segmente basierend auf Lemma 5.10 entfernt (entweder vollständige Übernahme oder Tail-Erweiterung).
5. Einfügen des Grenzzustands: Der optimale Zustand für den Start der nächsten Station ($dp(i+1, 0)$) wird berechnet und eingefügt.
6. Holding Costs & Demand Shift: Lagerkosten werden addiert (als Verschiebung der Kostenfunktion) und die Nachfrage wird subtrahiert.

---

3. Schlüsselbeiträge und Theoretische Ergebnisse

• Komplexitätsreduktion: Der Algorithmus erreicht eine Zeitkomplexität von $O(n \log n)$, was eine signifikante Verbesserung gegenüber dem bisherigen State-of-the-Art von $O(n^2)$ (z. B. Down et al., 2021) darstellt.
• Strukturelle Lemmata:
  • Lemma 5.2: Es genügt, nur die ersten $2Q$ Zustände zu betrachten; Zustände darüber sind für die optimale Konstruktion der nächsten Periode irrelevant.
  • Lemma 5.3 & 5.5: Monotonie der "Legacy-Preise" (frühere Rabatte) und Kontinuität der optimalen Zustände. Dies ermöglicht die effiziente Segmentierung.
  • Lemma 5.7 & 5.9: Bedingungen für die Dominanz von Segmenten basierend auf Endpunkten und gleichen Steigungen.
• Datenstruktur: Die Verwendung eines augmentierten BST mit Lazy-Tags für Massenupdates (Bulk-Updates) und Holding-Kosten-Verschiebungen ist entscheidend für die Effizienz.
• Erweiterbarkeit: Der Ansatz kann lineare Lagerhaltungskosten und Kapazitätsbeschränkungen ($B(i)$) effizient handhaben, ohne die asymptotische Komplexität zu erhöhen.

---

4. Ergebnisse und Bedeutung

• Leistung: Der Algorithmus ist nicht nur theoretisch schneller, sondern nutzt auch eine kompakte Darstellung, die den Speicherbedarf reduziert und die Anzahl der Operationen pro Periode minimiert.
• Vergleich: Tabelle 1 im Papier zeigt den direkten Vergleich mit früheren Arbeiten. Während frühere Ansätze für ähnliche Probleme (mit Rabatt und nicht-steigenden Preisen) $O(n^2)$ bis $O(n^4)$ benötigten, liefert dieser Ansatz $O(n \log n)$.
• Allgemeingültigkeit: Die entwickelten Techniken (Segmentierung, MV-Schwellenwerte, hybride DP) sind allgemein genug, um potenziell auf andere Varianten der Losgrößenplanung oder graphbasierte Probleme (wie das Tankstellenproblem) anwendbar zu sein.
• Praktische Relevanz: Da viele reale Produktions- und Beschaffungsszenarien Mengenrabatte und schwankende (oft fallende) Preise aufweisen, bietet dieser Algorithmus eine effiziente Lösung für die Optimierung dieser Prozesse.

Fazit

Dieses Papier stellt einen bedeutenden Fortschritt in der kombinatorischen Optimierung dar. Durch die Kombination von tiefgehenden strukturellen Einsichten in die Eigenschaften der optimalen Lösung (insbesondere die Reduktion des relevanten Zustandsraums auf $2Q$ und die Nutzung von Dominanz-Eigenschaften) mit effizienten Datenstrukturen (BST mit Lazy-Updates) gelingt es, ein klassisches NP-schweres Problem (in allgemeinen Fällen) für eine wichtige Spezialklasse in fast linearer Zeit zu lösen.