Paper: Performance enhancing of hybrid quantum-classical Benders algorithm for MILP optimazation
Sergio López Baños · Elisabeth Lobe · Ontje Lünsdorf · Oriol Raventós
arXiv · 2026
Gemischt-ganzzahlige lineare Programmierprobleme werden in der Industrie für eine Vielzahl von Optimierungsaufgaben eingesetzt. Da sie jedoch immer größer werden, stellen sie für klassische Löser eine rechnerische Herausforderung innerhalb praktischer Zeitgrenzen dar. Quanten-Annealer können im Prinzip die Lösung von Problemen beschleunigen, die als quadratische, uneingeschränkte, binäre Optimierungsinstanzen formuliert sind, aber ihre begrenzte Skala verhindert derzeit das Erreichen praktischer Geschwindigkeitssteigerungen. Es wurden klassische Quantenalgorithmen vorgeschlagen, um die Vorteile beider Paradigmen zu nutzen und die Verwendung aktueller Quantencomputer für größere Probleme zu ermöglichen. In dieser Arbeit werden ein hardware-agnostischer Benders-Zerlegungsalgorithmus und eine Reihe von Erweiterungen vorgestellt, die darauf abzielen, die Vorteile des Quantencomputers optimal zu nutzen. Die Zerlegung besteht aus einem Hauptproblem mit ganzzahligen Variablen, das als quadratisches, uneingeschränktes binäres Optimierungsproblem umformuliert und mit einem Quantenglätter gelöst wird, und einem linearen Teilproblem, das von einem klassischen Computer gelöst wird. Die Verbesserungen bestehen unter anderem aus verschiedenen Einbettungsprozessen, die die Vorverarbeitungszeit der Einbettungsberechnung erheblich reduzieren, ohne die Lösungsqualität zu beeinträchtigen, einer konservativen Behandlung von Cut Beschränkungen und ein Abbruchkriterium, das die begrenzte Größe aktueller Quantencomputer und ihre heuristische Natur berücksichtigt. Der vorgeschlagene Algorithmus wird im Vergleich zu klassischen Ansätzen mit einem D-Wave-Quanten-Annealer für eine skalierbare Familie von Übertragungsnetzausbauplanungsproblemen getestet.
arXiv (2026)
https://arxiv.org/abs/2601.14024v1
