Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

Technische Samenvatting: Ising-Machine-Assisted Large Neighborhood Search met Flexibel Instelbare Subprobleemgrootte

Probleemstelling
Ising-machines dienen als heuristische solvers voor combinatorische optimalisatie door te zoeken naar toestanden met een lage energie van Ising- of Quadratic Unconstrained Binary Optimization (QUBO)-modellen. Het direct toepassen van Ising-machines op grootschalige gebonden problemen (de "naïeve methode") stuit echter op twee primaire moeilijkheden:

1. Schaalbaarheid: Het aantal binaire variabelen in de QUBO-formulering overschrijdt vaak de hardwarecapaciteit van huidige Ising-machines.
2. Haalbaarheid: Constraints worden doorgaans geïntegreerd als straftermen (penalty terms). Bijgevolg bevat de zoekruimte niet-haalbare oplossingen, en corresponderen toestanden met een lage energie niet noodzakelijkerwijs met hoogwaardige haalbare oplossingen van het oorspronkelijke probleem.

Bestaande benaderingen zoals variabele fixatie of divide-and-conquer proberen de probleemgrootte te reduceren, maar worstelen vaak met het balanceren van de subprobleemgrootte met het vermogen om haalbare oplossingen voor het oorspronkelijke probleem te reconstrueren. Large Neighborhood Search (LNS) biedt een raamwerk waarbij een haalbare huidige oplossing iteratief wordt verbeterd door een subprobleem (een "neighborhood") opnieuw te optimaliseren. Terwijl LNS de haalbaarheid behoudt als de methode voor subprobleemgeneratie correct is ontworpen, is de prestatie van Ising-machine-ondersteunde LNS zeer gevoelig voor de grootte van het subprobleem. Als het subprobleem te klein is, is de potentiële verbetering per iteratie beperkt; als het te groot is, verslechtert de kwaliteit van de oplossing van de Ising-machine door de uitgebreide zoekruimte.

Methodologie
Het artikel richt zich op twee problemen: het Vehicle Routing Problem (VRP) en het Quadratic Multiple Knapsack Problem (QMKP).

• Bestaande Methode (LNS-V): Voor het VRP analyseert de auteur een eerdere methode (LNS-V) die een subset van voertuigen selecteert en de volledige routes van deze voertuigen opnieuw optimaliseert. Hoewel dit de haalbaarheid waarborgt, wordt de omvang van het subprobleem uitsluitend bepaald door het aantal geselecteerde voertuigen ($V'$). Omdat de volledige route van een geselecteerd voertuig opnieuw wordt geoptimaliseerd, schaalt het aantal variabelen als $(V')^2(T-2)^2$ (waarbij $T$ de totale stappen is). Dit resulteert in een grove granulariteit; het veranderen van $V'$ met één kan een enorme sprong in het aantal variabelen veroorzaken, waardoor het moeilijk is om de subprobleemgrootte af te stemmen op het optimale bereik voor de Ising-machine.

