Lesen des CBC-Löserprotokolls (Pulp, Python-Mip)

Ich habe versucht zusammenzufassen, wie man das Protokoll des CBC-Lösers (COIN-OR Brand-and-Cut) liest, der frei von Pulp [^ 1] und Python-mip [^ 2] betrieben werden kann. (Ich habe es als persönliches Memo zusammengestellt. Bitte weisen Sie auf Fehler hin.)

Der Inhalt ist fast eine Übersetzung des folgenden PDFs.

• CBC : COIN-OR Branch-and-Cut (A Short Guide to the CBC Command Line Interface)
  http://www.decom.ufop.br/haroldo/files/cbcCommandLine.pdf

Einführung

Im obigen PDF wird Nachricht 7 anhand des Protokolls bei der Berechnung des Benchmarks für das Set-Partitionierungsproblem "air03" erläutert. Nachricht 7 und höher wird mit "air04" erklärt.

http://miplib2017.zib.de/instance_details_air03.html http://miplib2017.zib.de/instance_details_air04.html

Sie können die mps-Datei über den obigen Link erhalten. Sie können "read" in Python-Mip verwenden, um das Problem zu lesen und zu berechnen. (Pulp hat keine Lesefunktion ... obwohl es eine Schreibfunktion hat.)

So lesen Sie das Protokoll

Meldungen 1-3

Nachricht 1

Continuous objective value is 338864 - 0.05 seconds

Der Wert (Kosten) und die Berechnungszeit des Zielterms beim Lösen der linearen Relaxationslösung des Modells werden angezeigt. In diesem Beispiel wird eine lineare Relaxationslösung mit Kosten von "338864" in "0,05" Sekunden erhalten. Dieser Wert ist die Ober- und Untergrenze des ursprünglichen Problems. (Im Fall der Minimierung ist es die Untergrenze und im Fall der Maximierung die Obergrenze. Von nun an werden wir das Minimierungsproblem betrachten.) Da keine spezielle Operation durchgeführt wird, ist dies die niedrigste geschätzte untere Welt.

Nachricht 2

Cgl0004I processed model has 120 rows, 8456 columns (8456 integer) and 71651 elements

Die mit "Cgl" gekennzeichnete Zeile ist ** vorverarbeitet **. Cgl scheint eine Abkürzung für Cut Generation Library zu sein [^ 3].

Die Einschränkungen ("Zeilen"), Variablen ("Spalten") und die Anzahl der Nicht-Null-Elemente ("Elemente") nach Reduzierung der Vorverarbeitung werden in der letzten Zeile angezeigt. Die Vorverarbeitung reduziert die Größe des Problems wie unten gezeigt.

Es scheint, dass es für den MIP-Solver umso einfacher ist, das Problem zu lösen, je kleiner das Problem bei der Vorverarbeitung ist.

Nachricht 3

Cbc0038I Pass 1: suminf. 8.33333 (22) obj.  341524 iterations 106
Cbc0038I Pass 2: suminf. 8.33333 (22) obj.  341524 iterations 3
Cbc0038I Pass 3: suminf. 8.33333 (22) obj.  341524 iterations 70
Cbc0038I Pass 4: suminf. 7.20000 (20) obj.  342390 iterations 75
Cbc0038I Pass 5: suminf. 1.50000 (3)  obj.  343697 iterations 45
Cbc0038I Pass 6: suminf. 1.50000 (3)  obj.  343697 iterations 55
       ...
Cbc0038I Pass 12: suminf. 0.00000 (0) obj.  362176 iterations 144
Cbc0038I Solution found of 362176

Dies bedeutet, dass Cbc0038I gestartet wurde. In "Cbc0038I" wird die anfängliche Lösung (vorläufige Lösung), die zu einer realisierbaren Lösung wird, unter Verwendung einer Methode namens ** Machbarkeitspumpe (M. Fischetti, Glover & Lodi, 2005) [^ 4], [^ 5] ** gesucht. Scheint zu tun. (Ist "Ich" eine Abkürzung für "Initial"?) Nach Abschluss der 12 Durchgänge wird die Meldung "Cbc0038I Lösung gefunden von 362176" angezeigt, die angibt, dass eine vorläufige Lösung mit Kosten von "362176" erhalten wurde. Da die in Nachricht 1 angezeigte Untergrenze "338864" war, können wir sehen, dass es eine optimale Lösung (exakte Lösung) in mindestens dem Bereich von "[338864, 362176]" gibt. Je kleiner die Differenz (Lücke) zwischen den Kosten der vorläufigen Lösung und der Untergrenze ist, desto besser ist die Leistung von CBC.

Meldungen 4 ~ 6

Nachricht 4

