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

$\mathrm{Q}\mathrm{U}\mathrm{B}\mathrm{O}:\underset{x\in \{0,1{\}}^n}{\min }{x}^{T}Qx+d^{T}x+c$

und in Summenschreibweise gilt

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

Eigenschaften

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

QUBO und gemischt-ganzzahlige Optimierung

QUBO kann unter Einsatz eines Modellierungstricks als (restringiertes) ganzzahliges lineares Optimierungsproblem (ILP) formuliert werden. Dazu wird das Produkt $x_i{x}_j$ durch eine zusätzliche Binärvariable $z_{ij}\in \{0,1\}$ ersetzt und die Nebenbedingungen $x_i\ge z_{ij}$, $x_j\ge z_{ij}$ und $x_i+x_j-1\le z_{ij}$ hinzugefügt. Das vollständige Optimierungsproblem lautet

$\begin{array}{cc}\mathrm{Q}\mathrm{U}\mathrm{B}{\mathrm{O}}_{\mathrm{I}\mathrm{L}\mathrm{P}}:\underset{x,z}{\min }\sum _{i=1}^n\sum _{j=1}^n{q}_{ij}{z}_{ij}+\sum _{i=1}^n{d}_i{x}_i+c\mathrm{s}\mathrm{.}\mathrm{t}\mathrm{.}& x_i,z_{ij}\in \{0,1\}\mathrm{\forall }i,j\in \{1,\dots ,n\}\\ & x_i\ge z_{ij}\mathrm{\forall }i,j\in \{1,\dots ,n\}\\ & x_j\ge z_{ij}\mathrm{\forall }i,j\in \{1,\dots ,n\}\\ & x_i+x_j-1\le z_{ij}\mathrm{\forall }i,j\in \{1,\dots ,n\}\end{array}$

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

$\hat{\mathscr{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 $J_{ij}$ und $H_z$. Die Spin-Variablen $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 $s_i^z=2x_i-1$ mit $x_i\in \{0,1\}$ ergibt jedoch die Formulierung

$\hat{\mathscr{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 $\hat{\mathscr{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.

Anwendungen

Anwendungsmöglichkeiten von QUBO

Viele Anwendungen lassen sich formal als QUBO modellieren, 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

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 $D\in {ℝ}^{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 $x_i\in \{0,1\}$ zugewiesen, die angibt, ob der Punkt in der $i$-ten Zeile von $D$ dem ersten ($x_i=0$) oder zweiten Cluster ($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 $d_{ij}\ge 0$ der Punkte $i$ und $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 $i$ und $j$ Teil desselben Clusters sind? Dies ist genau dann der Fall, wenn $x_i=x_j=1$ oder $x_i=x_j=0$ gilt. Alternativ und äquivalent lässt sich auch schreiben $x_i{x}_j=1$ oder $(1-x_i)(1-x_j)=1$.
• Umgekehrt sind die Punkte $i$ und $j$ in verschiedenen Clustern, falls $x_i(1-x_j)=1$ oder $(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

$\begin{array}{cc}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{array}$

und kann unter Verwendung der Matrix

$\begin{array}{cc}{Q}_{ij}& =\{\begin{array}{cc}{d}_{ij}& \text{, wenn }i\ne j\\ -(\sum _{k=1}^{i-1}{d}_{ki}+\sum _{\ell =i+1}^n{d}_{i\ell })& \text{, wenn }i=j\end{array}\end{array}$

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