Wo sollen Lagerhäuser stehen, und welche Kunden sollen sie versorgen? Schon diese alltäglich klingende Frage mischt zwei Arten von Entscheidungen. Ein Standort wird eröffnet oder nicht. Die Menge, die von dort zu einem Kunden gelangt, kann dagegen abgestuft sein. Wer beides in ein Rechenverfahren mit reinen Ja-Nein-Schaltern presst, schafft sich zusätzliche Arbeit.
Eine neue Studie von Taisei Takabayashi und Masayuki Ohzeki untersucht, wie sich ein Teil dieser Übersetzungsarbeit vermeiden lässt. Die kontinuierlichen Größen werden für eine bestimmte Problemklasse mathematisch behandelt, während das Suchverfahren nur die ursprünglichen binären Entscheidungen übernimmt. In den numerischen Versuchen entstehen dadurch häufiger zulässige Lösungen. Der interessante Fortschritt beginnt hier bei der Form des Problems, noch bevor die Wahl einer besonderen Rechenmaschine ins Spiel kommt.
Warum ein Mengenregler viele Schalter braucht
Die Studie arbeitet mit einer Form namens QUBO: quadratische Optimierung mit binären Variablen ohne ausdrücklich eingebaute Nebenbedingungen. Binär bedeutet, dass jede Variable nur zwei Werte annimmt. Quadratisch erlaubt neben dem Einfluss einzelner Entscheidungen auch Wechselwirkungen zwischen jeweils zwei Entscheidungen. So kann ein Modell berücksichtigen, dass zwei gewählte Standorte gemeinsam zusätzliche Kosten verursachen.
Die Welt hält sich selten an dieses Eingabeformat. Ein Lager soll eine bestimmte Nachfrage bedienen, eine Menge darf eine Grenze nicht überschreiten, und insgesamt sollen nur einige Standorte geöffnet werden. Solche Regeln müssen bei einer klassischen QUBO-Umformung über Strafkosten in der Zielfunktion wirksam werden. Eine unzulässige Antwort wird rechnerisch verteuert.
Kontinuierliche Mengen bereiten eine weitere Schwierigkeit. Man kann sie mit mehreren Bits annähern, ähnlich wie eine Folge von Schaltern unterschiedliche Zahlen codiert. Eine feinere Abstufung benötigt dabei mehr binäre Variablen. Mit ihnen wachsen die möglichen Kombinationen und oft auch die Verknüpfungen im Modell. Die offizielle Dokumentation von D-Wave zur Problemumformung beschreibt sowohl diese Vermehrung von Variablen als auch die nötige Abstimmung von Strafgewichten.
Eine hohe Strafe löst dabei nicht jede Schwierigkeit. Sie verändert das Verhältnis zwischen den eigentlichen Kosten und den Regeln. Ein Suchverfahren soll schließlich eine günstige zulässige Lösung finden, statt lediglich irgendeine Regelverletzung teuer zu bezahlen. Wie gut das gelingt, hängt auch von dieser mathematischen Landschaft ab.
Die Mengen verlassen den inneren Suchraum
Takabayashi und Ohzeki setzen an einer trennbaren Klasse gemischt binärer quadratischer Probleme an. Für festgehaltene Lagrange-Multiplikatoren lassen sich darin der binäre und der kontinuierliche Anteil getrennt behandeln. Die Multiplikatoren kann man sich als veränderliche Gewichte vorstellen, mit denen die Einhaltung der Nebenbedingungen in die Rechnung eingeht.
Der kontinuierliche Anteil wird bei der untersuchten Struktur analytisch ausintegriert. Er verschwindet dadurch nicht aus dem Gesamtproblem: Sein Beitrag fließt in die Aktualisierung dieser Gewichte ein. Das innere Suchverfahren erhält aber ein QUBO, das nur die ursprünglichen binären Variablen enthält. Es muss die Mengen nicht zusätzlich in Bitketten darstellen.
Der Ablauf pendelt zwischen beiden Aufgaben. Zunächst liefert ein QUBO-Sampler mehrere Kandidaten für die binären Entscheidungen. Daraus und aus dem analytisch berechneten kontinuierlichen Anteil entstehen Informationen für die nächste Gewichtsanpassung. Danach beginnt eine weitere Suchrunde. Für behaltene Standortkandidaten werden die kontinuierlichen Größen anschließend wieder bestimmt.
Das ist eine Aufteilung der Arbeit nach mathematischer Struktur. Ein größerer Computer müsste einen unnötig aufgeblähten Suchraum ebenfalls durchsuchen. Eine passende Formulierung spart diesen Umweg schon beim Aufstellen der Aufgabe. Ob sie insgesamt schneller ist, entscheidet dann die gesamte Schleife einschließlich der äußeren Aktualisierungen.
Was die Standortversuche tatsächlich vergleichen
Als Test dient eine kontinuierliche Relaxation des quadratischen p-Median-Problems. Darin werden Standorte ausgewählt und Nachfrageanteile zugeordnet; zusätzlich gibt es Wechselwirkungskosten zwischen geöffneten Standorten. Die Testfälle wurden synthetisch erzeugt. Das erlaubt kontrollierte Vergleiche unterschiedlich großer Instanzen, beschreibt aber keinen Einsatz in einem konkreten Logistikbetrieb.
Der akzeptierte Volltext in Scientific Reports, veröffentlicht am 17. Oktober 2026, vergleicht drei Alternativen: eine QUBO-Fassung mit Strafkosten, eine lokale Suche über Standortmengen und den kommerziellen Optimierer Gurobi. Das neue Verfahren erzeugt gegenüber der Strafkostenfassung zuverlässiger zulässige Antworten. Bei geeigneter Einstellung erreicht es in den untersuchten größeren Fällen auch günstigere Fehlerwerte als die lokale Suche.
Für die Qualitäts- und Zulässigkeitsvergleiche verwendet das neue Verfahren höchstens 30 Multiplikatorrunden mit jeweils 1.000 QUBO-Stichproben. Die Strafkostenfassung erhält 30.000 Stichproben, die lokale Suche 30.000 Versuche. Das ist ein nachvollziehbarer Vergleich von Suchbudgets. Gleiche Versuchszahlen bedeuten allerdings noch keine identische Rechenarbeit pro Versuch; deshalb betrachtet die Studie zusätzlich Laufzeiten.
Der eingestellte inverse Temperaturparameter beeinflusst zwei Dinge zugleich: die Konzentration der binären Suche auf günstige Zustände und die Behandlung des kontinuierlichen Anteils. Dadurch können Qualität und Zulässigkeit gegeneinander arbeiten. Eine einzige möglichst scharfe Suche ist deshalb nicht automatisch die beste Wahl. Die Autoren sehen eine adaptive Einstellung als weitere Forschungsaufgabe.
Geschwindigkeit braucht ein Ziel und eine Erfolgsquote
Wie lange ein Optimierer benötigt, lässt sich sinnvoll erst mit der verlangten Antwortgüte vergleichen. Wer nach einer brauchbaren Lösung aufhört, ist früher fertig als jemand, der zusätzlich deren globale Optimalität beweisen muss. Die Studie trennt diese Aufgaben in ihren Zeitvergleichen ausdrücklich.
Für kleinere Fälle, deren Optimum bestimmt werden konnte, werden gemeinsame relative Fehlerziele gesetzt. Berichtet werden sowohl die Zeit erfolgreicher Läufe bis zum Ziel als auch der Anteil der Läufe, die es überhaupt erreichen. Gerade bei zufallsbasierten Suchverfahren gehört beides zusammen. Ein schneller Treffer und viele gescheiterte Versuche ergeben eine andere Betriebssituation als ein ähnlich schneller, verlässlicher Lauf.
Für größere Fälle fehlt teilweise ein innerhalb des Zeitlimits bestätigtes Optimum. Dort dient die vom neuen Verfahren erreichte zulässige Lösung als Ziel, das Gurobi einholen soll. Dieser Versuch beantwortet die konkrete Frage nach der Zeit bis zu dieser Lösungsgüte. Seine Aussage unterscheidet sich vom Vergleich gegen ein bekanntes Optimum. Auch die Darstellung von Läufen, die ihr Ziel innerhalb von 600 Sekunden verfehlen, ist deshalb Teil des Befunds.
Die Rechenmaschine erklärt den Vorteil mit
Alle Versuche liefen auf einem klassischen Rechner mit Apple-M3-Prozessor und 16 Gigabyte Arbeitsspeicher. Als innerer Sampler diente simuliertes Quantenannealing mit OpenJij. Es bildet einen quantenphysikalisch motivierten Suchprozess auf klassischer Hardware nach. Das äußere Verfahren ist laut Studie vom gewählten Sampler unabhängig.
Für Gurobi wurde ein Thread eingestellt und die Suche auf das Finden guter zulässiger Lösungen ausgerichtet. Für OpenJij und die numerischen Python-Bibliotheken gab es keine ausdrücklich gesetzte Threadbegrenzung. Damit gehört die Softwarekonfiguration zur Interpretation des gemessenen Laufzeitabstands. Der Befund zeigt, was diese Formulierung in diesem Versuch leistet; ein anderer Sampler oder ein anders konfigurierter Vergleichsoptimierer ist eine weitere konkrete Untersuchung.
Auch die Trennbarkeit bleibt eine entscheidende Voraussetzung. Sind die kontinuierlichen Größen so mit dem Rest verwoben, dass ihr Beitrag nicht einfach berechnet werden kann, entsteht an dieser Stelle neue Rechenarbeit. Eine allgemeinere Aufgabenklasse kann deshalb andere Integrations- oder Näherungsverfahren verlangen.
Die verständliche Einsicht reicht dennoch über das Testproblem hinaus: Bei einer schweren Suche lohnt es sich, zuerst die Darstellung der Aufgabe zu untersuchen. Standortentscheidungen und Mengen müssen gemeinsam stimmen. Sie müssen aber nicht zwangsläufig durch denselben engen binären Suchraum wandern.
Quellen
- Taisei Takabayashi und Masayuki Ohzeki: QUBO sampling for mixed binary quadratic programming without continuous variable binarization, Scientific Reports, akzeptierte Frühfassung, veröffentlicht am 17. Oktober 2026; Original und Volltext am 18. Oktober 2026 gelesen.
- D-Wave: Reformulating a Problem, offizielle laufende Dokumentation, abgerufen am 18. Oktober 2026.
Für diesen Artikel wurden KI-gestützte Recherche- und Editierwerkzeuge verwendet. Der Inhalt wurde redaktionell geprüft.