Cbc0012I Integer solution of 340160 found by DiveCoefficient after 14 iterations and 0 n odes (0.97 seconds)

Das Ergebnis der Vorverarbeitung mit dem Namen ** DiveCoefficient [^ 5], [^ 6] ** wird angezeigt. (Ich kenne die Details nicht.) Infolgedessen wurde die vorläufige Lösung weiter aktualisiert, um die Lücke zu einem Abschnitt von "[338864, 340160]" zu machen.

Nachricht 5

Cbc0013I At root node, 5 cuts changed objective from 338864.25 to 340160 in 2 passes

Es scheint, dass der Schnittalgorithmus ausgeführt wird. Insbesondere um die Ober- und Untergrenze des ** Doppelproblems ** zu verbessern, scheint er einige Schnitte zu versuchen, die die Dezimalwerte der erhaltenen Minderungslösung entfernen. In diesem Beispiel wurden anscheinend 5 Arten von Schnitten ausgeführt. Details werden am unteren Rand des Protokolls angezeigt.

Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 160 column cuts (160 active) in 0.840 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 4 row cuts average 1257.2 elements, 0 column cuts (3 active) in 0.020 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.020 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 10 row cuts average 3.7 elements, 0 column cuts (0 active) in 0.000 seconds - new frequency is 1
Cbc0014I Cut generator 6 (TwoMirCuts) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.030 seconds - new frequency is -100

Der 0., 1. und 3. Schnitt scheinen für dieses Problem ausreichend zu sein. (Sie können sehen, dass Gomory Cut [^ 7] und Clique Cut besonders effektiv sind.) Es wurde festgestellt, dass die Obergrenze des Doppelproblems "340160" ist. Die Kosten für die vorläufige Lösung betragen ebenfalls "340160", sodass Sie sehen können, dass es sich um die optimale Lösung handelt.

Nachricht 6

Result - Finished objective 340160 after 0 nodes and 11 iterations - took 4.75 seconds (total time 5.06)
Total time 5.14

Der endgültige Kostenwert und die Berechnungszeit werden angezeigt. Für dieses Problem hat der Wurzelknoten eine ausreichend gute realisierbare Lösung und die Obergrenze des Doppelproblems, so dass kein weiteres Beschneiden des Verzweigungsschneidverfahrens durchgeführt wird.

Nachrichten 7, 8

Diese Meldungen sind die Protokolle, die Sie sehen, wenn Sie das schwierigere Problem berechnen (air04). In air04 scheint diese Suche vor der Verzweigungsbegrenzungsmethode durchgeführt zu werden. Die Anzahl der Knoten, die mit der Baumstruktursuche nach der molekularen Begrenzungsmethode durchsucht wurden, und die Anzahl der Knoten, die noch nicht durchsucht wurden, werden angezeigt. Jedes Mal, wenn eine neue Ganzzahl abgerufen wird, werden Informationen zu deren Kosten und der verwendeten Methode angezeigt. (Nachricht 8)

Das Obige ist, wie man das Protokoll liest. Als Referenz wird das Protokoll bei der Berechnung von "air03" und "air04" mit Python-Mip unten hochgeladen. https://github.com/Noriaki416/Qiita/tree/master/CBC_log

air0 # _cbc_log.txt wird das Protokoll sein.

Tuning

Durch Lesen des Protokolls können Sie erkennen, welcher Prozess der Engpass bei der Lösung des Problems ist. Sie sollten in der Lage sein, die Lösungsleistung zu verbessern, indem Sie die Ursache identifizieren und die Optimierung vornehmen. Detaillierte Abstimmungsparameter werden zu Beginn nach p6 des PDF beschrieben.

Wenn Sie mit Pulp abstimmen, können Sie es anscheinend mit options angeben. Es wird im folgenden Blog ausführlich erklärt.

https://inarizuuuushi.hatenablog.com/entry/2019/03/07/090000

Mit> options können Sie andere CBC-Optionen festlegen.

Um beispielsweise die Option maxsol zu verwenden, setzen Sie options = ['maxsol 1']. Mit der Option maxsol können Sie angeben, wie viele vorläufige Lösungen gefunden werden, bevor die Berechnung endet. Wenn Sie eine praktikable Lösung wünschen, auch wenn dies nicht die optimale Lösung ist, können Sie maxsol 1 verwenden, um sie schneller zu finden. Ich kann es schaffen

Andere Parameter als "maxsol" sind ebenfalls auf der GAMS [^ 8] -Seite beschrieben. Es kann interessant sein, den Unterschied beim Spielen mit verschiedenen Dingen zu sehen.

Das ist es. Wenn Sie Vorschläge haben, zögern Sie bitte nicht, uns zu kontaktieren.