Quadratische unrestringierte binäre Optimierung
In der quadratischen unrestringierten binären Optimierung (QUBO), auch bekannt als unrestringierte binäre quadratische Optimierung (UBQP), werden Optimierungsprobleme untersucht, die binäre Entscheidungsvariablen, eine quadratische Zielfunktion, jedoch keine Nebenbedingungen besitzen. QUBO ist Teil der mathematischen Optimierung mit Anwendungen unter anderem in Finanzen, Wirtschaft und maschinelles Lernen.[1] Einige klassische Probleme der theoretischen Informatik wie Maximaler Schnitt, Färbung und das Partitionsproblem lassen sich als QUBO formulieren, weshalb es sich um eine NP-schwere Problemklasse handelt.[2] Es bestehen außerdem enge Zusammenhänge zum Ising-Modell der theoretischen Physik und dadurch zu Quantencomputern, insbesondere zu Optimierungsmethoden wie Quantum Annealing. QUBO kann als quadratisches oder, nach Umformulierungen, auch als lineares ganzzahliges Optimierungsproblem modelliert und mit den Methoden der gemischt-ganzzahligen Optimierung gelöst werden.
Definition
BearbeitenEin quadratisches unrestringiertes Optimierungsproblem (QUBO) besteht aus einer quadratischen Zielfunktion und binären Entscheidungsvariablen. Es enthält keine Nebenbedingungen. In Matrix-Vektor-Schreibweise kann es mit einer Matrix , einem Vektor sowie einer Zahl darstellt werden als
und in Summenschreibweise gilt
wobei und für die Einträge von bzw. sind. Gesucht ist nun ein Optimalpunkt von QUBO, das heißt ein Punkt mit minimalem Zielfunktionswert. Die Anzahl der Elemente in der Menge ist , was impliziert, dass sie exponentiell in wächst.
Eigenschaften
Bearbeiten- QUBO kann durch Negieren aller Vorzeichen äquivalent als Maximierungsproblem formuliert werden.
- Falls alle Koeffizienten positiv sind, ist trivialerweise ein Optimalpunkt von QUBO. Analog dazu ist optimal, falls alle Vorfaktoren negativ sind.
- Falls eine Diagonalmatrix ist, ist das Optimierungsproblem separabel, was bedeutet, dass es in unabhängige Optimierungsprobleme zerfällt, die getrennt gelöst werden können, da die Entscheidungsvariablen sich gegenseitig nicht beeinflussen. Dieses Problem ist lösbar in und die optimalen Belegungen der Entscheidungsvariablen sind einfach falls und ansonsten .
QUBO und gemischt-ganzzahlige Optimierung
BearbeitenQUBO kann unter Einsatz eines Modellierungstricks als (restringiertes) ganzzahliges lineares Optimierungsproblem (ILP) formuliert werden.[3] Dazu wird das Produkt durch eine zusätzliche Binärvariable ersetzt und die Nebenbedingungen , und hinzugefügt. Das vollständige Optimierungsproblem lautet
Man beachte, dass auch als kontinuierliche Variable mit den Grenzen null und eins gewählt werden kann, da durch die Nebenbedingungen keine Werte annehmen kann, die nicht ganzzahlig sind. Diese Formulierung würde in einem linearen gemischt-ganzzahligen Optimierungsproblem (MILP) resultieren, da nun nicht mehr alle Variablen ganzzahlig sind. Für die Lösung von (M)ILP-Modellen können neben (Meta-)Heuristiken exakte Methoden wie Branch-and-Cut- sowie Branch-and-Bound-Verfahren angewandt werden, die zwar eine theoretisch schlechte Worst-Case-Laufzeit besitzen, aber effizient in kommerziellen und freien Paketen wie CPLEX, Gurobi und SCIP implementiert sind und somit oft die Lösung praxisüblicher QUBO-Instanzen ermöglichen.
QUBO und das Ising-Modell
BearbeitenQUBO ist eng verwandt mit dem Ising-Modell in der theoretischen Physik, dessen Hamiltonoperator definiert ist als
mit reellen Zahlen und . Die Spin-Variablen sind optimal zu wählen und sind in der ursprünglichen Beschreibung keine Binärvariablen. Eine Substitution der Spin-Variablen durch mit ergibt jedoch die Formulierung
,
ohne die Werte der Funktion zu verändern, welche nun als quadratische Zielfunktion binärer Variablen in einem QUBO verwendet werden könnte.
QUBO und Quantencomputer
BearbeitenEin weiterer Lösungsansatz besteht darin, QUBO auf Quantencomputern zu modellieren und zu lösen. Hierbei wird für die Modellierung jeder Binärvariable ein Qubit verwendet. Beliebte Lösungsmethoden sind hierbei Heuristiken wie das Quantum Annealing.[4]
Anwendungen
BearbeitenAnwendungsmöglichkeiten von QUBO
BearbeitenViele Anwendungen lassen sich formal als QUBO modellieren[5], was aber nicht bedeutet, dass diese Anwendungen auch durch das Berechnen eines globalen Optimalpunkts des QUBOs gelöst werden. Das gilt auch für das kommende Beispiel aus dem Bereich Clusteranalyse, welches sich zwar als QUBO formulieren lässt, aber in der Praxis in der Regel mit effizienten Heuristiken wie der K-Means-Methode gelöst wird.
Clusteranalyse
BearbeitenUm zu illustrieren, wie ein Anwendungsproblem als QUBO modelliert werden kann, wird die Clusteranalyse betrachtet. Hier sind 20 Punkte in der Ebene gegeben, deren Koordinaten durch eine Matrix beschrieben werden. Jeder Punkt soll einem von zweien Clustern zugeordnet werden, sodass benachbarte Punkte Teil desselben Clusters sind. Jedem Punkt wird eine Binärvariable zugewiesen, die angibt, ob der Punkt in der -ten Zeile von dem ersten ( ) oder zweiten Cluster ( ) zugeordnet wird. Insgesamt ergeben sich dadurch also 20 Binärvariablen, die optimal zu wählen sind, wobei noch zu klären ist, was "Optimalität" hier genau bedeutet.
Eine Möglichkeit Cluster zu bestimmen, ist den paarweisen euklidischen Abstand der Punkte und zueinander zu betrachten. Die Grundidee ist es nun, Cluster so zu wählen, dass die Abstände zwischen Punkten desselben Clusters möglichst gering und zwischen Punkten verschiedener Cluster möglichst groß sind.
- Woran erkennt man, dass die Punkte und Teil desselben Clusters sind? Dies ist genau dann der Fall, wenn oder gilt. Alternativ und äquivalent lässt sich auch schreiben oder .
- Umgekehrt sind die Punkte und in verschiedenen Clustern, falls oder gilt.
Die zu minimierende Zielfunktion besteht nun also aus den aufsummierenden Abstände innerhalb eines Clusters, wovon die gesamten Abstände zwischen den beiden Clustern subtrahiert werden. In Summenschreibweise lautet die Zielfunktion
und kann unter Verwendung der Matrix
auch in Matrix-Vektor-Schreibweise dargestellt werden.
Solver
BearbeitenEinzelnachweise
Bearbeiten- ↑ Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, Yang Wang: The unconstrained binary quadratic programming problem: a survey. In: Journal of Combinatorial Optimization. Band 28, Nr. 1, Juli 2014, ISSN 1382-6905, S. 58–81, doi:10.1007/s10878-014-9734-0 (springer.com [abgerufen am 8. Januar 2024]).
- ↑ Andrew Lucas: Ising formulations of many NP problems. In: Frontiers in Physics. Band 2, 2014, ISSN 2296-424X, doi:10.3389/fphy.2014.00005.
- ↑ Nathan Georg Sudermann-Merx: Einführung in Optimierungsmodelle: mit Beispielen und Real-World-Anwendungen in Python. Springer Spektrum, Berlin / Heidelberg 2023, ISBN 978-3-662-67380-5.
- ↑ Fred Glover, Gary Kochenberger, Yu Du: Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. In: 4OR. Band 17, Nr. 4, 26. November 2019, ISSN 1619-4500, S. 335–371, doi:10.1007/s10288-019-00424-y.
- ↑ Daniel Ratke: List of QUBO formulations. 10. Juni 2021, abgerufen am 16. Dezember 2022.