• Voorgestelde Methode (LNS-VT): Om de granulariteitsproblematiek aan te pakken, stellen de auteurs LNS-VT voor. Naast het selecteren van $V'$ voertuigen introduceert LNS-VT een nieuwe parameter: het aantal opeenvolgende stappen ($T'$) dat voor elk geselecteerd voertuig opnieuw moet worden geoptimaliseerd.

  • Mechanisme: Voor elk geselecteerd voertuig wordt een aaneengesloten segment van de route (van lengte $T_{seg} = \min(T', \text{werkelijke geldige stappen})$) geëxtraxt. Het subprobleem optimaliseert de toewijzing en volgorde van locaties binnen deze specifieke segmenten, terwijl de rest van de route vast blijft staan.
  • Haalbaarheid: Door de locaties buiten de extractie-intervallen vast te leggen en ervoor te zorgen dat de geëxtraheerde segmenten alleen niet-depotlocaties bevatten, garandeert de methode dat het herinvoegen van elke haalbare subprobleemoplossing leidt tot een haalbare oplossing voor het oorspronkelijke VRP.
  • Variabele Controle: Het aantal vrije variabelen in LNS-VT is ongeveer $(V'T')^2$. Dit maakt fijnmazige controle over de subprobleemgrootte mogelijk, onafhankelijk van het totaal aantal stappen $T$.

• Extensie naar QMKP: De auteurs passen hetzelfde ontwerpprincipe toe op de QMKP. Ze construeren een methode voor subprobleemgeneratie die een subset van knapsacks ($K'$) en een subset van items ($N'$) selecteert om opnieuw te optimaliseren. Deze methode behoudt eveneens de haalbaarheid door items die niet in de geselecteerde set zitten vast te leggen en de capaciteitsrestricties aan te passen op basis van de resterende capaciteit van de geselecteerde knapsacks.

Belangrijkste Resultaten
Numerieke experimenten werden uitgevoerd met een 300-locatie, 5-voertuig VRP en een 200-item, 5-knapsack QMKP, gebruikmakend van de Fixstars Amplify AE Ising-machine.

• VRP Prestaties:

  • LNS-VT presteerde beter dan zowel de naïeve methode als de bestaande LNS-V.
  • De beste LNS-VT-instelling (specifiek $V'=2, T'=40$) verminderde de objectieve waarde met ongeveer 10% ten opzichte van LNS-V na 100 iteraties.
  • LNS-VT bereikte de uiteindelijke oplossingskwaliteit van LNS-V met slechts ongeveer 30% van de iteraties.
  • Variabele Sensitiviteit: De optimale subprobleemgrootte (in termen van niet-depot locatie-toewijzingsvariabelen) werd gevonden te liggen tussen 6.000 en 10.000. De bestaande LNS-V kon dit bereik niet bereiken met $V' \ge 2$ (het minimum was ~14.400 variabelen), wat de inferieure prestatie verklaart.
  • Dynamische Behoeften: De geschikte subprobleemgrootte veranderde tijdens het zoekproces. Grotere subproblemen waren effectiever in de vroege iteraties (hoge objectieve waarden), terwijl kleinere subproblemen effectiever waren in latere iteraties (verfijning van hoogwaardige oplossingen).

• QMKP Prestaties:

  • LNS toegepast op de QMKP presteerde eveneens beter dan de naïeve methode.
  • De optimale subprobleemgrootte voor QMKP werd gevonden te zijn aanzienlijk kleiner, ongeveer 100 tot 150 variabelen.
  • Dit drastische verschil met de VRP (6.000–10.000) geeft aan dat de optimale subprobleemgrootte afhankelijk is van de specifieke probleemklasse en de QUBO-formulering, en niet enkel van de capaciteiten van de Ising-machine.

Significantie en Claims
Het artikel claimt dat voor Ising-machine-ondersteunde LNS om effectief te zijn voor grootschalige gebonden problemen, het louter waarborgen van haalbaarheid onvoldoende is. Het vermogen om de subprobleemgrootte flexibel af te stemmen op het prestatie-optimum van de Ising-machine is een kritieke ontwerpfactor.

De studie demonstreert dat:

1. Het introduceren van een extra controleparameter (opeenvolgende stappen voor VRP, of item/knapsack-aantallen voor QMKP) zorgt voor een fijnmazige aanpassing van de subprobleemgrootte, wat onmogelijk is met methoden die alleen het aantal geselecteerde entiteiten variëren.
2. Er bestaat een optimaal bereik van variabelen voor het subprobleem dat de oplossingskwaliteit maximaliseert, en dit bereik varieert aanzienlijk tussen verschillende probleemklassen (VRP vs. QMKP).
3. De optimale subprobleemgrootte kan ook afhangen van de kwaliteit van de huidige oplossing, wat suggereert dat statische parameterinstellingen niet optimaal kunnen zijn gedurende het gehele zoekproces.

De auteurs concluderen dat hoewel hun resultaten specifiek zijn voor de geteste instanties en machine-instellingen, het principe van structuur-bewuste, flexibel instelbare subprobleemgeneratie een veelbelovende richting is voor gebonden combinatorische optimalisatie. Zij merken op dat toekomstig werk zich moet richten op het ontwikkelen van adaptieve strategieën om subprobleemparameters automatisch te selecteren op basis van de fase van het zoekproces en de probleemstructuur.