Online Inventory Problems: Beyond the i.i.d. Setting with Online Convex Optimization

Dit artikel introduceert MaxCOSD, een online algoritme dat gegarandeerde prestaties biedt voor multi-product voorraadbeheer onder realistische, niet-i.i.d. vraagpatronen en dynamische toestanden, zoals bederf, door af te wijken van traditionele nieuwe-kruidenier-aannames.

De kern

Stel je voor dat je de manager bent van een grote supermarkt. Je taak is simpel klinken, maar in de praktijk een enorme uitdaging: hoeveel producten moet je elke week bestellen?

Te veel bestellen? Dan moet je betalen voor opslag, en als het voedsel bederft, gooi je het weg. Te weinig bestellen? Dan staan de schappen leeg, klanten zijn boos en je mist omzet.

In de wereld van de wiskunde en bedrijfskunde heet dit een voorraadprobleem.

Het oude verhaal: De "Gokker"

Vroeger dachten wetenschappers dat je dit probleem kon oplossen door te gokken op het verleden. Ze gingen ervan uit dat de vraag van klanten altijd hetzelfde patroon volgde (zoals een dobbelsteen die eerlijk is). Als je gisteren veel melk verkocht, was de kans groot dat je vandaag ook veel melk verkoopt.

Maar in het echte leven is dat niet zo. Soms is het regent, soms is er een feestje, soms is er een schandalig nieuwsbericht. De vraag is niet altijd hetzelfde (niet "i.i.d." zoals wiskundigen zeggen). En als je probeert te leren van het verleden terwijl de toekomst steeds verandert, raken de oude methoden in de war. Ze werken niet meer als de dynamiek van de winkel verandert (bijvoorbeeld als producten een houdbaarheidsdatum hebben).

De nieuwe oplossing: MaxCOSD

De auteurs van dit paper hebben een nieuwe, slimme manier bedacht om dit probleem op te lossen. Ze noemen hun algoritme MaxCOSD.

Om dit uit te leggen, gebruiken we een analogie: Het fietsen in een storm.

Stel je voor dat je een fietspad hebt (dat is je voorraadkast) en je moet erop fietsen zonder te vallen (dat is je voorraad niet laten leeglopen of te vol te maken).

• De oude methode: Je kijkt alleen naar de wind van gisteren en hoopt dat het vandaag hetzelfde waait. Als de wind plotseling verandert, val je.
• De nieuwe methode (MaxCOSD): Je kijkt niet alleen naar de wind, maar je voelt ook direct hoe de grond onder je wielen voelt. Als je merkt dat je te ver naar links leunt (te veel voorraad), corrigeer je je richting, maar niet elke seconde. Je wacht tot je zeker weet dat de grond stabiel genoeg is om te sturen.

Hoe werkt MaxCOSD precies?

1. Het "Cyclische" Ritme:
   In plaats van elke dag een nieuwe bestelling te doen (wat chaos kan veroorzaken), wacht MaxCOSD op het juiste moment. Het kijkt: "Is de situatie stabiel genoeg om een nieuwe berekening te maken?"
   Als de vraag van klanten erg onvoorspelbaar is (bijvoorbeeld omdat er bijna geen vraag is), wacht het algoritme langer. Het durft niet te snel te reageren. Dit heet een "cyclus".

2. De "Niet-Degeneratie" Regel (De Brandstof):
   Dit is het belangrijkste punt van het paper. Het algoritme heeft een speciale waarschuwing: "Er moet altijd een beetje vraag zijn."
   Stel je voor dat je een auto hebt die rijdt op brandstof (de vraag). Als er geen brandstof is (geen klanten), kun je de auto niet besturen. Je kunt niet leren hoe je moet sturen als de auto nooit beweegt.
   De auteurs bewijzen wiskundig dat als de vraag soms helemaal op nul zakt, je nooit goed kunt leren. Je moet dus aannemen dat er altijd een minimale kans is dat er een klant komt. Zonder die minimale "brandstof" faalt elk slim algoritme.

3. Leren van fouten (Subgradiënten):
   Elke keer als je een fout maakt (bijvoorbeeld te veel melk besteld), krijg je een "stootje" terug (de kosten). MaxCOSD gebruikt deze stootjes om zijn koers te corrigeren. Maar in plaats van direct te draaien, doet het dit op een slimme manier die rekening houdt met hoe onzeker de toekomst is.

Waarom is dit belangrijk?

