1. Zuallererst

Dies ist Qiitas erster Beitrag. Dieser Artikel wurde als Memorandum aufgezeichnet und es kann einige Fehler geben.

Die von IBM ILOG als Optimierungslösung bereitgestellte Entwicklungsumgebung heißt IBM ILOG CPLEX Optimization Studio. Zu den CPLEX-Entwicklungssprachen gehören C / C ++ / Java / Python. Andere Optimierungsprobleme können mithilfe der OPL-Sprache mithilfe des Eclipse-Plugins beschrieben werden. Mit der Integrated Development Environment (IDE) von CPLEX Studio können Sie Optimierungsprobleme grundsätzlich interaktiv mit der Entwicklung mithilfe der OPL-Sprache lösen und gleichzeitig Mehrzweckoptimierungsprobleme und weitere mit CPLEX erzielte Lösungen lösen. Es scheint ein wenig schwierig zu sein, es in Situationen wie der Anwendung auf das Problem von zu verwenden. Daher werde ich dieses Mal einen Artikel mit der Bedeutung schreiben, den Aufbau der Entwicklungsumgebung durch die Python-API als Memorandum aufzuzeichnen. Hier gibt es zwei wichtige CPLEX-Python-APIs, DOCplex [1] und Python-API (Legacy) [2], aber es scheint, dass die Legacy-Version in nicht allzu ferner Zukunft abgeschafft wird, daher werden wir hier DOCplex verwenden. Wir werden die verwendete Entwicklungsumgebung erstellen.

2. Betriebsumgebung

Funktionsprüfung ・ Ubuntu 18.04 Bionic (64 Bit, 8 GB, auf VMWare) ・ CPLEX Optimization Studio 12.9 ・ Python 3.7.3 Es wurde um gemacht.

Als Voraussetzung ist Python bereits installiert. Außerdem ist Python Python2 * (≧ Python2.7.9) oder Python3 * (≧ Python3.6). (Es scheint jedoch, dass Python 3.8 und höher nicht unterstützt werden)
In diesem Artikel erstellen wir eine Umgebung ohne Verwendung von pip oder conda. Die Installation mit pip / conda wurde bereits durchgeführt, daher werde ich hier nicht darauf eingehen.

3. Installationsanweisungen für CPLEX Studio 12.9

Zunächst DL CPLEX Studio. Laden Sie .bin von der Website [3] herunter (vorausgesetzt, Sie geben es in ~ / Downloads ein). Obwohl es sich um eine Download-Methode handelt, wird sie hier weggelassen, da sie leicht durch Lesen von [3] heruntergeladen werden kann.

Beginnen wir nach dem Herunterladen mit der Installation. Gehen wir zu ~ / Downloads und arbeiten daran.


$cd ~/Downloads

Geben Sie zunächst der .bin-Datei die Ausführungsberechtigung.

$chmod +x CPLEX_OPT_STUD_129_LNX_X86-64.bin

Führen Sie dann die BIN-Datei aus.

$sudo ./CPLEX_OPT_STUD_129_LNX_X86-64.bin

In einigen Sprachen wird das Installationsprogramm gestartet und stellt Ihnen einige Fragen. Es ist unten zusammengefasst. Wenn es dir nicht gefällt, drücke einfach auf Beenden, um anzuhalten.

Lokale Auswahl: -> 1. Englisch oder 2. Japanisch
Es wird empfohlen, alle Programme vor der Installation zu beenden: -> ENTER oder zurück
Geben Sie den Installationspfad an: / opt / ibm / ILOG / CPLEX_Studio129 ist die Standardeinstellung
Drücken Sie zur Installation ENTER: -> ENTER
Überprüfen Sie die Festplattenkapazität (ca. 2 GB): -> ENTER
Erfolgreiche Installation: -> ENTER

Sie müssen einige Wege gehen. CPLEX verfügt über zwei Optimierungs-Engines, Mathematical Programming (MP) und Constraint Programming (CP), die jeweils einen anderen Binärpfad haben. Öffnen Sie die Shell-Konfigurationsdatei (~ / .bashrc) und schreiben Sie den folgenden Export nach der letzten Zeile.

$echo "export LD_LIBRARY_PATH="/opt/ibm/ILOG/CPLEX_Studio129/opl/bin/x86-64_linux:$LD_LIBRARY_PATH"
$echo "export PATH="/opt/ibm/ILOG/CPLEX_Studio129/opl/bin/x86-64_linux:$PATH"
$echo "export PATH="/opt/ibm/ILOG/CPLEX_Studio129/cplex/bin/x86-64_linux:$PATH"
$echo "export PATH="/opt/ibm/ILOG/CPLEX_Studio129/cpoptimizer/bin/x86-64_linux:$PATH"

Wenn Sie es hinzufügen, werde ich es reflektieren.


$source ~/.bashrc

Nun wollen wir sehen, ob der Befehl funktioniert.

