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

Ein 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 ${\displaystyle Q\in \mathbb {R} ^{n\times n}}$, einem Vektor ${\displaystyle d\in \mathbb {R} ^{n}}$ sowie einer Zahl ${\displaystyle c\in \mathbb {R} }$ darstellt werden als

${\displaystyle \mathrm {QUBO}$ :\qquad \min _{x\in \{0,1\}^{n}}x^{T}Qx+d^{T}x+c}

und in Summenschreibweise gilt

${\displaystyle \mathrm {QUBO}$ :\qquad \min _{x\in \{0,1\}^{n}}\sum _{i=1}^{n}\sum _{j=1}^{n}q_{ij}x_{i}x_{j}+\sum _{i=1}^{n}d_{i}x_{i}+c,} wobei ${\displaystyle q_{ij}}$ und ${\displaystyle d_{i}}$ für ${\displaystyle i,j\in \{1,\ldots ,n\}}$ die Einträge von ${\displaystyle Q}$ bzw. ${\displaystyle d}$ sind. Gesucht ist nun ein Optimalpunkt von QUBO, das heißt ein Punkt ${\displaystyle x^{\star }\in \{0,1\}^{n}}$ mit minimalem Zielfunktionswert. Die Anzahl der Elemente in der Menge ${\displaystyle \{0,1\}^{n}}$ ist ${\displaystyle 2^{n}}$, was impliziert, dass sie exponentiell in ${\displaystyle n}$ wächst.

Eigenschaften

• QUBO kann durch Negieren aller Vorzeichen äquivalent als Maximierungsproblem formuliert werden.
• Falls alle Koeffizienten positiv sind, ist ${\displaystyle x^{*}=(0,\dots ,0)}$ trivialerweise ein Optimalpunkt von QUBO. Analog dazu ist ${\displaystyle x^{*}=(1,\dots ,1)}$ optimal, falls alle Vorfaktoren negativ sind.
• Falls ${\displaystyle Q}$ eine Diagonalmatrix ist, ist das Optimierungsproblem separabel, was bedeutet, dass es in ${\displaystyle n}$ 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 ${\displaystyle {\mathcal {O}}(n)}$ und die optimalen Belegungen der Entscheidungsvariablen sind einfach ${\displaystyle x_{i}^{*}=1}$ falls ${\displaystyle q_{ii}<0}$ und ansonsten ${\displaystyle x_{i}^{*}=0}$.

QUBO und gemischt-ganzzahlige Optimierung

QUBO kann unter Einsatz eines Modellierungstricks als (restringiertes) ganzzahliges lineares Optimierungsproblem (ILP) formuliert werden.^[3] Dazu wird das Produkt ${\displaystyle x_{i}x_{j}}$ durch eine zusätzliche Binärvariable ${\displaystyle z_{ij}\in \{0,1\}}$ ersetzt und die Nebenbedingungen ${\displaystyle x_{i}\geq z_{ij}}$, ${\displaystyle x_{j}\geq z_{ij}}$ und ${\displaystyle x_{i}+x_{j}-1\leq z_{ij}}$ hinzugefügt. Das vollständige Optimierungsproblem lautet

${\displaystyle {\begin{aligned}\mathrm {QUBO_{ILP}}$ :\ \min _{x,z}\sum _{i=1}^{n}\sum _{j=1}^{n}q_{ij}z_{ij}+\sum _{i=1}^{n}d_{i}x_{i}+c\quad \mathrm {s.t.} \quad &x_{i},z_{ij}\in \{0,1\}\quad \forall i,j\in \{1,\ldots ,n\}\\&x_{i}\geq z_{ij}\quad \forall i,j\in \{1,\ldots ,n\}\\&x_{j}\geq z_{ij}\quad \forall i,j\in \{1,\ldots ,n\}\\&x_{i}+x_{j}-1\leq z_{ij}\quad \forall i,j\in \{1,\ldots ,n\}\end{aligned}}}

Man beachte, dass ${\displaystyle z_{ij}}$ auch als kontinuierliche Variable mit den Grenzen null und eins gewählt werden kann, da ${\displaystyle z_{ij}}$ 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

QUBO ist eng verwandt mit dem Ising-Modell in der theoretischen Physik, dessen Hamiltonoperator definiert ist als

