Wie lese ich Open-Source-Code eines Lösers (Or-Tools, OptaPlanner, Minotaurus usw.)?

Sep 12 2020

Ich möchte mehr über Löser erfahren, indem ich den Code einiger Open-Source-Projekte wie MINOTAUR , Optaplanner und OR-Tools lese .

Ich kämpfe jedoch. Ich weiß nicht, wo ich anfangen soll. Es gibt viele Repositorys und Dateien ohne allgemeine Übersicht. Ich weiß nicht, ob ich mit kleineren Lösern beginnen muss (in diesem Fall können Sie einen oder mehrere vorschlagen) oder ich muss lernen, wie man Open-Source-Projekte im Allgemeinen angeht (irgendwelche Referenzen dafür?).

Ich wäre dankbar, wenn jemand eine Anleitung geben könnte.

Antworten

14 mtanneau Sep 12 2020 at 09:31

Ich habe den Code mehrerer Löser gelesen, bevor ich Tulip.jl entwickelt habe . Um ehrlich zu sein, es ist wahrscheinlich besser, Ihre Zeit zu nutzen, als den Quellcode des Lösers zu lesen, es sei denn, Sie entwickeln selbst einen Solver / eine Schnittstelle oder müssen die Implementierung eines Autors reproduzieren. Das Lesen des Benutzerhandbuchs oder gegebenenfalls der Dokumente, in denen die algorithmischen Komponenten der Software beschrieben werden, sollte auf jeden Fall Ihr Ausgangspunkt sein. Wie Kuifje in seinem Kommentar erwähnt, erleichtert die Kenntnis der Benutzeroberfläche eines Lösers das Verständnis seiner inneren Funktionsweise.

Davon abgesehen habe ich festgestellt, dass zumindest für die lineare Programmierung die meisten algorithmischen Komponenten insgesamt ziemlich ähnlich sind. Unterschiede ergeben sich aus bestimmten Auswahlmöglichkeiten der Datenstrukturen und der Modularität des Codes.

Für mich ist das Wichtigste zu wissen, wonach Sie im Code suchen. Ist es, die Implementierung eines Algorithmus zu verstehen? Spezifische Datenstrukturen? Wie werden Löserparameter behandelt? Dies hilft Ihnen, sich auf Ihre Arbeit zu konzentrieren und nicht verloren zu gehen.

Hier sind einige weitere Faktoren, die ich bei der Auswahl der zu betrachtenden Löser berücksichtigen würde (ich denke, einige sind nicht spezifisch für Optimierungssoftware):

Dokumentation. Erwarten Sie nur nicht viel von nicht dokumentiertem Quellcode.
Wird der Solver gewartet? Wenn ein Solver von mehreren Personen verwaltet wird, haben sich diese Personen den Code angesehen. Dies ist ein guter Hinweis darauf, dass die Quelle lesbar ist, zumindest so weit, dass andere sie ändern konnten.
Programmiersprache. Es mag offensichtlich klingen, aber das Lesen einer Sprache, mit der Sie vertraut sind, erleichtert die Aufgabe erheblich. Die meisten Löser sind in C oder C ++ geschrieben, einige alte in Fortran und ich kenne einige in Julia. Ähnliche Paradigmen können zu völlig unterschiedlichen Implementierungen in verschiedenen Sprachen führen, obwohl die Grundideen höchstwahrscheinlich gleich bleiben werden.
Welche Probleme werden unterstützt? Datenstrukturen (und Algorithmen) variieren stark zwischen einem linearen Programmierlöser und einem nichtlinearen Programmierlöser. Ersteres benötigt nur Matrizen und Vektoren, letzteres wird wahrscheinlich automatische Differenzierungswerkzeuge, geeignete Datenstrukturen für Gradienten- und Hessische Berechnungen enthalten. Mixed-Integer-Solver erhöhen die Komplexität von Verzweigungsbäumen usw. Die Constraint-Programmierung ist eine weitere Kategorie. So wissen Sie, wonach Sie suchen.

