Wie implementiere ich Filiale und Preis?
Ich habe einmal gehört, dass der Branch & Price (B & P) -Algorithmus zu den schwierigsten im OP gehört, aber wenn er gut implementiert ist, könnte er sehr effizient sein. Gibt es andere Algorithmen, die auch so knifflig sind?
Ich möchte B & P bei einem Problem implementieren. Wie wähle ich ein Problem aus, das nicht zu komplex ist? Sie können gerne mehr als ein Problem vorschlagen, wenn Sie der Meinung sind, dass es Auswirkungen auf die Art und Weise hat, wie der Algorithmus implementiert wird, dh wenn ich aus verschiedenen Problemen unterschiedliche Prinzipien lernen werde.
Ich brauche auch eine Anleitung. Wie man anfängt? Was sind die zu vermeidenden Fallstricke? Jede Ressource mit einem gut dokumentierten Open-Source-Code wäre ebenfalls willkommen. Ich möchte Python oder C ++ wählen.
Antworten
Bevor ich mit der Implementierung beginne, würde ich sicherstellen, dass ich mit allen theoretischen Aspekten vertraut bin, die ebenfalls etwas schwierig sind. Dies ist ein ziemlich fortgeschrittenes Thema im OP und erfordert einige Erfahrung. Sind Sie mit Branch-and-Bound, dem Simplex-Algorithmus, der Dantzig-Wolfe-Zerlegung, der Spaltengenerierung usw. vertraut?
Sie zögern zwischen Python und C ++. Gibt es einen Grund dafür? Python ist viel einfacher, aber C ++ wird schneller sein. Ist das also für die Wissenschaft oder für die Industrie?
Sie können auch Kasse Dippy , die eine Erweiterung der ist Pulp (so seine Python) , die Benutzer Zersetzungen angeben können , und die Verzweigung, schneiden Generation anpassen und Spalte Erzeugung von DIP , aus einem Pulp - Modell. Alles ist Open Source.
Die Verwendung eines Frameworks wie SCIP kann eine gute Idee für den Start sein. Auf diese Weise können Sie Ihre Formulierung schnell implementieren. Es hat Schnittstellen unter C ++ und Python. Die Dokumentation enthält Beispiele für Filiale und Preis. Ich empfehle Ihnen, sie sich anzusehen. Für jedes Problem können Sie die Dantzig-Wolfe-Zerlegungsmethode verwenden, um ein Verzweigungs- und Preisschema zu generieren.
Nein, nein. Das Erstellen einer ASL-Schnittstelle ist schwierig , BnP ist in Ordnung. Angenommen, Sie kennen die Bausteine (wie bei jedem anderen Algorithmus), liegt die Herausforderung in den Implementierungsdetails.
Für BnB im Allgemeinen und für BnP im Besonderen sind einige Dinge zu beachten:
BnB
- Beschleunigungsheuristiken: BnB-Algorithmen funktionieren nur dann gut, wenn sie mit bestimmten Beschleunigungsheuristiken wie Domänenreduktion (z. B. Einschränkungsausbreitung) oder guten Verzweigungsstrategien (z. B. Pseudokosten) kombiniert werden.
- Bei großen Problemen benötigen Sie gute und skalierbare Datenstrukturen, um zu vermeiden, dass der Algorithmus langsamer wird, insbesondere wenn Ihre Probleme groß genug sind, um eine Spaltengenerierung zu erfordern.
- Pure Python ist bei Problemen mit anständiger Größe 1.000 bis 10.000 Mal langsamer als C ++. Der richtige Weg, dies zu tun, besteht darin, C ++ - Bibliotheken für die Hochleistungsberechnungen zu codieren und sie als Python-Objekte zu importieren, indem Python-> C ++ - APIs wie Boost Python verwendet werden. Dies kann dazu führen, dass Sie 100x langsamer als C ++ sind.
- Aus den beiden oben genannten Gründen hat Python aufgrund der begrenzten Bandbreite beim Übertragen von Daten zwischen verschiedenen Teilen Ihres Codes seine Grenzen. Insbesondere lösen viele Python-> C ++ - APIs unvermeidlich C ++ - Kopierkonstruktoren aus, was ein großes Problem sein kann, wenn Ihre Datenstrukturen groß sind. Speicher kann auch ein Problem werden.
- Selbst wenn Sie wirklich wissen, was Sie in C ++ tun, ist das Beste, was Sie mit Hybridcode tun können, 100x langsamer als in C ++. Wenn Sie jedoch genau wissen, was Sie tun, können Sie das Ganze auch in C ++ ausführen.
- MINOTAUR ist der am besten geschriebene C ++ - Open-Source-BnB-Code, den ich bisher gesehen habe (obwohl er vor einigen Jahren nicht sehr gut dokumentiert war).
- Eine Sache, die die meisten Leute am Anfang vernachlässigen, ist, dass Sie einen Weg brauchen, um die Mathematik in Ihren Code zu bekommen. Überlegen Sie sich frühzeitig, wie Sie dies tun werden, da dies viele Ihrer Architekturentscheidungen beeinflusst.
BnP
- Eine wichtige Überlegung bei der Implementierung ist, dass Sie im Verlauf des Lösungsverfahrens Spalten zur Entspannung hinzufügen müssen. Dies kann eine sehr kostspielige Operation sein, insbesondere bei großen Matrizen. Daher müssen Sie nach dem schnellsten Weg suchen, den Ihr linearer Löser unterstützt, um neue Spalten hinzuzufügen. Das Neuerstellen der Matrix ist natürlich der einfachste Weg und für viele Algorithmen in Ordnung, für die Spaltengenerierung jedoch ein Nein-Nein.
Aus Ihrer Beschreibung geht hervor, dass es Ihr Ziel ist, neue Dinge zu lernen. Daher sind entweder Python oder C ++ für diesen Zweck in Ordnung. Wenn Sie Ihren Code für etwas "Reales" verwenden möchten, ist die Verwendung von C ++ bis zu einem gewissen Grad unvermeidlich. Es liegt also an Ihnen, zu entscheiden, was Sie programmieren lernen möchten. Beachten Sie jedoch, dass die Migration von Hybridcode nach C ++ sehr schmerzhaft sein kann. Wenn Sie also feststellen, dass Sie sich besser für C ++ entscheiden müssen, um dies früh in der Entwicklung zu tun.
Bereiten Sie sich mental auf eine große Investition vor und haben Sie Spaß!
Wenn Sie sich den C ++ - Quellcode ansehen möchten, gibt es einige COIN-OR-Projekte, die Frameworks für "Branch Price and Cut" oder "Branch Cut and Price" bereitstellen, wie es manchmal genannt wird. Zwei, die mir in den Sinn kommen, sind BCP und Symphony .
Eine der Hauptideen hinter unserem Zerlegungslöser GCG (gcg.or.rwth-aachen.de/dev) ist es, Ihnen die Zeit zu sparen, mit Ihrem eigenen B & P-Code zu experimentieren, nur um herauszufinden, dass B & P nicht der richtige Ansatz für Ihr Problem ist. Eine weitere Hauptidee unseres Lösers ist, dass Sie, sobald Sie herausgefunden haben, dass B & P ein guter Ansatz ist, GCG verwenden können, um die Arbeit für Sie zu erledigen. Probieren Sie es aus, es spart Ihnen hoffentlich einige Stunden. Download mit SCIP unter scipopt.org.