Standardization of Multi-Objective QUBOs

Dit artikel introduceert een nieuwe techniek voor het standaardiseren van multi-objectieve QUBO-problemen door de variantie van elke doelstelling exact te berekenen en te normaliseren, waardoor een betere balans wordt bereikt bij het samenvoegen van doelen met gelijke gewichten en de keuze van gewichten wordt vergemakkelijkt.

De kern

Stel je voor dat je een chef-kok bent die een perfecte maaltijd moet bereiden. Maar er is een probleem: je hebt drie verschillende ingrediënten die je moet combineren, en ze hebben allemaal een heel ander gewicht en formaat.

1. De Suiker: Een heel klein beetje (bijvoorbeeld 1 gram).
2. Het Zout: Een beetje meer (bijvoorbeeld 10 gram).
3. De Groenten: Een hele berg (bijvoorbeeld 500 gram).

Als je nu een recept schrijft dat zegt: "Voeg 1 deel suiker, 1 deel zout en 1 deel groenten toe", dan is je gerecht een ramp. De suiker is vergeten, het zout is verwaarloosbaar, en je eet alleen maar groenten. In de wereld van wiskunde en computers (specifiek bij het oplossen van complexe problemen met kwantumcomputers) noemen we dit het balanceren van doelen.

Dit artikel van Loong Kuan Lee en zijn collega's gaat precies over dit probleem, maar dan in de taal van QUBO (Quadratic Unconstrained Binary Optimization). Dat is een ingewikkelde manier om te zeggen: "Hoe vinden we de beste 'ja' of 'nee'-combinaties voor een heel groot probleem?"

Hier is de uitleg in simpele taal:

Het Probleem: De "Grote" en de "Kleine" Doelen

Stel je voor dat je een computerprogramma hebt dat twee dingen tegelijkertijd moet optimaliseren:

• Doel A: De kosten van een reis minimaliseren (bijvoorbeeld tussen €10 en €100).
• Doel B: De reistijd minimaliseren (bijvoorbeeld tussen 1000 en 5000 minuten).

Als je deze twee getallen gewoon bij elkaar optelt om de "beste" oplossing te vinden, negeert de computer de kosten volledig. Waarom? Omdat een verschil van €50 (van 10 naar 60) verwaarloosbaar klein is vergeleken met een verschil van 4000 minuten (van 1000 naar 5000). De computer denkt: "Ah, tijd is belangrijk, geld is niets."

Normaal gesproken proberen mensen dit op te lossen door de getallen te "normaliseren" (ze in een schaal van 0 tot 1 te zetten). Maar in dit artikel zeggen de auteurs: "Dat is lastig, want we weten vaak niet precies wat de absolute grenzen zijn (het maximum en minimum) van die problemen." Het is alsof je probeert de berg te meten zonder te weten hoe hoog de top is.

De Oplossing: De "Statistische Schaal"

De auteurs komen met een slimme truc: Standaardisatie.

In plaats van te kijken naar de grenzen van de getallen (het hoogste en laagste punt), kijken ze naar de verspreiding (de variantie).

• Denk aan een klaslokaal. Sommige leerlingen zijn allemaal ongeveer even lang (kleine verspreiding). Andere leerlingen hebben een enorme variatie in lengte (grote verspreiding).
• De auteurs zeggen: "Laten we alle doelen zo schalen dat ze allemaal even 'uitgebreid' zijn."

Ze gebruiken een wiskundige formule om precies te berekenen hoe willekeurig de uitkomsten van elk doel zijn. Vervolgens delen ze elk doel door die "willekeurigheid".

• Als een doel heel groot is maar heel voorspelbaar (weinig variatie), wordt het kleiner gemaakt.
• Als een doel klein is maar heel willekeurig (veel variatie), wordt het groter gemaakt.

Het resultaat: Alle doelen krijgen nu een "gelijk gewicht" in de ogen van de computer, ongeacht of ze oorspronkelijk in centen of in miljoenen werden gemeten. Het is alsof je alle ingrediënten in je recept eerst weegt en dan in gelijke porties verdeelt, zodat ze allemaal even belangrijk zijn.

Waarom is dit cool?

1. Het is exact: Ze hebben een formule bedacht die dit in één keer berekent, zonder dat ze het hele probleem eerst moeten oplossen (wat vaak onmogelijk is).
2. Het werkt snel: De berekening is snel genoeg voor grote problemen.
3. Het geeft betere resultaten: In hun experimenten (waar ze verschillende problemen combineerden, zoals het verdelen van influencers voor marketing of het plotten van routes) zagen ze dat hun methode veel "eerlijkere" oplossingen gaf. De computer koos niet meer automatisch voor het doel met de grootste getallen, maar vond een echte balans.