• Voor de supermarkt: Je kunt nu voorraadbeheer doen in een wereld die chaotisch is. Of het nu gaat om verse bloemen (die bederven) of dure elektronica, dit algoritme werkt zonder dat je hoeft te gokken op een "gemiddelde" vraag.
• Voor de wetenschap: Het verbindt twee werelden die eerder gescheiden waren: Online Learning (leren terwijl je doet) en Operations Research (voorraadbeheer). Ze tonen aan dat je geen perfecte voorspellingen nodig hebt om goed te presteren, zolang je maar slim omgaat met onzekerheid.

Samenvattend in één zin:

MaxCOSD is als een ervaren schipper die niet probeert de golven te voorspellen, maar die weet hoe hij zijn boot moet sturen door constant te voelen waar de wind vandaan komt, zolang er maar een beetje wind is om op te varen.

Het paper laat zien dat je, zelfs als de wereld chaotisch is en producten bederven, toch slimme beslissingen kunt nemen als je alleen maar weet dat er altijd een klein beetje vraag blijft bestaan.

Technische samenvatting

Probleemstelling

Het artikel adresseert het probleem van online voorraadbeheer (multi-product inventory control), waarbij een manager sequentiële beslissingen moet nemen over hoeveel goederen er besteld moeten worden om de cumulatieve verliezen (kosten) te minimaliseren.

Traditionele literatuur op dit gebied maakt vaak te sterke aannames die de realiteit niet goed weerspiegelen:

1. i.i.d. Aannames: De vraag wordt vaak verondersteld onafhankelijk en identiek verdeeld (i.i.d.) te zijn, wat correlaties en non-stationariteit (veranderingen in tijd) uitsluit.
2. Beperkte Kostenstructuren: Veel modellen focussen specifiek op de "newsvendor"-kostfunctie (over- en onderkost).
3. Beperkte Dynamiek: Modellen gaan vaak uit van niet-bederfelijke producten of specifieke dynamieken zoals verloren verkoop of backlogging, zonder complexere scenario's zoals bederfelijkheid (perishability) te behandelen.

Het doel van dit onderzoek is om een raamwerk te ontwikkelen dat generieke vraagprocessen, kostenfuncties en voorraaddynamieken (inclusief bederfelijkheid) kan hanteren, zonder de i.i.d.-aanname, en dat theoretische garanties biedt.

Methodologie en Raamwerk

De auteurs introduceren een nieuw raamwerk genaamd Online Inventory Optimization (OIO). Dit is een strikte uitbreiding van Online Convex Optimization (OCO).

Het OIO-model:

• Protocol: Op elk tijdstip $t$ observeert de manager de voorraadtoestand $x_t$, kiest een bestelniveau $y_t$ (waarbij $y_t \succeq x_t$), en ontvangt direct de bestelde eenheden.
• Verliezen: De manager ondergaat een verlies $\ell_t(y_t)$ en observeert een subgradient $g_t \in \partial \ell_t(y_t)$.
• Dynamiek: De voorraadtoestand wordt bijgewerkt volgens $x_{t+1} \preceq [y_t - d_t]^+$. Dit dekt diverse scenario's af:
  • Stateless: Geen overdracht van voorraad (vergelijkbaar met standaard OCO).
  • Backlogging: Onvoldane vraag wordt uitgesteld.
  • Lost sales: Onvoldane vraag gaat verloren.
  • Perishable: Producten hebben een beperkte levensduur.
• Regret: De prestatie wordt gemeten aan de hand van de regret $R_T$, het verschil tussen de cumulatieve kosten van het algoritme en de beste constante strategie (base-stock policy) die achteraf bekend zou zijn.

Het Algoritme: MaxCOSD
De kern van de bijdrage is het MaxCOSD-algoritme (Maximum Cyclic Online Subgradient Descent). Dit is een variant op subgradient descent met de volgende kenmerken:

• Cyclische Updates: In plaats van elke periode te updaten, worden updates alleen uitgevoerd op specifieke momenten ($t_k$). Tussen deze updates blijft het bestelniveau $y_t$ constant.
• Dynamische Trigger: Een update wordt getriggerd wanneer een kandidaat-niveau $\hat{y}_t$, berekend via een subgradient-stap, haalbaar is (d.w.z. voldoet aan de voorraad-dynamische beperkingen).
• Adaptieve Leerstappen: Het algoritme gebruikt adaptieve leerstappen (geïnspireerd op AdaGrad-Norm) die afhankelijk zijn van de geaccumuleerde subgradiënten, wat zorgt voor robuustheid zonder kennis van de constante $G$ (bound van subgradiënten).