$cplex
Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.9.0.0
with Simplex, Mixed Integer & Barrier Optimizers
5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21
Copyright IBM Corp. 1988, 2019. All Rights Reserved.
Type 'help' for a list of available commands.
Type 'help' followed by a command name for　more
information on commands.

Lassen Sie uns auch die Optimierungs-Engine für die Einschränkungsprogrammierung starten und überprüfen.

$cpoptimizer
Welcome to IBM(R) ILOG(R) CP Interactive Optimizer 12.9.0.0
with Simplex, Mixed Integer & Barrier Optimizers
5724-Y48 5724-Y49 5724-Y54 5724-Y55 5724-A06 5724-A29
Copyright IBM Corp. 1990, 2019. All Rights Reserved.

Type 'help' for a list of available commands.
Type 'help' followed by a command name for　more
information on commands.

Wenn der Pfad übergeben wird, sollte auch der folgende Befehl übergeben werden. Wenn der Inhalt der Hilfe schlampig angezeigt wird, verläuft der Pfad problemlos.

$oplrun

[Wenn der Befehl nicht gefunden angezeigt wird und nicht ordnungsgemäß gestartet wird] Es scheint, dass die Einstellung LD_LIBRARY_PATH möglicherweise nicht wiedergegeben wird (ist sie vom Betriebssystem abhängig? ..?). Dies kann vermieden werden, indem der Pfad in der gemeinsam genutzten Bibliothek registriert wird (ich weiß nicht viel darüber ...). Es scheint in Ordnung zu sein, wenn Sie eine Datei mit dem Namen hogehoge.conf unter /etc/ld.so.conf.d erstellen und LD_LIBRARY_PATH hinzufügen.


$sudo vim /etc/ld.so.conf.d/oplrun.conf

Ich werde folgendes drinnen schreiben.

/opt/ibm/ILOG/CPLEX_Studio129/opl/bin/x86-64_linux/
/opt/ibm/ILOG/CPLEX_Studio129/cplex/bin/x86-64_linux/
/opt/ibm/ILOG/CPLEX_Studio129/cpoptimizer/bin/x86-64_linux/

Speichern Sie die Datei und erstellen Sie den Cache neu.

$sudo ldconfig

4. DOCplex-Setup

In diesem Artikel habe ich CPLEX in / opt / ibm / ILOG / CPLEX_Studio129 / ... installiert. Im Folgenden wird / opt / ibm / ILOG / CPLEX_129 als (CPLEX_DIR) platziert. Wenn Sie selbst einen beliebigen Pfad festlegen, sollte CPLEX_DIR ein anderer Pfad sein. Achtung.

Gehen Sie zu (CPLEX_DIR) / python / docplex / und Sie finden eine Datei namens setup.py, führen Sie sie aus.

$cd (CPLEX_DIR)/python/docplex
$sudo python3 setup.py install

Das Setup beginnt und endet innerhalb von Sekunden. Damit ist der Aufbau der DOCplex-Umgebung abgeschlossen.

5. Lösen Sie das Beispiel

Von hier aus werde ich kurz darauf eingehen, wie man anhand des offiziellen Referenzmusters schreibt [4]. Da ich mich selbst studiere, gibt es einige Unsicherheiten, aber ich wäre dankbar, wenn ich in irgendeiner Weise dazu beitragen könnte.

Hier werde ich das erste Beispiel von [4], Das Transportproblem, aufgreifen.

Dies ist ein Problem, das die Kosten für den Transport von Waren an zwei Standorten zu drei Standorten minimiert. Die Figur ist ein gerichteter nicht kreisförmiger Graph (DAG) mit nicht negativer ganzzahliger Gewichtung. Der Ausgangsknoten links zeigt die Orte an, an denen Lieferungen durchgeführt werden können. Außerdem sind die rot geschriebenen Zahlen die Gewichte jedes Knotens und geben die Gesamtmenge der Waren an, die transportiert werden können. Die grüne Zahl neben dem Eingangsknoten rechts gibt die Gesamtmenge der vom Standort benötigten Lieferungen an. Der Bogen zwischen den Knoten gibt die transportable Route an, und das Gewicht auf dem Bogen gibt die Transportkosten pro Material an.

Bei diesem Problem gibt es verschiedene Kombinationen zur Berechnung der Transportkosten. Da dies ein einfaches Beispiel ist, kann die optimale Lösung leicht wie folgt gefunden werden.

Knoten 3 kann nur Lieferungen von Knoten 1 empfangen und benötigt 7 Lieferungen. Da daher nur Lieferungen 7 von Knoten 1 an Knoten 3 gesendet werden, beträgt die verbleibende Menge von Knoten 1 8, und zu diesem Zeitpunkt werden Lieferungen 7 zu Transportkosten von 2 an Knoten 3 gesendet, so dass Transportkosten von 2 × 7 = 14 erforderlich sind. Machen.