Was die Frage betrifft, ob einige Löser "lesbarer" sind als andere, beschränkt sich meine Erfahrung hier auf (gemischte ganzzahlige) lineare Programmierung und ein wenig konische Optimierung. Ich habe festgestellt, dass GLPK gut geschrieben und leicht zu befolgen ist. SCIP und Ipopt haben gute und umfangreiche Dokumentationen, was für mich eine Voraussetzung ist. Ich würde nicht in die Nähe der Codebasis von Clp oder Cbc gehen, wenn Sie nicht wissen, was Sie tun. Für die konische Optimierung ist ECOS ein leichter Innenpunktlöser in C. HiGHS ist ein moderner Simplex-Löser für die lineare Programmierung in aktiver Entwicklung. Löser, die in höheren Sprachen wie Julia oder Matlab geschrieben sind, sind möglicherweise einfacher zu befolgen: Die gesamte Codebasis von Tulip besteht nur aus ~ 4000 Codezeilen (Clp ist ~ 180k, Ipopt ~ 75k, HiGHS ~ 50k).

Im Quellcode der meisten Löser finden Sie ein src/Verzeichnis: Hier befindet sich der Quellcode. Ich gehe im Allgemeinen wie folgt vor:

Identifizieren Sie, welche spezifische Komponente ich verstehen möchte, z. B. wie Parameter intern behandelt werden
Führen Sie eine schnelle Suche in den Dokumenten durch. Oft ist das genug
Wenn nicht, werfen Sie einen Blick auf den Code, auf den in der Dokumentation verwiesen wird. Ich beginne im Allgemeinen mit dem Betrachten von Header-Dateien und schaue mir Quelldateien selten direkt an.
Wenn ich etwas nicht verstehe, z. B. eine Klasse, die ich nicht kenne oder deren Funktion unklar ist, suchen Sie dort, wo sie definiert ist.
Wiederholen.

5 prubin Sep 13 2020 at 03:47

