Forscher nähern sich neuem Tempolimit für bahnbrechendes Problem | Quanta-Magazin

Das Problem des Handlungsreisenden ist eine der ältesten bekannten Rechenfragen. Es fragt nach der idealen Route durch eine bestimmte Liste von Städten und minimiert so den Kilometeraufwand. Obwohl das Problem einfach erscheint, ist es bekanntermaßen schwierig. Während Sie mit roher Gewalt alle möglichen Routen prüfen können, bis Sie den kürzesten Weg gefunden haben, ist eine solche Strategie bereits nach wenigen Städten unhaltbar. Stattdessen können Sie ein strenges mathematisches Modell namens lineare Programmierung anwenden, das das Problem grob als eine Reihe von Gleichungen annähert und die möglichen Kombinationen methodisch prüft, um die beste Lösung zu finden.

Aber manchmal müssen Sie bei Problemen mit ganzzahligen Beträgen eine Optimierung durchführen. Was nützt ein Fabrikoptimierungsplan, der 500.7 Sofas herstellt? Zu diesem Zweck greifen Forscher häufig auf eine Variante der linearen Programmierung namens „ ganzzahlige lineare Programmierung (ILP). Es ist beliebt bei Anwendungen, die diskrete Entscheidungen erfordern, einschließlich der Produktionsplanung, der Personaleinsatzplanung von Fluggesellschaften und der Fahrzeugroutenplanung. „Im Grunde ist ILP sowohl in der Theorie als auch in der Praxis das A und O des Operations Research“, sagte er Santosh Vempala, Informatiker am Georgia Institute of Technology.

Seit sie ILP zum ersten Mal formuliert haben vor über 60 JahrenForscher haben verschiedene Algorithmen entdeckt, die ILP-Probleme lösen, aber alle waren im Hinblick auf die Anzahl der erforderlichen Schritte relativ langsam. Die beste Version, die sie sich vorstellen konnten – eine Art Geschwindigkeitsbegrenzung – stammt aus dem trivialen Fall, dass die Variablen des Problems (z. B. ob ein Verkäufer eine Stadt besucht oder nicht) nur binäre Werte (Null oder 1) annehmen können. In diesem Fall verfügt ILP über eine Laufzeit, die exponentiell mit der Anzahl der Variablen, auch Dimension genannt, skaliert. (Wenn es nur eine Variable gibt, sind nur zwei Schritte erforderlich, um jede mögliche Kombination zu testen und das Problem zu lösen; zwei Variablen bedeuten vier Schritte, drei bedeuten acht Schritte und so weiter.)

Sobald die Variablen einen Wert über Null und Eins annehmen, verlängert sich leider die Laufzeit des Algorithmus erheblich. Forscher fragen sich schon lange, ob sie dem trivialen Ideal näher kommen könnten. Die Fortschritte waren langsam Rekord spielt in den 1980er Jahren und ist nur inkrementell Verbesserungen seitdem gemacht.

Aber kürzlich Arbeit by Victor Reis, derzeit am Institute for Advanced Study, und Thomas Rothvoss, an der University of Washington, hat den größten Laufzeitsprung seit Jahrzehnten gemacht. Durch die Kombination geometrischer Werkzeuge zur Begrenzung der möglichen Lösungen erstellten sie einen neuen, schnelleren Algorithmus zur Lösung von ILP in fast derselben Zeit wie der triviale Binärfall. Das Ergebnis wurde beim 2023 mit einem Best-Paper-Award ausgezeichnet Grundlagen der Informatik Konferenz.

„Dieser neue Algorithmus ist äußerst aufregend“, sagte er Noah Stephens-Davidowitz, Mathematiker und Informatiker an der Cornell University. „Es stellt die erste [große] Verbesserung der ILP-Löser seit fast 40 Jahren dar.“

ILP funktioniert, indem es ein gegebenes Problem in einen Satz linearer Gleichungen umwandelt, die einige Ungleichungen erfüllen müssen. Die spezifischen Gleichungen basieren auf den Details des ursprünglichen Problems. Obwohl sich diese Details unterscheiden können, bleibt der grundlegende Aufbau von ILP-Problemen derselbe und bietet Forschern eine einzige Möglichkeit, eine Vielzahl von Problemen anzugehen.

Das heißt nicht, dass es eine leichte Arbeit ist. Erst 1983 wurde der Mathematiker Hendrik Lenstra erwies sich dass das allgemeine Problem überhaupt lösbar war und der erste Algorithmus bereitgestellt wurde, der dies konnte. Lenstra dachte geometrisch über ILP nach. Zunächst verwandelte er die Ungleichungen im Herzen von ILP in eine konvexe Form, beispielsweise in ein beliebiges regelmäßiges Polygon. Diese Form stellt die Einschränkungen des einzelnen Problems dar, das Sie lösen, sei es die Herstellung von Sofas oder die Planung von Fluglinien. Das Innere der Form entspricht also allen möglichen Werten, die die Ungleichungen und damit das Problem lösen könnten. Lenstra nannte diese Form den konvexen Körper. Die Dimension des Problems beeinflusst die Dimension dieser Form: Mit zwei Variablen nimmt sie die Form eines flachen Polygons an; in drei Dimensionen ist es ein Platonischer Feststoff, Und so weiter.