De Metafoor: De Weegschaal

Stel je een oude weegschaal voor.

• De oude manier: Je legt een veer op de ene kant en een bakstenen muur op de andere. De veer wordt genegeerd.
• De "normale" normalisatie: Je probeert de baksteen te hakken in stukjes die net zo groot zijn als de veer, maar je weet niet precies hoe zwaar de baksteen is, dus je hakt het verkeerd.
• De nieuwe manier (Standaardisatie): Je meet hoe "onrustig" de veer is en hoe "onrustig" de baksteen is. Je past de weegschaal zo aan dat de onrust van beide kanten gelijk is. Plotseling weegt de veer even zwaar als de baksteen, en de weegschaal is in evenwicht.

Conclusie

Deze paper zegt eigenlijk: "Als je meerdere doelen hebt die in verschillende eenheden worden gemeten, stop dan met gokken over hoe je ze moet vergelijken. Gebruik in plaats daarvan de statistische 'ruis' van de doelen om ze op één lijn te krijgen."

Dit maakt het makkelijker voor computers (en mensen) om eerlijke beslissingen te nemen in complexe situaties, zonder dat je eerst een expert moet zijn in het afwegen van elke variabele. Het is een simpele, maar krachtige manier om chaos in orde te brengen.

Technische samenvatting

Titel: Standaardisatie van Multi-Objective QUBO's

Auteurs: Loong Kuan Lee, Thore Gerlach, Nico Piatkowski (Fraunhofer IAIS & Universiteit Bonn)

---

1. Probleemstelling

Het artikel adresseert een fundamentele uitdaging binnen het domein van Multi-Objective Optimization (MOO) met Quadratic Unconstrained Binary Optimization (QUBO) problemen.

• Context: QUBO-problemen zijn NP-hard en vormen de basis voor veel combinatorische optimalisatietaken, waaronder die op kwantumcomputers (via Quantum Annealing) en digitale annealers.
• De Uitdaging: Bij multi-objective problemen (mQUBO) moeten meerdere, vaak conflicterende doelstellingen gelijktijdig worden geoptimaliseerd. Een groot probleem is dat deze doelstellingen vaak op verschillende schalen opereren (bijvoorbeeld één doelstelling varieert tussen 0 en 10, terwijl een andere tussen 0 en 1.000.000 varieert).
• Gevolg: Wanneer deze doelstellingen worden gecombineerd tot een enkel objectief (scalarisatie) om een oplossing te vinden, domineert de doelstelling met de grootste schaal de oplossing. Dit leidt tot onbalans en suboptimale trade-offs.
• Bestaande Oplossingen & Beperkingen:
  • Normering: Vaak wordt genormaliseerd door te delen door het bereik (max - min). Bij QUBO is het exact berekenen van het bereik echter equivalent aan het oplossen van het probleem zelf, wat onpraktisch is.
  • Schatting: Men kan schattingen gebruiken (zoals de "roof dual bound"), maar deze zijn vaak niet strak genoeg, wat kan leiden tot een onderschatting van de gewichten en daarmee weer tot onbalans.
  • Handmatige gewichten: Het handmatig kiezen van gewichten is tijdrovend en vereist vaak specifieke voorkeursinformatie die niet altijd beschikbaar is.

2. Methodologie

De auteurs stellen een nieuwe techniek voor: Standaardisatie van QUBO-doelstellingen. In plaats van te normaliseren naar een bereik [0,1], wordt elke doelstelling zo geschaald dat deze een variantie van 1 heeft (en een gemiddelde van 0).

• Aannames: De auteurs modelleren de oplossing $x$ als een steekproef uit een uniforme verdeling over de ruimte van alle mogelijke binaire vectoren ($X = \{0, 1\}^n$). Dit maximaliseert de entropie en maakt geen sterke aannames over de specifieke structuur van het probleem.
• Wiskundige Afleiding:
  • Ze leiden een gesloten vorm (closed-form expression) af voor het gemiddelde en de variantie van een QUBO-functie $f(x) = x^T Q x$ onder een uniforme verdeling.
  • Theorema 1: Biedt een formule voor het gemiddelde en de tweede moment (vereist voor variantie) met een complexiteit van $O(n^4)$.
  • Theorema 2: Biedt een geoptimaliseerde formule voor de variantie die gebruikmaakt van eigenschappen van onafhankelijke Bernoulli-variabelen ($p=0.5$). Dit reduceert de rekencomplexiteit tot $O(n^3)$.
