🤖 machine learning

Regularized Large Neighborhood Search

Dit artikel introduceert Regularized Large Neighborhood Search (RLNS), een nieuw framework dat de LNS-heuristiek transformeert naar een efficiënte MCMC-sampler via regularisatie, waardoor end-to-end leren van combinatorische optimalisatielagen mogelijk wordt zonder dat daarvoor computationeel onhaalbare globale solvers vereist zijn.

Oorspronkelijke auteurs: Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

Gepubliceerd 2026-06-02

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier, Mathieu Blondel

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een enorme, ongelooflijk complexe puzzel op te lossen. Je hebt duizenden stukjes, en ze moeten perfect in elkaar passen om aan een set strikte regels te voldoen. In de wereld van de wiskunde en informatica wordt dit een combinatorisch optimalisatieprobleem genoemd.

Decennialang hebben experts (operations researchers) een slimme truc gebruikt die Large Neighborhood Search (LNS) wordt genoemd om deze puzzels op te lossen. Denk aan LNS als een meesterredacteur die werkt aan een roman. In plaats van het hele boek in één keer te herschrijven (wat onmogelijk is), bevriest de redacteur 90% van het verhaal en herschrijft hij telkens één klein hoofdstuk. Ze vinden de beste versie van dat hoofdstuk, leggen het vast, gaan naar het volgende hoofdstuk en herhalen dit proces. Dit is snel en schaalbaar, maar het is een "heuristiek" — een methode gebaseerd op een slimme gok die geen gegarandeerde perfecte globale oplossing biedt, maar slechts een zeer goede.

Aan de andere kant van de kamer proberen onderzoekers van Machine Learning computers te leren hoe ze deze puzzels kunnen oplossen door naar voorbeelden te kijken. Ze willen een "neuraal netwerk" (een type AI) bouடen dat de regels van de puzzel leert begrijpen en de oplossing kan produceren. Echter, om de AI te onderwijzen, moet de computer weten hoe hij zijn "knoppen" (gradiënten) precies moet aanpassen om een beter antwoord te krijgen. Dit vereist meestal een exacte globale solver — een methode die elke keer de perfecte oplossing vindt.

Het Probleem:
Voor enorme, real-world puzzels (zoals het plannen van bezorgwagens of het toewijzen van taken) is het vinden van die perfecte globale oplossing computationeel onmogelijk. Het zou langer duren dan het huidige universum bestaat. Dus de "perfecte" solvers die gebruikt worden bij AI-training, werken niet voor de grote problemen waar LNS-experts dagelijks mee te maken hebben.

De Oplossing: Regularized LNS (RLNS)
De auteurs van dit artikel overbruggen deze kloof. Ze hebben een nieuwe methode ontwikkeld genaamd Regularized Large Neighborhood Search (RLNS).

Hier is hoe ze het deden, met behulp van een paar analogieën:

1. De "Gladgestreken" Redacteur

Standaard LNS is rigide: het kiest een klein deel van de puzzel en vindt de enkele beste manier om het te repareren.
RLNS voegt een "temperatuur" of "ruis" toe aan het proces. Stel je voor dat de redacteur niet alleen op zoek is naar de één beste zin, maar dat hij ook de ruimte krijgt om een paar licht afwijkende, "goed genoeg" zinnen te proberen op basis van een waarschijnlijkheid.

De Magie: Door deze willekeur (regularisatie) toe te voegen, stopt de redacteur met simpelweg "gokken" en begint hij te handelen als een wetenschappelijke sampler. Hij zoekt niet langer alleen naar een lokaal hoogtepunt; hij verkent het landschap op een manier die, na verloop van tijd, de statistische verdeling van alle mogelijke goede oplossingen perfect nabootst.

2. De "Block Gibbs" Dans

Het artikel bewijst dat wanneer je een specif kind type "ruis" gebruikt (genaamd entropische regularisatie), RLNS een Block Gibbs Sampler wordt.