Als nächstes stellte sich Lenstra alle ganzen Zahlen als eine unendliche Menge von Gitterpunkten vor, die in der Mathematik als Gitter bekannt sind. Eine zweidimensionale Version sieht aus wie ein Meer aus Punkten, und in drei Dimensionen sieht es aus wie die Verbindungspunkte von Stahlträgern in einem Gebäude. Die Dimension des Gitters hängt auch von der Dimension eines gegebenen Problems ab.

Um ein gegebenes ILP-Problem zu lösen, zeigte Lenstra, dass man einfach danach sucht, wo die möglichen Lösungen die Menge der ganzen Zahlen treffen: am Schnittpunkt des konvexen Körpers und des Gitters. Und er entwickelte einen Algorithmus, der diesen Raum umfassend durchsuchen konnte – aber um effektiv zu sein, musste er das Problem manchmal in Teile kleinerer Dimensionen zerlegen, was die Laufzeit um viele Schritte verlängerte.

In den folgenden Jahren untersuchten mehrere Forscher, wie dieser Algorithmus schneller ausgeführt werden kann. 1988 führten Ravi Kannan und László Lovász ein Konzept namens „Abdeckungsradius“ ein. ausgeliehen aus dem Studium von fehlerkorrigierende Codes, um den konvexen Körper und das Gitter effizienter zu schneiden. Grob gesagt stellt der Überdeckungsradius sicher, dass der konvexe Körper immer mindestens einen ganzzahligen Punkt enthält, egal wo man ihn auf dem Gitter platziert. Die Größe des Abdeckungsradius bestimmt somit auch, wie effizient Sie das ILP-Problem lösen können.

Es kam also darauf an, die Größe des idealen Überdeckungsradius zu bestimmen. Leider erwies sich dies allein schon als schwieriges Problem, und das Beste, was Kannan und Lovász tun konnten, war, einen möglichen Wert einzugrenzen, indem sie nach Ober- und Untergrenzen suchten. Sie zeigten, dass die Obergrenze – die maximale Größe des Abdeckungsradius – linear mit der Abmessung skaliert. Das war ziemlich schnell, aber nicht genug, um die ILP-Laufzeit deutlich zu beschleunigen. Andere Forscher könnten in den nächsten 30 Jahren nur geringfügig besser abschneiden.

Was Reis und Rothvoss letztendlich zum Durchbruch verhalf, war ein unabhängiges mathematisches Ergebnis, das sich ausschließlich auf Gitter konzentrierte. Im Jahr 2016 Oded Regev und Stephens-Davidowitz zeigte, also wie viele Gitterpunkte in eine bestimmte Form passen könnten. Reis und Rothvoss wandten dies auf andere Formen an, wodurch sie die Anzahl der in einem ILP-Abdeckungsradius enthaltenen Gitterpunkte besser abschätzen konnten, wodurch die Obergrenze gesenkt wurde. „Der jüngste Durchbruch kam mit der Erkenntnis, dass man tatsächlich andere Arten von Formen herstellen kann“, sagte Regev.

Diese neue verschärfte Obergrenze stellte eine enorme Verbesserung dar und ermöglichte es Reis und Rothvoss, eine dramatische Beschleunigung des gesamten ILP-Algorithmus zu erreichen. Ihre Arbeit bringt die Laufzeit auf (log n)^O(n), Wobei n ist die Anzahl der Variablen und O (n)bedeutet, dass es linear mit skaliert n. (Dieser Ausdruck wird als „fast“ identisch mit der Laufzeit des Binärproblems angesehen.)

„Es ist ein Triumph an der Schnittstelle von Mathematik, Informatik und Geometrie“, sagte er Daniel Dadush vom nationalen Forschungsinstitut CWI in den Niederlanden, der Pionierarbeit bei dem Algorithmus leistete, den Reis und Rothvoss zur Messung der ILP-Laufzeit verwendeten.

Bisher wurde der neue Algorithmus noch nicht zur Lösung logistischer Probleme eingesetzt, da die Aktualisierung heutiger Programme zu aufwändig wäre, um ihn nutzen zu können. Aber für Rothvoss ist das nebensächlich. „Es geht um das theoretische Verständnis eines Problems, das grundlegende Anwendungen hat“, sagte er.

Was die Frage betrifft, ob die Recheneffizienz von ILP weiter verbessert werden könnte, sind die Forscher immer noch zuversichtlich, dass sie sich weiterhin der idealen Laufzeit nähern – aber nicht so schnell. „Das würde eine grundlegend neue Idee erfordern“, sagte Vempala.