Evaluating the solution performance of the augmented Lagrangian function on Ising machines

Technische Samenvatting: Evaluatie van de Prestaties van de Augmented Lagrangian-functie op Ising-machines

Probleemstelling
Ising-machines zijn gespecialiseerde computerapparaten die zijn ontworst om combinatorische optimalisatieproblemen op te lossen door ze in kaart te brengen naar de grondtoestand van een Ising-model. Een aanzienlijke uitdaging bij het toepassen van deze machines op beperkte problemen is de formulering van restricties. Typisch worden restricties in de objectieve functie opgenomen via een strafterm, wat een strafcoëfficiënt ($\mu$) vereist om de objectieve functie af te wegen tegen de naleving van de restrictie. Deze coëfficiënt houdt een inherent compromis in zich: als $\mu$ te klein is, genereert de machine niet-haalbare toestanden; als $\mu$ te groot is, wordt het energielandschap gedomineerd door de restrictieterm, waardoor verschillen in de waarden van de objectieve functie worden vertroebeld en het moeilijk wordt om hoogwaardige haalbare oplossingen te vinden. Hoewel er diverse afstemmethoden bestaan om $\mu$ aan te passen, vertrouwen deze over het algemeen op een enkele parameter om dit compromis te beheren.

Methodologie
Deze studie evalueert de Augmented Lagrangian Function (ALF) als een alternatieve formulering voor Ising-machines, waarbij deze specifiek wordt vergeleken met de standaard Penalty Function (PF) formulering. De auteurs maken gebruik van het Quadratic Knapsack Problem (QKP) als benchmark, een probleem met ongelijkheidsrestricties waarbij het doel is om de waarde van items te maximaliseren zonder een gewichtscapaciteit te overschrijden.

1. Formuleringen:

   • Penalty Function: De probleem-Hamiltoniaan wordt gedefinieerd als $H_P(x) = f(x) + \frac{\mu}{2}[g(x) - c]^2$, waarbij $f(x)$ de objectieve functie is en $g(x)=c$ de restrictie is.
   • Augmented Lagrangian Function: De Hamiltoniaan wordt gedefinieerd als $H_{AL}(x) = f(x) + \frac{\mu}{2}[g(x) - c]^2 - \lambda[g(x) - c]$. Dit introduceert een Lagrange-multiplierterm ($\lambda$) die lineair is ten opzichte van de restrictie-overtreding.
   • De studie behandelt de ALF als een statische formulering met vaste hyperparameters ($\mu, \lambda$), in plaats van een iteratief algoritme dat deze parameters tijdens de zoektocht bijwerkt, hoewel de iteratieve Augmented Lagrangian Method (ALM) als een aanvullende analyse wordt besproken.

2. Experimentele Opstelling:

   • Solver: De Fixstars Amplify Annealing Engine (AE) werd gebruikt.
   • Instanties: Drie QKP-benchmarkinstanties ($N=100, 200, 300$) met bekende optimale oplossingen werden gebruikt.
   • Metriek: Prestaties werden geëvalueerd met behulp van Time-to-Epsilon ($TT_\epsilon$), gedefinieerd als de totale rekentijd die nodig is om een haalbare oplossing te verkrijgen met een objectieve fout binnen een relatieve tolerantie $\epsilon$ (gesteld op 0,05) met een doelwaarschijnlijkheid ($p_R = 0,99$).
   • Parameters: Er werd een grid search uitgevoerd over $\mu$ (0 tot 100) en $\lambda$ (-500 tot 500).

Belangrijkste Bijdragen en Resultaten
De studie biedt een kwantitatieve evaluatie van hoe de ALF-formulering de prestaties van de oplossing beïnvloedt in vergelijking met de PF-formulering.

• Reductie in $TT_\epsilon$: De ALF-formulering verminderde de $TT_\epsilon$ met ongeveer één orde van grootte vergeleken met de best presterende PF-formulering. Specifiek, voor de instantie 'r 100 50 5', werd de minimale $TT_\epsilon$ voor de PF gevonden bij $\mu=40$, terwijl de ALF aanzienlijk lagere $TT_\epsilon$-waarden bereikte bij veel kleinere $\mu$-waarden (bijv. $\mu=5, \lambda=100$).
• Parameterafhankelijkheid: De resultaten toonden aan dat de ALF de mogelijkheid biedt om relatief kleine $\mu$-waarden te gebruiken terwijl er nog steeds haalbare oplossingen worden verkregen. In de PF-formulering leidt een kleine $\mu$ tot onhaalbaarheid, terwijl een grote $\mu$ de kwaliteit van de oplossing verslechtert. De ALF verzacht dit door de $\lambda$-term te gebruiken om het energielandschap te corrigeren, waardoor de relatieve energieschaal van de objectieve functie behouden blijft, zelfs wanneer $\mu$ klein is.
• Temporele Evolutie: Analyse van de temporele evolutie van de incidentele oplossing toonde aan dat de oplossing onder representatieve ALF-instellingen de plateau (nabij optimale objectieve waarde) eerder bereikte in de uitvoeringstijd vergeleken met de PF. Bovendien was de variatie tussen haalbare oplossingen kleiner voor de ALF.
• Structurele Verklaring: Door middel van een "kwadraataanvullings"-analyse lieten de auteurs zien dat de ALF wiskundig equivalent is aan het verschuiven van de effectieve capaciteit van de restrictie. De term $\lambda$ verschuift effectief het minimum van de strafterm van $H_{const}=0$ naar $H_{const}=\lambda/\mu$. Voor $\lambda > 0$ verschuift dit de zoektocht naar itemselecties met kleinere totale gewichten, wat de kans vergroot om de oorspronkelijke ongelijkheidsrestrictie te voldoen zonder dat een grote $\mu$ vereist is.

Significantie en Claims
Het artikel claimt dat de Augmented Lagrangian Function een veelbelovende formulering is voor het verbeteren van de prestaties van Ising-machines. De primaire significantie ligt in het feit dat de introductie van de Lagrange-multiplierterm het mogelijk maakt om de strafcoëfficiënt $\mu$ klein te houden. Dit behoudt de bijdrage van de term van de objectieve functie in het energielandschap, wat het efficiënter maakt om haalbare oplossingen met kleine objectieve fouten te vinden dan de standaard penalty function.

De auteurs merken op dat hun conclusies gebaseerd zijn op QKP-benchmarkinstanties en specifieke solver-instellingen. Ze stellen expliciet dat het gedetailleerde dynamische mechanisme dat verklaart waarom de ALF de asymptotische waarde eerder bereikt, nog niet is opgehelderd en verdere investigatie vereist naar de toestandsveranderingsgedragingen. Daarnaast, hoewel de studie zich richt op de formulering zelf, suggereren de resultaten dat de voordelen potentieel kunnen worden benut door de iteratieve Augmented Lagrangian Method (ALM), die parameters adaptief bijwerkt op basis van de restrictie-overtreding, hoewel een systematische kostenvergelijking tussen iteratieve updates en directe parameterzoekopdrachten een onderwerp voor toekomstig onderzoek blijft.