De Analogie: Stel je een dansvloer voor met duizenden mensen (mogelijke oplossingen). Je wilt weten waar de menigte zich waarschijnlijk bevindt.
- De Oude Manier: Je probeert elke persoon in de hele kamer tegelijkertijd te tellen (Global Solver). Onmogelijk voor een enorme menigte.
- De RLNS-Manier: Je bevriest 90% van de dansers op hun plek. Je vraagt de resterende 10% om rond te schuifelen en de beste plekken voor hen te vinden, gegeven waar de anderen staan. Daarna bevries je een andere 90% en laat je de nieuwe 10% rondschuifelen.
- Het Resultaat: Het artikel bewijst dat als je deze "schuif-en-vries"-dans blijft uitvoeren, de menigte uiteindelijk in exact hetzelfde patroon terechtkomt als wanneer je iedereen perfect had geteld. Je krijgt de statistische waarheid zonder dat je de onmogelijke globale telling nodig hebt.

3. Leren zonder de "Perfecte" Solver

De grootste doorbraak is hoe dit hels AI leert.

Het Oude Probleem: Om een AI te trainen, heb je meestal het "perfecte" antwoord nodig om de fout te berekenen. Als je het perfecte antwoord niet kunt vinden, kun je de AI niet trainen.
De RLNS Fix: De auteurs laten zien dat je de AI kunt trainen met enkel deze "lokale verschuivingen".
- Als je één verschuiving doet (K=1), leert de AI op basis van "pseudolikelihood" (een lokale benadering). Dit is snel en goedkoop.
- Als je veel verschuivingen doet (K=100), leert de AI dichter bij de "exacte maximum likelihood" (de globale waarheid).
- Het Voordeel: Je kunt aan een knop draaien om de afweging tussen snelheid en nauwkeurigheid te maken. Je hebt geen globale solver meer nodig; je hebt alleen de lokale "redacteur" (LsN) nodig die operations researchers al gebruiken.

4. Real-World Tests

De auteurs hebben dit getest op drie soorten puzzels:

Het selecteren van een deelverzameling van items: Zoals precies 500 items kiezen uit een totaal van 1.000.
Generalized Assignment: Zoals het toewijzen van 50 pakketten aan 5 vrachtwagens met beperkte ruimte.
Vehicle Scheduling: Zoals het routeren van bezorgwagens door een stad met onzekere verkeersvertragingen.

In alle gevallen werkte RLNS. Het leerde om goede oplossingen sneller en efficiënter te voorspellen dan methoden die probeerden "black box"-benaderingen te gebruiken of die onmogelijke globale berekeningen vereisten.

Samenvatting

Het artikel introduceert RLNS, een methode die een standaard "lokale zoekheuristiek" (die meestal gewoon een goed antwoord vindt) verandert in een rigoureus statistisch instrument dat gebruikt kan worden om AI-modellen te trainen.

Het stelt machine learning-modellen in staat om te leren hoe ze enorme, complexe real-world puzzels (zoals logistiek en planning) kunnen oplossen zonder eerst de "perfecte" versie van de puzzel te hoeven oplossen. Het zegt effectief: "We hoeven niet het hele bos te zien om te leren hoe we erin moeten navigeren; we hoeven alleen maar te weten hoe we door de bomen vlak voor ons moeten navigeren, en dat vaak genoeg te doen."

Technische Samenvatting: Regularized Large Neighborhood Search (RLNS)

Probleemstelling

Het integreren van combinatorische optimalisatielagen in neurale netwerken is een krachtig paradigma geworden voor gestructureerde voorspelling, waarbij modellen discrete beslissingen kunnen genereren die voldoen aan complexe restricties. De standaardformulering betreft een laag gedefinieerd door $\hat{y}(\theta) \triangleq \arg \max_{y \in \mathcal{Y}} \langle \theta, y \rangle$ , waarbij $\mathcal{Y}$ een eindige maar combinatorisch grote verzameling haalbare outputs is.