${\displaystyle {\hat {\mathcal {H}}}=-{\frac {1}{2}}\sum _{i,j}J_{ij}s_{i}^{z}s_{j}^{z}-H_{z}\sum _{i=1}^{N}s_{i}^{z}}$

mit reellen Zahlen ${\displaystyle J_{ij}}$ und ${\displaystyle H_{z}}$. Die Spin-Variablen ${\displaystyle s_{i}^{z}\in \{-1,1\}}$ sind optimal zu wählen und sind in der ursprünglichen Beschreibung keine Binärvariablen. Eine Substitution der Spin-Variablen durch ${\displaystyle s_{i}^{z}=2x_{i}-1}$ mit ${\displaystyle x_{i}\in \{0,1\}}$ ergibt jedoch die Formulierung

${\displaystyle {\hat {\mathcal {H}}}=-{\frac {1}{2}}\sum _{i,j}J_{ij}(2x_{i}-1)(2x_{j}-1)-H_{z}\sum _{i=1}^{N}(2x_{i}-1)}$,

ohne die Werte der Funktion ${\displaystyle {\hat {\mathcal {H}}}}$ zu verändern, welche nun als quadratische Zielfunktion binärer Variablen in einem QUBO verwendet werden könnte.

QUBO und Quantencomputer

Ein 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

Anwendungsmöglichkeiten von QUBO

Viele 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

Binäres Clustering mit QUBO

Eine schlechte Cluster-Zuordnung

Eine gute Cluster-Zuordnung

Visuelle Darstellung eines Clusteringproblems mit 20 Punkten. Kreise derselben Farbe gehören zu demselben Cluster.

Um 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 ${\displaystyle D\in \mathbb {R} ^{20\times 2}}$beschrieben werden. Jeder Punkt soll einem von zweien Clustern zugeordnet werden, sodass benachbarte Punkte Teil desselben Clusters sind. Jedem Punkt wird eine Binärvariable ${\displaystyle x_{i}\in \{0,1\}}$ zugewiesen, die angibt, ob der Punkt in der ${\displaystyle i}$-ten Zeile von ${\displaystyle D}$ dem ersten (${\displaystyle x_{i}=0}$) oder zweiten Cluster (${\displaystyle x_{i}=1}$) 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 ${\displaystyle d_{ij}\geq 0}$ der Punkte ${\displaystyle i}$ und ${\displaystyle j}$ 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 ${\displaystyle i}$ und ${\displaystyle j}$ Teil desselben Clusters sind? Dies ist genau dann der Fall, wenn ${\displaystyle x_{i}=x_{j}=1}$ oder ${\displaystyle x_{i}=x_{j}=0}$ gilt. Alternativ und äquivalent lässt sich auch schreiben ${\displaystyle x_{i}x_{j}=1}$ oder ${\displaystyle (1-x_{i})(1-x_{j})=1}$.
• Umgekehrt sind die Punkte ${\displaystyle i}$ und ${\displaystyle j}$ in verschiedenen Clustern, falls ${\displaystyle x_{i}(1-x_{j})=1}$ oder ${\displaystyle (1-x_{i})x_{j}=1}$ 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

${\displaystyle {\begin{aligned}f(x)&=\sum _{i<j}d_{ij}(x_{i}x_{j}+(1-x_{i})(1-x_{j}))-d_{ij}(x_{i}(1-x_{j})+(1-x_{i})x_{j})\\&=\sum _{i<j}4d_{ij}x_{i}x_{j}-2d_{ij}x_{i}-2d_{ij}x_{j}+d_{ij}\end{aligned}}}$

und kann unter Verwendung der Matrix

${\displaystyle {\begin{aligned}Q_{ij}&={\begin{cases}d_{ij}&{\text{, wenn }}i\neq j\\-\left(\sum \limits _{k=1}^{i-1}d_{ki}+\sum \limits _{\ell =i+1}^{n}d_{i\ell }\right)&{\text{, wenn }}i=j\end{cases}}\end{aligned}}}$

auch in Matrix-Vektor-Schreibweise dargestellt werden.

Solver

• Alle Solver zur Lösung gemischt-ganzzahliger (linearer) Optimierungsprobleme wie CPLEX, Gurobi, CBC, GLPK, SCIP oder HiGHS
• Spezialisierte Solver für die Lösung von QUBOs wie QuBowl