- Für Optimierungsprobleme, die Entscheidungen in ganzzahligen Einheiten erfordern – etwa Produktionsplanung, Crew-Einsatzplanung oder Fahrzeugrouten –, stellen Victor Reis und Thomas Rothvoss einen neuen Algorithmus vor, der die Laufzeit von ILP deutlich senkt
- ILP ist anspruchsvoller als allgemeines Linear Programming, und seit den 1980er-Jahren gab es kaum rekordverdächtige Verbesserungen; deshalb gilt dieses Ergebnis als großer Fortschritt nach Jahrzehnten
- Der neue Ansatz kombiniert geometrische Werkzeuge, die den Schnitt von Gittern und konvexen Körpern behandeln, und grenzt den Bereich möglicher ganzzahliger Lösungen stärker ein
- Der Kern liegt darin, mithilfe eines Ergebnisses von 2016 zu Gitterpunkten die Obergrenze des covering radius zu senken; die Laufzeit sinkt auf ein Niveau von ((\log n)^{O(n)})
- Zwar wird der Ansatz noch nicht direkt in realen Logistiksystemen eingesetzt, doch als Ergebnis, das der theoretischen Geschwindigkeitsgrenze von ILP sehr nahekommt, zeigt er eine langfristige Richtung für Verbesserungen praktischer Solver auf
Warum Ganzzahligkeitsbeschränkungen Optimierung erschweren
- Das Traveling-Salesman-Problem ist ein altes Rechenproblem, bei dem die kürzeste Route durch mehrere Städte gesucht wird; prüft man alle möglichen Routen, wird das schon bei einer nur leicht steigenden Zahl von Städten unbeherrschbar
- Linear Programming ist ein mathematisches Modell, das mögliche Kombinationen mithilfe von Gleichungen und Ungleichungen systematisch behandelt
- Bei realen Optimierungsproblemen sind Antworten mit Dezimalstellen oft nutzlos
- In einem Optimierungsplan für eine Fabrik ist die Antwort, 500,7 Sofas zu produzieren, als reale Entscheidung schwer verwendbar
- Integer Linear Programming (ILP) ist eine Variante des Linear Programming mit solchen Ganzzahligkeitsbeschränkungen und wird breit für diskrete Entscheidungsprobleme wie Produktionsplanung, Crew-Planung bei Airlines und Fahrzeugrouting eingesetzt
- Santosh Vempala sieht ILP als zentrales Werkzeug des Operations Research, sowohl in der Theorie als auch in der Praxis
Seit den 1980er-Jahren nur langsam verbesserte Geschwindigkeitsgrenze
- Seit ILP vor mehr als 60 Jahren formalisiert wurde, sind mehrere Algorithmen entstanden, doch gemessen an der Zahl der nötigen Schritte ist es weiterhin eher langsam
- Der einfachste Bezugspunkt ist der Fall von binären Variablen, bei denen Variablen nur 0 oder 1 annehmen können
- 1 Variable ergibt 2 mögliche Kombinationen
- 2 Variablen ergeben 4
- 3 Variablen ergeben 8
- Allgemein wächst die Laufzeit exponentiell mit der Zahl der Variablen, also mit der Dimension
- Können Variablen über 0 und 1 hinaus einen größeren Bereich ganzzahliger Werte annehmen, wird die Laufzeit noch deutlich länger
- Forschende untersuchen seit Langem, ob sich allgemeines ILP in der Geschwindigkeit stärker an diesen einfachen binären Fall annähern lässt
- Seit dem Rekord aus den 1980er-Jahren gab es nur schrittweise Verbesserungen
Lenstras geometrische Deutung
- 1983 bewies Hendrik Lenstra, dass allgemeine ILP-Probleme lösbar sind, und stellte den ersten Algorithmus dafür vor
- Lenstra behandelte ILP, indem er es in ein geometrisches Problem verwandelte
- Die Ungleichungen von ILP werden als konvexe Form, also als konvexer Körper (convex body), dargestellt
- Das Innere der Form entspricht allen möglichen Werten, die die Ungleichungen erfüllen können
- Ein Problem mit 2 Variablen wird zu einem ebenen Polygon, eines mit 3 Variablen zu einem dreidimensionalen Körper; so steigt die Dimension
- Alle ganzen Zahlen lassen sich mathematisch als Punkte eines Gitters (lattice) auffassen
- In 2D wirkt es wie ein Meer aus Punkten
- In 3D ähnelt es einer Struktur wie den Schnittpunkten eines Gebäudestahlskeletts
- ILP zu lösen heißt letztlich, den Schnitt von konvexem Körper und Gitter zu finden, also die Stellen, an denen mögliche Lösungen auf ganzzahlige Punkte treffen
- Lenstras Algorithmus konnte diesen Raum durchsuchen, musste das Problem aus Effizienzgründen aber teils in niedrigerdimensionale Stücke zerlegen; dieser Prozess erhöhte die Laufzeit
Der covering radius als 30-jähriger Engpass
- 1988 versuchten Ravi Kannan und László Lovász, den Schnitt von konvexen Körpern und Gittern effizienter zu behandeln, und nutzten dafür das aus der Forschung zu fehlerkorrigierenden Codes stammende Konzept des covering radius
- Der covering radius hängt mit der Größe zusammen, die garantiert, dass ein konvexer Körper mindestens einen ganzzahligen Punkt enthält, egal wo man ihn auf dem Gitter platziert
- Die Größe dieses Werts bestimmt, wie effizient sich ein ILP-Problem lösen lässt
- Die ideale Größe des covering radius herauszufinden, war selbst ein schwieriges Problem
- Kannan und Lovász grenzten mögliche Werte durch Ober- und Untergrenzen ein und zeigten, dass die Obergrenze linear mit der Dimension wächst
- Dieses Ergebnis allein reichte nicht aus, um die ILP-Laufzeit stark zu senken, und in den folgenden 30 Jahren blieben die Verbesserungen begrenzt
Der neue Algorithmus von Reis und Rothvoss
- Victor Reis und Thomas Rothvoss erzielten den Durchbruch, indem sie ein separates mathematisches Ergebnis nutzten, das sich auf Gitter konzentriert
- 2016 zeigten Oded Regev und Noah Stephens-Davidowitz, wie viele Gitterpunkte in bestimmten Formen enthalten sein können
- Reis und Rothvoss wandten dieses Ergebnis auf andere Formen an und schätzten damit die Zahl der Gitterpunkte im covering radius von ILP besser ab
- Durch diese Schätzung wurde die Obergrenze gesenkt, und die Laufzeit des gesamten ILP-Algorithmus ging deutlich zurück
- Die neue Laufzeit beträgt ((\log n)^{O(n)}), wobei (n) die Zahl der Variablen ist und (O(n)) linear proportional zu (n) ist
- Diese Darstellung gilt als Laufzeitniveau, das „fast“ dem von Problemen mit binären Variablen entspricht
Theoretischer Erfolg und Abstand zur praktischen Anwendung
- Noah Stephens-Davidowitz sieht den neuen Algorithmus als erste große Verbesserung für ILP-Solver seit fast 40 Jahren
- Daniel Dadush bewertet das Ergebnis als Leistung an der Schnittstelle von Mathematik, Informatik und Geometrie
- Der neue Algorithmus wird noch nicht zur Lösung realer Logistikprobleme eingesetzt
- Aktuelle Programme auf diesen Ansatz zu aktualisieren, würde viel Arbeit erfordern
- Rothvoss sieht den Fokus dieses Ergebnisses im theoretischen Verständnis eines Problems mit grundlegenden Anwendungen
- Es bleibt möglich, die Recheneffizienz von ILP weiter zu verbessern, doch Vempala geht davon aus, dass grundlegend neue Ideen nötig sind, um der idealen Laufzeit noch näherzukommen
1 Kommentare
Hacker-News-Kommentare
Es ist immer sehr interessant, wenn die algorithmische Obergrenze eines zentralen NP-vollständigen Problems gesenkt wird, aber das muss nicht bedeuten, dass das Problem in realen Implementierungen schneller gelöst wird.
Mixed-Integer-Programming(MIP)-Solver nutzen viele Algorithmen zusammen mit einer großen Menge an Heuristiken; der Aufbau von Bibliotheken aus Heuristiken und Strategien ist ein wesentlicher Grund dafür, dass Verbesserungen bei MIP-Solvern das Mooresche Gesetz übertroffen haben.
Laut https://www.math.uwaterloo.ca/~hwolkowi/henry/teaching/f16/6... sorgten Hardware-Verbesserungen von 1990 bis 2014 für einen Faktor 6500, Software-Verbesserungen dagegen für einen Leistungsgewinn um den Faktor 870000.
Auch dieses Paper könnte ein Puzzleteil sein, das die Leistungssteigerung von MIP-Solvern fortsetzt, garantiert ist das aber nicht.
Die Erklärung, der neue Algorithmus werde noch nicht zur Lösung von Logistikproblemen eingesetzt, weil es „zu viel Arbeit erfordert, heutige Programme zu aktualisieren“, leuchtet mir nicht ganz ein.
Die meisten domänenspezifischen Modelle rufen bei großen Problemen Gurobi, CPLEX oder FICO-Solver auf, bei kleinen Problemen Open-Source-Solver wie SCIP.
Über das standardisierte MPS-Format lassen sich Modelle zwischen diesen Solvern austauschen; die Problemformulierung ändert sich nicht, sondern nur die interne Lösungsweise des Solvers, oder?
Falls gemeint ist, dass eine neue Implementierung nötig ist, wäre der Nutzen für die Welt bei einer Implementierung wohl ebenfalls enorm.
Diese Tools sind extrem komplexe technische Artefakte, in denen sich jahrzehntelange schrittweise Verbesserungen angesammelt haben; allein herauszufinden, wie man eine neue Entdeckung in solche Engines integriert, dürfte erheblichen Forschungsaufwand erfordern.
Es stimmt, dass es mit Formaten wie MPS standardisierte Wege gibt, Problemformulierungen auszutauschen, und heutzutage werden wohl eher algebraische Modellierungssprachen wie AMPL verwendet; aber was solche Formate liefern, ist nur eine standardisierte mathematische Formulierung.
Die eigentliche Lösung ist stark auf den jeweiligen Solver zugeschnitten, mit jeweils eigenen Datenstrukturen, Algorithmen und heuristischen Verfahren.
Diese sind weder austauschbar noch absichtlich öffentlich offengelegt, und ohne Kenntnis des Solver-Codes und des gesamten Ablaufs kann man nicht einfach ein paar externe Zahlen mitten in den Prozess einschieben.
Ich wollte das Missverständnis ausräumen.
Wenn möglich, vermeide ich es, so etwas selbst zu implementieren.
Das ändert nichts daran, dass es ein hervorragendes Ergebnis ist.
Aus Sicht der theoretischen Rechenkomplexität basieren die besten Algorithmen für „ganzzahlige lineare Programmierung“ [2] auf Gittern und haben die beste Worst-Case-Big-O-Komplexität.
Heutige Implementierungen benötigen jedoch meist (1) Arithmetik mit rationalen Zahlen beliebiger Größe wie gmplib [3], was viel Speicher frisst und in der Praxis langsam ist, und (2) Schritte zur Gitterreduktion vom LLL-Typ [4], die die Dünnbesetztheit von Matrizen nicht ausnutzen können.
In der Folge passen solche Algorithmen normalerweise nicht in den Speicher, sodass Probleme mit Matrizen größer als 1000x1000 gar nicht erst starten; und selbst wenn sie hineinpassen, sind sie viel zu langsam.
Praktische Solver für ganzzahlige Programmierung basieren stattdessen auf Branch and Bound, einem Backtracking-Algorithmus ähnlich dem, was beim SAT-Solving verwendet wird, und lösen in jeder Iteration ein „lineares Programmierungsproblem“, bei dem alle Variablen des ursprünglichen Problems durch kontinuierliche Variablen ersetzt werden.
Jedes lineare Programmierungsproblem lässt sich zwar mit polynomialzeitlichen Algorithmen wie Innere-Punkte-Methoden lösen, in der Praxis verwendet man aber das Simplex-Verfahren, das im Worst Case exponentielle Zeit braucht.
Der Grund ist, dass die zu lösenden linearen Programmierungsprobleme einander sehr ähnlich sind und das Simplex-Verfahren diesen Umstand in der Praxis gut ausnutzt.
Außerdem nutzen die verwandten Algorithmen die Dünnbesetztheit von Vektoren und Matrizen stark aus.
Deshalb können manche Leute auch Probleme der ganzzahligen Programmierung mit Millionen von Variablen in wenigen Tagen, manchmal sogar in wenigen Stunden lösen.
Solver-Implementierer jagen nicht der absolut besten theoretischen Komplexität hinterher; man kann sagen, dass sich Theorie und Praxis der diskreten Optimierung bis zu einem gewissen Grad auseinanderentwickelt haben.
Trotzdem ist das Paper von Reis & Rothvoss [1] eine tiefgehende mathematische Arbeit und für alle, die sich für diskrete Mathematik interessieren, an sich sehr beeindruckend.
Es löst eine zehn Jahre alte Vermutung von Dadush und wurde im vergangenen November auf der FOCS vorgestellt, einer der beiden führenden Konferenzen für theoretische Informatik.
Unmittelbare praktische Nützlichkeit ist nicht der Kernpunkt, und die Autoren würden das inoffiziell wohl auch so einräumen.
In Förderanträgen würden sie natürlich etwas anderes sagen, aber das gehört zum Spiel.
Das heißt nicht, dass es nutzlos ist; allein der Fortschritt mathematischen Wissens ist von großem Wert, und vielleicht bauen Forschende in ein paar Generationen auf diesen Ideen praktische Algorithmen auf, die den Stand der Technik bei Solvern voranbringen.
Am Ende haben diese Algorithmen im Worst Case alle exponentielle Laufzeit.
In der Theorie versucht man vielleicht, das Polynom im Exponenten der Worst-Case-Komplexität ein wenig zu verkleinern, aber Praktiker wollen meist nicht eine Problemfamilie mit wachsendem n lösen, sondern ein einzelnes großes Optimierungsproblem.
Wichtiger als die Wachstumsrate der Laufzeit-Trendlinie ist, ob die eine große Instanz vor ihnen gelöst wird; und diese Instanz hat normalerweise eine Struktur, die verhindert, dass sie ein Worst Case derselben Größe ist.
Deshalb fallen auch die ingenieurmäßigen Entscheidungen anders aus.
[1] https://arxiv.org/abs/2303.14605
[2] min { c^T x : A x >= b, A in R^n, some components of x in Z }
[3] https://gmplib.org/
[4] https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1982f/art.p...
Das Abstract ist aussagekräftiger: https://arxiv.org/abs/2303.14605
Es geht darum, dass sie einen randomisierten Algorithmus mit Laufzeit (log(2n))^O(n) zum Lösen ganzzahliger Programmierung mit n Variablen erhalten haben.
Das heißt, diese Arbeit ist ein theoretisches Ergebnis: Auf Basis der Analyse der Struktur konvexer Körper in R^n und der Frage, wie man sie mit einem ganzzahligen Gitter überdeckt, stellt sie einen Exponentialzeit-Algorithmus vor, der besser ist als der bisher beste.
Die meisten praktischen ILP-Aufgaben verwenden Heuristiken und Branch-and-Bound und nutzen die besondere Struktur der jeweiligen Problemformulierung aus.
Ob diese Forschung bei einem von beidem hilft, ist nicht klar; allein aus dem Paper dürfte das schwer zu beurteilen sein, solange es nicht jemand von einem Anbieter wie Gurobi erklärt.
Eine kleine Anmerkung, aber im Titel sollte ausdrücklich ganzzahlige lineare Programmierung stehen.
Denn der Teil „ganzzahlig“ macht hier den deutlich größeren Unterschied.
Für lineare Programmierung sind seit Jahrzehnten Polynomialzeit-Algorithmen bekannt, während ganzzahlige lineare Programmierung NP-schwer ist.
Auch kontinuierliche lineare Programmierung ist schwierig.
Nicht im Sinne von NP-schwer, sondern in dem Sinne, dass für effiziente moderne LP-Solver viel Algorithmik und Engineering nötig ist.
Allein die numerische Berechnung ist schon komplex genug.
Und viele Solver für ganzzahlige lineare Programmierung basieren auf Solvern für kontinuierliche lineare Programmierung.
Wenn man als Software Engineer an Machine Learning oder Algorithmen interessiert ist, lohnt es sich, lineare Programmierung zu lernen.
Erstaunlich viele Probleme lassen sich als lineare Optimierung formulieren.
Zum Beispiel habe ich mich im Studium einmal mit einem Freund aus dem Wirtschaftsingenieurwesen darüber unterhalten, wie viele Vertauschungen im Mittel mindestens nötig sind, um Billardkugeln in zulässige Startpositionen innerhalb des Rack-Dreiecks zu bringen.
Wir haben beide Programme geschrieben, die das per Monte-Carlo-Sampling lösen sollten; meine Lösung machte BFS im Graph-Zustandsraum, die meines Freundes nutzte lineare Programmierung.
Wahrscheinlich war die Variante meines Freundes effizienter.
Beispiele sind minimale Spannbäume, Matching in bipartiten oder allgemeinen Graphen, Netzwerkflüsse, Matroid-Schnittmengen, submodulare Flüsse und so weiter.
Eckpunktlösungen bestimmter LPs haben außerdem interessante Eigenschaften, die man beim Entwurf von Approximationsalgorithmen für NP-vollständige Probleme nutzen kann.
Beim Steiner-Forest-Problem lässt sich zum Beispiel beweisen, dass eine Eckpunktlösung immer eine Variable mit Wert mindestens 1/2 enthält; rundet man Variablen iterativ und löst das LP erneut, erhält man einen 2-Approximationsalgorithmus.
In meiner Graduate-School-Zeit war das der einzige 2-Approximationsalgorithmus für dieses Problem.
Ebenfalls interessant ist, dass man ein LP selbst mit exponentiell vielen Nebenbedingungen lösen kann, solange man nur ein Polynomialzeit-Separationsorakel hat.
Das war wirklich spannend und ist empfehlenswert.
Schon heute gibt es in der Operations Research erstaunlich viele Überschneidungen, aber es ist schockierend, wie viele Absolventen des Wirtschaftsingenieurwesens nicht ordentlich programmieren können.
Wirklich schade.
Soweit ich mich erinnere, war der Ganzzahligkeitsaspekt ziemlich wichtig, weil man normalerweise nur mit ganzzahligen Cent-Beträgen handeln kann.
Kurz, aber ein guter Artikel.
Ich habe mir die Mathematik noch nicht im Detail angesehen, aber der Preprint scheint dieser hier zu sein: https://arxiv.org/pdf/2303.14605.pdf
Es sieht nicht so aus, als würden sie direkt Raumgruppen betrachten, um den Problem-„Raum“ zu verallgemeinern und zu vereinfachen, indem Symmetrien oder Wiederholungen reduziert werden; es wäre aber interessant zu sehen, ob sich solche Strukturen anwenden lassen.
Als jemand, der Software verwendet, die Raumgruppen anwendet und Voronoi-Zellen um darin verteilte Punkte oder Punktmengen beschreibt, bin ich mit der „unheimlichen“ Art vertraut, wie sich Effekte fortpflanzen [1].
Ich bin kein Mathematiker, nur Architekt, daher liegt dieses Gebiet außerhalb meiner Kompetenz; aber als jemand, der Pfade durch erzeugte Wabenstrukturen betrachtet, halte ich dieses Ergebnis für weitere Untersuchung wert.
[0] https://arxiv.org/pdf/2303.14605.pdf
[1] Wenn jemand Mathematiker kennt, mit denen man an solchen Arbeiten zusammenarbeiten könnte, würde ich mich über eine Kontaktaufnahme freuen.
Es ist laufende Arbeit, und wie gesagt liegt sie mathematisch außerhalb meiner Kompetenz, aber ich bin auf interessante Eigenschaften gestoßen, die sich echte Experten genauer ansehen sollten.
Im Zusammenhang mit dem Problem des Handlungsreisenden ist ein Zitat aus Sapolskys neuestem Buch Determined: A Science of Life without Free Will interessant
Ich weiß nicht, wie relevant das für Softwareentwickler ist, aber es ist faszinierend
Wenn eine Ameise auf der Suche nach Nahrung acht Orte überprüft, sollte sie idealerweise jeden Ort nur einmal besuchen und unter den 5.040 möglichen Routen, also 7!, die kürzeste wählen
Das ist eine Form des berühmten Problems des Handlungsreisenden, an dem Mathematiker seit Jahrhunderten arbeiten, ohne eine allgemeine Lösung gefunden zu haben
Eine Strategie ist Brute Force: alle möglichen Routen durchsehen, vergleichen und die beste auswählen. Doch schon bei 10 Besuchsorten gibt es mehr als 360.000 Möglichkeiten, bei 15 mehr als 80 Milliarden
Lässt man jedoch die etwa 10.000 Ameisen einer typischen Kolonie auf ein Problem mit acht Futterstellen los, finden sie in deutlich kürzerer Zeit als per Brute Force eine von 5.040 Lösungen, die nahezu optimal ist, obwohl keine Ameise mehr kennt als ihre eigene Route und zwei Regeln
Dieser Ansatz funktioniert so gut, dass auch Informatiker solche Probleme mit „virtuellen Ameisen“ lösen; das ist heute als Schwarmintelligenz bekannt
Und die Standardreaktion darauf ist: „Das schaffen auch sehr einfache Computeralgorithmen“
Für das Problem des Handlungsreisenden mit euklidischen Distanzen, also wenn jeder Knoten feste Koordinaten hat und die Kosten einer Route der euklidischen Distanz zwischen zwei Punkten entsprechen, kann man sogar einen Polynomialzeit-Algorithmus angeben, der eine Route innerhalb eines Faktors ε des Optimums findet
Allerdings ist er exponentiell in ε
Im Vorwort steht auch ein hervorragender Disclaimer
„Wir persönlich glauben, dass die Literatur dieses Felds weniger Beuteltiere und mehr Mathematik enthalten sollte und dass wir uns als Community aus dieser metaphernreichen Phase herausbewegen sollten, ähnlich wie die Chemie die Alchemie hinter sich gelassen hat. Diese Liste erhebt jedoch keinerlei Anspruch auf die wissenschaftliche Qualität der aufgeführten Arbeiten.“
[1]: https://fcampelo.github.io/EC-Bestiary/
Das ist ein Algorithmus, der das Verhalten solcher Ameisenkolonien modelliert
Wie andere schon gesagt haben, eignet er sich gut zum Finden lokaler Optima, ähnlich wie Tabu Search, Simulated Annealing oder genetische Algorithmen
Für die meisten Geschäftsziele, etwa das im Artikel genannte Beispiel der „Sofaproduktion“, reicht das aus
Es ist aber nicht dasselbe wie das Finden einer „allgemeinen Lösung“
Dass Sapolsky unsere Schwierigkeit, eine „allgemeine Lösung“ zu finden, mit der Fähigkeit von Ameisen vergleicht, lokale Optima zu finden, wirkt etwas irreführend
Es bedeutet nicht, dass die allgemeine Form des Problems nicht NP-schwer ist, sondern dass man mit zusätzlichen Informationen hinreichend gute Lösungen approximieren oder die optimale Suche handhabbar machen kann
Diese Sichtweise war besonders während der ersten KI-„Revolution“ ausgeprägt, als es populär war, KI als Suchproblem zu betrachten, das durch menschliches Wissen ergänzt wird
Ist das die „Schwarmintelligenz“, die das Buch meint?
Viele Probleme der diskreten Optimierung lassen sich in lineare Programmierung übersetzen
Wie SAT-Solver ist das ein wirklich mächtiges Werkzeug, das man kennen sollte
Als Entwickler war das einer dieser Momente, in denen man denkt: „Wie konnte mir das bisher entgehen?“
Ein großartiges Ergebnis, aber vermutlich nicht praxisrelevant
Das ist ähnlich wie bei der linearen Programmierung: Innere-Punkte-Verfahren haben zwar eine bessere theoretische Komplexität als die Simplex-Methode, aber in der Praxis gewinnt eine gut getunte Simplex-Methode fast immer
Gibt es einen allgemein akzeptierten „Grund“, warum Innere-Punkte-Verfahren in der Praxis normalerweise langsamer sind?
Wenn man durch das Innere geht, statt an die Grenze gebunden zu sein, würde ich erwarten, dass man schneller zu einer guten Lösung kommt; vielleicht ist dieser Unterschied in hohen Dimensionen aber weniger wichtig
Die Formulierung hier ist etwas verwirrend
Es gibt den Satz: „Die beste Version, die sie sich ausgedacht haben, eine Art Geschwindigkeitsbegrenzung, stammt aus dem trivialen Fall, in dem die Variablen des Problems nur binäre Werte annehmen können, also 0 oder 1, etwa ob ein Handlungsreisender eine Stadt besucht oder nicht.“ Wird hier ein NP-vollständiges Problem als trivialer Fall bezeichnet?
Soweit ich weiß, kann jedes ILP auf 01-ILP reduziert werden und umgekehrt
Außerdem heißt es: „Leider steigt die Laufzeit des Algorithmus stark an, wenn Variablen Werte jenseits von 0 und 1 annehmen. Forscher fragen sich schon lange, ob man diesem trivialen Ideal näherkommen kann.“ Daher frage ich mich, ob diese Arbeit ein Solver ist, der die untere Schranke für 01-ILP verbessert, oder ein Algorithmus, der die Grenze zwischen 01-ILP und allgemeinem ILP enger zusammenbringt