QUBO Generator

Einige Anwendungsfälle lassen sich als ein Quadratic unconstrained binary optimization (QUBO) Problem formulieren. Für die Erzeugung des QUBO steht dieser Generator als Python Package zur Verfügung.

Was ist ein QUBO?

Quadratic Unconstrained Binary Optimization (kurz QUBO) ist ein Model, das zur Darstellung von einigen kombinatorischen Optimierungsproblemen verwendet wird. Das QUBO Model wird folgendermaßen dargestellt:


x{0, 1} xTQx,


wobei x ein Vektor von Binärvariablen und Q eine quadratische Matrix ist. 


Die Matrix muss entweder symmetrisch oder eine obere Dreiecksmatrix sein. Wie ein QUBO aufgestellt wird kann hier in dem Paper nachgelesen werden. Die Implementierung des QUBO Generators entspricht dem Verfahren in dem Paper.

(Bemerkung: Die Slack Variablen, die zum auffüllen der Nebenbedingungen mit Ungleichungen dienen, werden unabhängig von den anderen Nebenbedingungen berechnet.)


Input:

Zur Erstellung einer QUBO Matrix mithilfe des QUBO Generators müssen zunächst Variablen mithilfe des Klasse symbols/Symbol aus der Library sympy erzeugt werden. Mithilfe dieser Variablen stellt man seine Funktion und die Nebenbedingungen zusammen. Die Funktion wird dem Objekt QUBOModel übergeben und die Nebenbedingungen werden dann mithilfe der Methode add_constraint hinzugefügt.

Output:

Der QUBO Generator berechnet darauf die Matrix Q (QUBO Matrix) aus dem Objekt QUBOModel mithilfe der Methode model_to_qubo.

Project Numbers

live

hoch

hoch