De fundamentele uitdaging in deze context is differentieerbaarheid. Omdat de $\arg \max$ -operator bijna overal een nul-gradiënt levert, vertrouwen bestaande benaderingen doorgaans op regularisatie om een continue, differentieerbare relaxatie te verkrijgen. Echter, de meeste huidige methoden (bijv. Fenchel-Young verliezen, geperturbeerde optimalisatoren) gaan fundamenteel uit van toegang tot een globale exacte solver (een globale MAP-oracle) of een marginaal oracle om verwachtingswaarden van de Gibbs-distributie te berekenen. Voor NP-harde optimalisatieproblemen die gebruikelijk zijn in operations research, is het aanroepen van een globale oracle bij elke trainingsstap computationeel onhaalbaar. Bijgevolg vertrouwen beoefenaars op schaalbare heuristieken zoals Large Neighborhood Search (LNS), die oplossingen iteratief verfijnen door subsets van variabelen te bevriezen en de rest opnieuw te optimaliseren. Het gebrek aan een principieel kader om LNS te gebruiken als een differentieerbare combinatorische laag blijft een kritieke flessenhals.

Methodologie: Regularized LNS (RLNS)

De auteurs introduceren Regularized Large Neighborhood Search (RLNS), een stochastische versie van LNS die de kloof overbrugt tussen schaalbare heuristieken en differentieerbare optimalisatielagen. Het kernidee is om de lokale subproblemen binnen het LNS-framework te regulariseren of te perturberen, waardoor de heuristiek wordt getransformeerd in een efficiënte Markov Chain Monte Carlo (MCMC) sampler over de combinatorische verzameling van haalbare oplossingen.

1. Framework en Lokale Regularisatie

RLNS definieert een familie van lokale regularisatiefuncties afgeleid van een globale regularisator $\Omega$ . Voor een subset van oplossingen $\mathcal{Z} \subseteq \mathcal{Y}$ wordt een lokale regularisator $\Omega_{\mathcal{Z}}$ gedefinieerd via een inclusie-afbeelding. In plaats van het globale geregulariseerde probleem op te lossen, bemonsteren RLNS iteratief uit lokaal geregulariseerde distributies $p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])$ , waarbij $\mathcal{Y}(k)$ de lokale buurt is die wordt gedefinieerd door een subset coördinaten $S^{(k)}$ te bevriezen.

2. Entropische Regularisatie en Block Gibbs Sampling

Wanneer de globale regularisator Shannon's negatieve entropie is ( $\Omega = -\gamma H_s$ ), bewijzen de auteurs dat RLNS exacte block Gibbs sampling uitvoert. Specifiek komt de lokaal geregulariseerde distributie overeen met de globale geregulariseerde Gibbs-distributie geconditioneerd op de vaste variabelen:
$p_{\Omega_{\mathcal{Y}(k)}}((s_\theta)[\mathcal{Y}(k)])(y) = p_{\Omega}(s_\theta)(y \mid y^{(k)}_{[S^{(k)}]})$
Onder een irreducibel variabele-selectieschema convergeert de stationaire distributie van de RLNS-iteraties exact naar de globaal geregulariseerde Gibbs-distributie. Dit resultaat is uniek voor entropische regularisatie; Propositie 2 karakteriseert Shannon's entropie als de enige scheidbare regularisator die deze exactheid garandeert.

3. Perturbatie-gebaseerde Regularisatie

In scenario's waar lokale marginale oracles (vereist voor entropische sampling) onhandelbaar zijn, maar lokale MAP oracles wel beschikbaar zijn, stellen de auteurs het gebruik van perturbatie-gebaseerde regularisatie voor. Door ruis $\epsilon Z$ toe te voegen aan de lokale scores en het geperturbeerde lokale maximalisatieprobleem op te lossen, kan RLNS samplen uit de lokale geregulariseerde distributie. Deze aanpak maakt gebruik van standaard LNS oracles (bijv. dynamisch programmeren voor knapzak-subproblemen) zonder dat er mechanismen voor sample-rejectie nodig zijn, in tegente opposed aan Metropolis-Hastings-gebaseerde lokale zoekmethoden.

4. Leren en Interpolatie

Het artikel legt een verband tussen het aantal RLNS-iteraties ( $K$ ) en de leerdoelstelling:

$K=1$ (Lokale Fenchel-Young Verlies): Een enkele stap van RLNS levert een onbevooroordeelde estimator voor een lokaal Fenchel-Young verlies. In de entropische setting herstelt dit de pseudolikelihood (composite likelihood) doelstelling, die de likelihood van subsets van variabelen maximaliseert geconditioneerd op de rest.
$K \to \infty$ (Globale Fenchel-Young Verlies): Naarmate het aantal iteraties toeneemt, convergeert de estimator naar de gradiënt van de globale Fenchel-Young verlies, wat een benadering vormt voor de exacte maximum likelihood schatting.
Dit stelt beoefenaars in staat om te interpoleren tussen pseudolikelihood en exacte maximum likelihood schatting door $K$ af te stemmen, wat end-to-end leren mogelijk maakt zonder globale solvers.

Belangrijkste Bijdragen

RLNS Framework: Introductie van een stochastische, geregulariseerde versie van LNS die lokale regularisatie integreert in LNS-subproblemen, waardoor een differentieerbare combinatorische laag ontstaat.
Theoretische Equivalentie: Bewijs dat onder entropische regularisatie RLNS een exacte block Gibbs sampler implementeert waarvan de stationaire distributie overeenkomt met de globale geregulariseerde Gibbs-distributie.
Hanteerbaarheid via Perturbatie: Demonstratie dat perturbatie-gebaseerde regularisatie RLNS in staat stelt om standaard lokale MAP oracles te gebruiken, wat de hanteerbaarheid garandeert telkens wanneer standaard LNS hanteerbaar is.
Interpolatie van Leervoorschriften: Theoretische en empirische demonstratie dat het aantal RLNS-iteraties toestaat te interpoleren tussen pseudolikelihood en exacte maximum likelihood schatting.
Empirische Validatie: Evaluatie op drie verschillende problemen:
- $\kappa$ -hot vectoren: Een gecontroleerde schattingsopgave die convergentie tegen de grondwaarheid valideert.
- Generalized Assignment Problem (GAP): Leren om assignments te voorspellen waarbij de lokale subproblemen 0/1 Knapsack problemen zijn.
- Stochastische Vehicle Scheduling: Een real-world benchmark waar RLNS-1 beter presteert dan blackbox differentiatie en binary cross-entropy baselines, terwijl het aanzienlijk minder rekenkracht vereist dan globale solvers.

Resultaten

Convergentie: In het $\kappa$ -hot vector experiment convergeert RLNS sneller dan Local Search MCMC en bereikt het een lagere Mean Absolute Error (MAE) dan Monte-Carlo schatting voor hetzelfde aantal samples, vooral wanneer een hoog aandeel variabelen vrij wordt gelaten.
Schaalbaarheid: In de GAP-experimenten zijn de lokale MAP oracles gebruikt door RLNS orden van grootte sneller dan globale Mixed Integer Linear Programming (MILP) solvers, vooral naarmate de probleemomvang toeneemt.
Prestaties: In stochastic vehicle scheduling benadert RLNS-1 (met een enkele iteratie) bijna de prestaties van globale perturbed Fenchel-Young (PFY) learning in termen van vertragingskosten, terwijl het slechts ongeveer een derde van de oorspronkelijke omvang van de subproblemen hoeft te verwerken. Het presteert significant beter dan de Blackbox Differentiation (DBB) en Binary Cross-Entropy (BCE) baselines.
Bias Analyse: Theoretische grenzen tonen aan dat de benaderingsfout schaalt met het aantal gedeelde restricties (cut constraints) tussen bevroren en vrije variabelen, wat motiveert om variabele-selectieschema's te gebruiken die deze cross-dependencies minimaliseren (bijv. min-cut selectie).

Betekenis en Claims

Het artikel beweert een kritieke kloof in de literatuur te dichten door het gebruik van zeer schaalbare heuristieken (LNS) als differentieerbare lagen in neurale netwerken mogelijk te maken, waardoor de afhankelijkheid van computationeel onhaalbare globale solvers wordt weggenomen. Door een rigoureus verband te leggen tussen LNS en Gibbs sampling, biedt het werk een principieel kader voor het differentiëren door combinatorische optimalisatielagen met behulp van enkel lokale oracles. De auteurs positioneren RLNS als een praktische oplossing voor end-to-end leren in gestructureerde voorspellingsopdrachten met NP-harde restricties, waarbij een instelbare afruil wordt geboden tussen computationele kosten en statistische nauwkeurigheid via het aantal iteraties $K$ .