Prof. Hans Mittelmann von der Arizona State University hat seine weithin anerkannten Benchmarks um Quadratic Unconstrained Binary Optimization (QUBO) Probleme erweitert. Mit dem wachsenden Interesse am Quantencomputing ist QUBO als potentielleLösung für komplexe Optimierungsprobleme ins öffentliche Bewusstsein gerückt, da Quantum Annealer approximative Lösungen für QUBOs finden können
Der QuBowl QUBO- und MaxCut-Solver, der vom SynLab des Forschungscampus MODAL in Zusammenarbeit mit der Abteilung für Methoden der Angewandten Algorithmischen Intelligenz am ZIB und der i2damo GmbH entwickelt wurde, bietet eine hocheffektive Lösung für diese Probleme. Der QuBowl-Solver hat die Konkurrenz im Nonconvex QUBO-QPLIB Benchmark übertroffen und 15 von 23 QUBO-Problemen zu globaler Optimalität gelöst.
“Wir sind sehr zufrieden, dass unser Löser zu den besten gehört, die es gibt, um nachweislich optimale Lösungen für QUBO-Probleme zu berechnen”, sagt Daniel Rehfeldt. “Im Gegensatz zu heuristischen Lösern bietet QuBowl eine garantiert beste Lösung und ist auch der insgesamt schnellste Löser im Benchmark.”
QuBowl bietet fortgeschrittende algorithmische Komponenten zur Lösung von unbeschränkten binären Problemen, wie z. B. Reduktionstechniken und Algorithmen zur Zerlegung von Schnittflächen. Diese Komponenten werden in einem exakten Branch-and-Cut-Löser mit einer parallelen Implementierung kombiniert, was QuBowl zu einer hocheffizienten Lösung für QUBO-Probleme macht. Die Ergebnisse dieser laufenden Zusammenarbeit sind zur Veröffentlichung in Mathematical Programming Computation angenommen worden.
Links:
https://arxiv.org/abs/2202.02305
http://plato.asu.edu/ftp/qubo.html
http://qplib.zib.de/