Es gibt Softwaretools (normalerweise sprachspezifisch, glaube ich), die ein Softwareprojekt aufnehmen und eine Karte der Abhängigkeiten ausscheiden (im Grunde genommen, welche Methoden / Klassen / Dateien etwas von welchen anderen Methoden / Klassen / Dateien aufrufen). Wenn Sie ein Open-Source-Projekt auswählen und es über ein solches Tool ausführen, sollten Sie in der Lage sein, alle Dateien usw. in einer Hierarchie zu sortieren. Dann können Sie mit dem Teil der obersten Ebene beginnen, den Code dort lesen und einfach notieren, was Aufrufe an andere Teile allgemein tun ("löst das Modell", "exportiert eine MPS-Datei", "prüft Daten auf Konsistenz" "...) ohne zu sehr ins Detail zu gehen. Arbeiten Sie sich dann so weit wie möglich durch die Hierarchie nach unten.

5 NikosKazazakis Sep 12 2020 at 17:00

Komisch, dass Sie MINOTAUR erwähnen sollten. Ich habe C ++ tatsächlich gelernt, indem ich den Quellcode von MINOTAUR für meine Promotion geändert habe.

Meiner Meinung nach verfügt praktisch kein Löser über eine Dokumentation, die hilft zu verstehen, wie der Code selbst funktioniert und warum er so zusammengesetzt ist, wie er ist.

Der Grund dafür ist, dass die allgemeinen Algorithmen unkompliziert sind. Sie können diese in ein paar Tagen erlernen. Solver-Magie liegt in den Datenstrukturen und in der Art und Weise, wie Informationen formatiert und für iterative Berechnungen effizient übergeben werden.

Der beste Weg, um den Code zu verstehen, besteht darin, ihn zu ändern, um etwas anderes zu tun. Seien Sie jedoch gewarnt, dass dies viele Monate dauern kann.

Hier sind einige Tipps, die ich Ihnen geben kann:

Holen Sie sich eine gute IDE wie CLion. Auf diese Weise können Sie einfach im Code navigieren, Methodenverwendungen nachschlagen usw.
Verwenden Sie Eclipse nicht, Sie werden es bereuen. Wenn Sie eine gute kostenlose Option wünschen, verwenden Sie VSCode.
Gehen Sie nicht davon aus, dass der gesamte Code gut geschrieben ist. Ich habe gelernt, wie CGraphs und AD funktionieren, indem ich den Code von MINOTAUR geändert habe. Als wir das für Octeract Engine von Grund auf neu implementiert haben, war unser Code für den CGraph ~ 50-mal kleiner und schneller.
Viele Designentscheidungen sind bewusst, auch wenn Sie für Ihr Leben die Motivation nicht ergründen können. Das Warum wird Jahre später klar, wenn Sie auf dieselben Engpässe stoßen, die die ursprünglichen Entwickler hatten. Solver verwenden viele Tricks wie Caching, Vektorisierung von Berechnungen und leider globale Variablen, da es nicht offensichtlich ist, wie Hochleistungscode zusammengestellt und gleichzeitig wartbar gehalten werden kann.
Wenn der Solver nicht mit objektorientierter Programmierung entwickelt wurde, verschwenden Sie keine Zeit mit dem Lesen des Codes. Es wird ewig dauern und Sie werden sehr wenig lernen, weil Sie heutzutage keinen Solver so codieren sollten.
Versuchen Sie für C ++, Zeigerargumente zu ersetzen, die stattdessen als Wert übergeben werden sollen. Dies zwingt Sie dazu, Konstruktoren zum Kopieren und Verschieben zu implementieren, was Ihnen wiederum hilft, die grundlegenden Datenstrukturen zu verstehen.
Denken Sie daran, dass Löser der alten Schule ohne moderne Compiler geschrieben wurden. Früher hat eine massive Funktion anstelle von 100 kleinen die Leistung tatsächlich gesteigert. Das stimmt nicht mehr.
Versuchen Sie, große Funktionen in kleinere zu unterteilen.
Schreiben Sie Tests für den Solver, damit Sie wissen, dass Ihre Änderungen zu denselben Ergebnissen geführt haben. Verwenden Sie im Idealfall eine CI-Plattform wie Jenkins.
Benutze Git und benutze es oft.

4 mattmilten Sep 14 2020 at 22:38

Für die letzten Versionen der SCIP Optimization Suite wurden technische Dokumente zu den neuen Funktionen und Verbesserungen veröffentlicht - im Grunde genommen ein sehr detaillierter CHANGELOG.

Dies könnte ein möglicher Ausgangspunkt sein, da der Quellcode ziemlich komplex ist - was für nahezu jeden Löser gilt.

4 PhilippChristophel Sep 15 2020 at 14:53

Die wichtigsten Dinge wurden bereits gesagt, aber ich möchte hinzufügen, dass meiner Meinung nach der beste Weg zum Lesen von Code darin besteht, ihn zu lesen, während Sie einen relativ einfachen Testfall im Debugger durchlaufen. Wenn ich mir einen LP- oder MILP-Solver anschaue, gehe ich zunächst eine winzige Instanz durch, um eine Vorstellung vom Programmablauf zu erhalten, mache dies mehrmals und gehe nach Bedarf in wichtige Funktionen und überprüfe die Datenstrukturen. Dann würde ich größere oder andere Arten von Problemen versuchen, um mehr vom Code zu sehen oder seine Feinheiten besser zu verstehen. Übrigens, meiner Erfahrung nach ist der beste Weg, einen Code wirklich gut zu lernen, zu versuchen, Fehler darin zu beheben ...

4 GeoffreyDeSmet Sep 14 2020 at 13:45

Beginnen Sie für OptaPlanner mit dem Verständnis des CloudBalancing-Beispiels, wie in den Dokumenten in Kapitel 2 erläutert . Aktivieren DEBUGund TRACEprotokollieren Sie, um zu sehen, was während eines Laufs passiert. Führen Sie dann einen Java-Debugger aus und fügen Sie Haltepunkte hinzu, um herauszufinden, was los ist.