Belangrijke Aannames:
Om leerbaarheid te garanderen zonder i.i.d.-aannames, introduceren de auteurs een niet-degeneratie-aanname op de vraag:

• Uniforme waarschijnlijkheid van positieve vraag (Assumptie 10): Er bestaat een $\rho > 0$ en $\mu \in (0,1]$ zodat de kans dat de vraag voor elk product groter is dan $\rho$, gegeven de geschiedenis, ten minste $\mu$ is.
• Dit is een verzwakte versie van eerdere aannames (zoals $E[d] > 0$) en is essentieel om te voorkomen dat de voorraadtoestand vastloopt in een staat waar geen haalbare beslissingen meer mogelijk zijn.

Kernbijdragen

1. MaxCOSD Algoritme: Een nieuw algoritme dat OIO-problemen oplost met bewezen theoretische garanties, zelfs bij niet-i.i.d. vraag en stateful dynamiek (zoals bederfelijkheid).
2. Theoretische Garanties: Het bewijs dat MaxCOSD een optimale regret-schaal van $O(\sqrt{T})$ bereikt, zowel in verwachting als met hoge waarschijnlijkheid.
3. Noodzaak van Niet-Degeneratie: De auteurs bewijzen (via Propositie 13 en 14) dat voor stateful voorraadproblemen een aanname over de vraag (dat deze niet te dicht bij nul mag komen) noodzakelijk is. Zonder deze aanname is het onmogelijk om sublineaire regret te bereiken, zelfs met volledige informatie over de vraag. Dit is een fundamenteel verschil met standaard OCO.
4. Generalisatie: Het model omvat bestaande modellen (zoals AIM, DDM, CUP) als speciale gevallen, maar werkt onder veel mildere aannames (geen i.i.d. vereist).

Resultaten

• Theoretisch:

  • Stelling 12: Onder de aannames van convexiteit, begrenzing en niet-degeneratie, voldoet MaxCOSD aan de regret-bound:
    $$E[R_T] \leq C \cdot \sqrt{T}$$
    waarbij de constante $C$ afhangt van de parameters van het probleem (zoals $\mu$, de diameter van het haalbare gebied, en de bound van de subgradiënten).
  • Het bewijs maakt gebruik van een analyse van de lengte van de cycli (geometrische cycli) en toont aan dat de haalbaarheidsvoorwaarde vaak genoeg wordt voldaan onder de niet-degeneratie-aanname.

• Empirisch:

  • Experimenten zijn uitgevoerd op synthetische data en real-world data (M5 competitie dataset).
  • Scenario's: Enkelvoudige producten, bederfelijke producten, multi-product systemen met capaciteitsbeperkingen.
  • Vergelijking: MaxCOSD presteert goed vergeleken met state-of-the-art baselines (AIM, CUP, DDM) in scenario's met een beperkt aantal producten.
  • Beperking: Bij zeer grote aantallen producten (bijv. $n=3049$) neemt de efficiëntie af omdat de cycli langer worden (het is minder waarschijnlijk dat de haalbaarheidsvoorwaarde snel wordt voldaan). Dit bevestigt de theoretische inzichten over de relatie tussen vraaggrootte en haalbaarheid.

Significantie

Dit artikel vormt een belangrijke brug tussen de theorie van Online Convex Optimization (OCO) en de praktische wereld van voorraadoptimalisatie.

• Realisme: Het doorbreekt de barrière van de i.i.d.-aanname, wat cruciaal is voor toepassingen in de echte wereld waar vraagpatronen vaak seizoensgebonden, correlatief of veranderlijk zijn.
• Theoretische Strenge: Het biedt de eerste algoritmen met sterke regret-garanties voor complexe, stateful voorraadproblemen (zoals bederfelijkheid) zonder de beperkende aannames van eerdere werken.
• Praktische Toepasbaarheid: Hoewel er nog ruimte is voor verbetering bij zeer grote schaal (veel producten), biedt MaxCOSD een robuust kader voor managers om beslissingen te nemen in onzekere en dynamische omgevingen, met garanties dat de kosten niet te veel afwijken van de optimale strategie.

Samenvattend stelt dit werk dat online voorraadproblemen oplosbaar zijn met sublineaire regret, mits men accepteert dat de vraag niet "degenerate" is (d.w.z. niet structureel nul is), en introduceert MaxCOSD als een veelzijdig algoritme om dit te bereiken.