• Algoritme: Er wordt een efficiënt algoritme gepresenteerd (zie Figuur 2 in het artikel) dat de variantie berekent door de covariantie-termen te groeperen, waardoor de berekening haalbaar wordt voor grotere $n$.
• Toepassing: De QUBO-matrices worden gedeeld door de berekende standaardafwijking ($\sigma$). Hierdoor worden alle doelstellingen op dezelfde schaal gebracht voordat ze worden opgeteld (lineaire scalarisatie).

3. Belangrijkste Bijdragen

1. Gesloten Formules: Afleiding van exacte formules voor het gemiddelde en de variantie van QUBO-objectieven onder een uniforme verdeling.
2. Efficiënt Algoritme: Een algoritme om deze variantie te berekenen met een complexiteit van $O(n^3)$, wat een aanzienlijke versnelling biedt ten opzichte van brute-force methoden.
3. Empirisch Bewijs: Experimenten die aantonen dat standaardisatie leidt tot meer gebalanceerde oplossingen in een "no-preference" setting (waar geen voorkeuren van de besluitvormer bekend zijn) vergeleken met ongecorrigeerde methoden of normalisatie via roof dual bounds.

4. Experimenten en Resultaten

De auteurs hebben hun methode getest op een reeks mQUBO-problemen, samengesteld uit verschillende combinaties van:

• Drie varianten van het Max-Cut probleem (MC[0,1], MC{0,1}, MC[1,5]) op Barabási-Albert-graaf.
• Een Subset Sum probleem (SubSum).

Opzet:

• Er werden 11 verschillende mQUBO-problemen gegenereerd (combinaties van 2, 3 of 4 doelstellingen).
• Drie schaalmethodes werden vergeleken:
  1. Geen schaling (Original).
  2. Normalisatie via Roof Dual Bound schatting.
  3. Standaardisatie (de voorgestelde methode).
• De oplossingen werden geoptimaliseerd met een digitale annealer (FPGA-gebaseerd).
• Maatstaf: De Hypervolume Indicator werd gebruikt om de kwaliteit en diversiteit van de gevonden Pareto-optimale oplossingssets te meten. Een hogere hypervolume betekent een betere set van trade-offs.

Resultaten:

• Algemene Superioriteit: Standaardisatie scoorde in bijna alle gevallen (zie Tabel I) significant hoger op de hypervolume-indicator dan de andere methoden. Dit impliceert dat de oplossingen een betere balans vinden tussen de verschillende doelstellingen.
• Uitzondering: Bij de combinatie van MC{0,1} en MC[1,5] presteerde de "geen schaling"-methode iets beter, maar het verschil was verwaarloosbaar (< 0,3%). De auteurs verklaren dit doordat deze twee problemen zeer vergelijkbaar zijn en hun schalen (bereik en variantie) al dicht bij elkaar liggen.
• Conclusie: Standaardisatie is robuust en effectief, zelfs wanneer de exacte ranges van de doelstellingen moeilijk te bepalen zijn.

5. Betekenis en Conclusie

Dit onderzoek biedt een praktische en wiskundig onderbouwde oplossing voor een veelvoorkomend probleem in multi-objective kwantum- en combinatorische optimalisatie.

• Voordeel: Het elimineert de noodzaak om handmatig gewichten te kiezen of onnauwkeurige schattingen (zoals roof dual bounds) te gebruiken voor normalisatie.
• Efficiëntie: De methode is computatie-efficiënt ($O(n^3)$) en kan exact worden uitgevoerd zonder het probleem zelf op te hoeven lossen.
• Toepassing: Het maakt het mogelijk om "no-preference" oplossingen te vinden die eerlijkere trade-offs bieden tussen conflicterende doelen. Dit is cruciaal voor toepassingen in finance, logistiek, chip-design en machine learning waar meerdere doelen tegelijkertijd moeten worden geoptimaliseerd zonder dat de besluitvormer vooraf specifieke voorkeuren moet specificeren.

Kortom, de auteurs bewijzen dat het standaardiseren van QUBO-doelstellingen op basis van hun variantie een superieure strategie is om gebalanceerde oplossingen te vinden in multi-objective scenario's.