In ähnlicher Weise beträgt die Menge an Resten in Knoten 2 20-10 = 10, da Knoten 4 nur Lieferungen von Knoten 2 empfangen kann, und die Transportkosten betragen zu diesem Zeitpunkt 10 x 5 = 50, so dass die Menge an Resten in Knoten 1 8 beträgt. Knoten 2 hat 10 Reste und Knoten 5 benötigt 15 Vorräte. Zu diesem Zeitpunkt, da die Transportkosten von Knoten 2 zu Knoten 5 niedrig sind, trägt Knoten 2 alle 10 und der verbleibende Betrag 0, während die erforderlichen Vorräte für Knoten 5 5 betragen, wenn wir uns dafür entscheiden, Vorräte bevorzugt von Knoten 2 zu befördern. Ich werde. Schließlich können alle Anforderungen erfüllt werden, indem nur 5 Lieferungen von Knoten 1 an Knoten 5 gesendet werden. In diesem Prozess trägt Knoten 2 10 zu Transportkosten 3, also 10 × 3 = 30 Transportkosten, und Knoten 1 trägt nur 5 zu Transportkosten 4, sodass 5 × 4 = 20 Transportkosten erforderlich sind.

Aus dem oben Gesagten sind die endgültigen Transportkosten von 14 + 50 + 30 + 20 = 114 erforderlich.

Um dieses Problem als Optimierungsproblem zu etablieren, müssen die Zielfunktion und die Einschränkungen organisiert und die Entscheidungsvariablen definiert werden.

Zielfunktion: Minimieren Sie die Gesamtversandkosten
Einschränkung 1: Das Exportvolumen jedes Knotens auf der linken Seite ist gleich oder kleiner als das Gewicht.
Einschränkung 2: Das Importvolumen jedes Knotens auf der rechten Seite ist gleich oder größer als das Gewicht.

Basierend auf dem oben Gesagten scheint es gut, die Entscheidungsvariablen wie folgt festzulegen.

Determinantenvariable: x (i, j) : Menge der von node_i nach node_j transportierten Waren

Ich werde das Programm unten schreiben.

`sample.py`


 #URL/Sie können das Problem in der Cloud lösen, indem Sie den Schlüssel schreiben.
 #Hier wird angenommen, dass es lokal ausgeführt wird, daher wird es auf Keine gesetzt.
url=None
key=None

 #Preparation of data
 #Knoten 1 ist 15,Knoten 2 hat nur 20 Vorräte
capacities = {1:15, 2:20} 
 #Knoten 3 ist 7,Knoten 4 ist 10,Knoten 5 hat 15 Anfragen
demands = {3:7, 4:10, 5:15}
 #Zu diesem Zeitpunkt betragen die Kosten im Lichtbogen(1,3)=2, (1,5)=4, (2,4)=5, (2,5)=Weil es 3 ist
costs = {(1,3):2, (1,5):4, (2,4):5, (2,5):3}
source = range(1,3) #Bereich in Python(i,j)Bin ich...j-Bis zu 1
target  = range(3,6)

 #description of a problem
 #Docplex importieren
from docplex.mp.model import Model
tm = Model(name='transportation')

 #decision (continuous) variable 
 #Variable x(i,j)Ist im Problem tm definiert. x ist eine stetige Variable, i bezieht sich auf die Quelle und j bezieht sich auf das Ziel. Dies ist jedoch kostenpflichtig(Diejenigen, die mit dem Lichtbogen verbunden sind)Nur in Fällen.
x = {(i,j): tm.continuous_var(name='x_{0}_{1}'.format(i,j)) for i in source for j in target if (i,j) in costs}
tm.print_information()

 #add constraints
 # (1,3), (1,5)Die Gesamtmenge der Lieferungen, die tragen[1]  (=15)Nicht überschreiten
 # (2,4), (2,5)Die Gesamtmenge der Lieferungen, die tragen[2]  (=20)Nicht überschreiten
for i in source:
    tm.add_constraint(tm.sum(x[i,j] for j in target if (i,j) in costs) <= capacities[i] )
for j in target:
    tm.add_constraint(tm.sum(x[i,j] for i in source if (i,j) in costs) >= demands[j] )

 #Objective function
 #Zielfunktion ist Bogen(i,j)Minimieren Sie den Gesamtbetrag der dazwischen liegenden Transportkosten
tm.minimize(tm.sum(x[i,j]*costs[i,j] for i in source for j in target if (i,j) in costs))

 #Solve
 #Das Problem lösen
tms = tm.solve(url=url,key=key)

 #Display and exceptions
 #Lösung anzeigen
assert tms
tms.display()

Beim Ausführen erhalten Sie:


Model: transportation
 - number of variables: 4
   - binary=0, integer=0, continuous=4
 - number of constraints: 0
   - linear=0
 - parameters: defaults
solution for: transportation
objective: 114.000
x_1_3 = 7.000
x_1_5 = 5.000
x_2_4 = 10.000
x_2_5 = 10.000

Dies ist das Ende der Einführung von DOCplex (Python-API).

Referenzlink

1: Offizielle DOCplex-Referenz 2: Python-API(Legacy) 3: CPLEX Download 4: Offizielles DOCplex-Referenzbeispiel

Rufen Sie CPLEX von Python aus auf (DO cplex)