HorusLP-Gurobi: High-Level-Optimierungsarchitektur für Gurobi

Da die Optimierungstechnologien immer ausgefeilter werden, spielen kommerzielle Solver eine immer wichtigere Rolle in der Industrie. Im Vergleich zu Open-Source-Lösern verfügen kommerzielle Lösungen tendenziell über mehr Funktionen zum Lösen komplexer Optimierungsmodelle, wie z. B. erweitertes Vorlösen, Warmstart und verteiltes Lösen.

Einer der beliebtesten kommerziellen Solver auf dem Markt ist Gurobi, benannt nach den Mitbegründern Zonghao Gu, Edward Rothberg und Robert Bixby, die alle Pioniere im Bereich kommerzieller Solver waren. Gurobi hat in der jüngeren Geschichte viele hochkarätige Optimierungsprojekte vorangetrieben, darunter das Bandbreitenzuweisungsprojekt der FCC und das Gefangenen-Neuzuweisungsprojekt des Pennsylvania State Prison.

Heute werden wir uns ansehen, wie HorusLP, ein Softwarepaket, das eine deklarative Schnittstelle auf hoher Ebene für die Optimierungsmodellierung bereitstellt, in die API von Gurobi integriert wird, um Benutzern ein intuitives Modellierungserlebnis zu bieten und gleichzeitig die fortschrittlichsten Funktionen von Gurobi zu nutzen.

Optimierung: Eine schnelle Auffrischung

Für diejenigen, die mit Optimierung oder Operations Research nicht vertraut sind, bezieht sich Optimierung auf eine Sammlung mathematischer Techniken, die die optimalen Werte von Variablen innerhalb eines Gleichungssystems finden, das einem System von Einschränkungen unterliegt. Wenn der obige Satz etwas trocken klingt, hilft vielleicht ein Beispiel zur Veranschaulichung.

Angenommen, Sie hätten einen Rucksack mit einer Tragfähigkeit von 15 Pfund. Sie haben einige Gegenstände vor sich, die jeweils ein bestimmtes Gewicht und einen bestimmten Geldwert haben:

1. Kamera: Gewicht 2 Pfund, Wert 5 $
2. Figur: Gewicht 4 Pfund, Wert 7 $
3. Apfelwein: Gewicht 7 Pfund, Wert 2 $
4. Horn: Gewicht 10 Pfund, Wert 10 $.

Sie möchten Gegenstände auswählen, die Sie in Ihrem Rucksack verstauen, sodass das Gesamtgewicht unter 15 Pfund bleibt, aber der Wert maximiert wird. (Wenn Sie mehr Kontext dazu benötigen, warum wir hochwertige Gegenstände in einen Rucksack stecken, werden Sie ermutigt, Ihre Vorstellungskraft für eine Erzählung einzusetzen. Gute Kandidatenerzählungen beinhalten die Rettung von Dingen aus einem Feuer und Immobilienauktionen … oder einige schändliche Aktivitäten, die wir lieber nicht erwähnen.)

Wir können das Problem als folgendes Optimierungsproblem formulieren:

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Sobald wir dieses Problem formuliert haben, können wir Optimierungstechniken anwenden, um die besten Gegenstände für unseren Rucksack zu finden. Ein Beispiel für die Lösung finden Sie in meinen früheren Artikeln zum Lösen von Optimierungsproblemen mit Python und zum Lösen von Optimierungsproblemen mit der zentralen HorusLP-API.

Die zugrunde liegende mathematische Technik ist ziemlich faszinierend, aber außerhalb des Rahmens dieses Artikels. Wenn Sie mehr erfahren möchten, empfehle ich, hier und hier zu suchen, beide mit freundlicher Genehmigung von Gurobi.

Gurobi

Während die frühesten Optimierungsprobleme von Mathematikerteams gelöst wurden, die mit Taschenrechnern arbeiteten, werden die meisten Optimierungsprobleme heute mit spezialisierter Software gelöst, die Solver genannt werden. Während die meisten Löser im Allgemeinen in der Lage sind, Lösungen für die meisten gut formulierten linearen und ganzzahligen Programmierprobleme zu finden, sind einige Löser viel leistungsfähiger als andere. Sie können Klassen von Problemen lösen, die andere nicht lösen können, Probleme schneller lösen, indem sie modernste Mathematik anwenden, oder große, schwierige Probleme mit verteilten Computern lösen. Die fortschrittlichsten Funktionen werden normalerweise in kommerziellen Solvern bereitgestellt, die von Unternehmen entwickelt und gewartet werden, die sich auf die Entwicklung der schnellsten und ausgereiftesten Solver spezialisiert haben.

Gurobi ist einer der führenden Anbieter auf dem Markt für kommerzielle Solver, der von großen Segmenten der Optimierungsgemeinschaft verwendet wird, darunter Regierungen, akademische Einrichtungen und Unternehmen, die in Branchen von Finanzen bis Logistik tätig sind. In Bezug auf die Geschwindigkeit schneidet Gurobi in mehreren Benchmarks, die zur Beurteilung von kommerziellen und Open-Source-Lösern verwendet werden, durchweg besser ab.

Gurobi wird auch mit einer leistungsstarken Python-API geliefert, mit der Sie Modelle aus Python erstellen können. Diese Funktion gibt Modellierern während der Modellerstellung Zugriff auf alle nützlichen Datenbearbeitungsbibliotheken von Python, was ihren Prozess erheblich unterstützt. Als Demonstration der Gurobi-Python-API sehen Sie hier, wie Sie das Rucksackproblem modellieren könnten:

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

Wenn Sie das Beispiel ausführen, erhalten Sie die folgende Ausgabe:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

HorusLP

HorusLP ist eine Optimierungsmodellierungsbibliothek, die auf Erfahrungen bei der Entwicklung von Optimierungsalgorithmen aufgebaut wurde. Den gegenwärtig verfügbaren Modellierungsbibliotheken mangelt es an Werkzeugen, die zum Arbeiten mit der Art von komplexen, facettenreichen Problemen erforderlich sind, die typischerweise bei kommerziellen Anwendungen von Operations Research angetroffen werden.

Während die meisten Optimierungsbibliotheken eine imperative Schnittstelle auf niedriger Ebene bieten, werden mit zunehmender Komplexität von Optimierungsmodellen bessere Tools benötigt, um die Komplexität zu bewältigen. HorusLP ist eine Bibliothek, die übergeordnete Tools zur Verwaltung dieser Komplexitäten bereitstellt. HorusLP bietet außerdem leistungsstarke Debugging- und Reporting-Tools, die eine schnellere Entwicklung und Iteration ermöglichen.

Im Kern ist HorusLP eine objektorientierte Bibliothek, die eine dringend benötigte Architektur rund um Optimierungsmodelle bereitstellt. Durch Nutzung der objektorientierten Python-Syntax bietet die HorusLP-Bibliothek eine Struktur, um die herum Optimierungsmodelle optimiert werden können. Das Ergebnis ist eine Codebasis, die entkoppelt, modular und einfach zu lesen ist.

Wenn Sie eine detailliertere Einführung in die zentrale HorusLP-Bibliothek mit Codebeispielen wünschen, finden Sie hier ein Tutorial.

HorusLP-Gurobi-Integration

Während die Kern-API von HorusLP eine bequeme API auf hoher Ebene zum Erstellen von Optimierungsmodellen bietet, basiert sie auf PuLP, das zwar Gurobi als Solver verwenden kann, aber keinen Zugriff auf einige der fortgeschritteneren Funktionen von Gurobi hat.

HorusLP-Gurobi ist eine Version der HorusLP-API, die mit der Python-API von Gurobi erstellt wurde. Dies ermöglicht dem Benutzer den direkten Zugriff auf erweiterte Funktionen von Gurobi, während die HorusLP-API konsistent bleibt.

Eine der Schlüsselphilosophien, die die Entwicklung von HorusLP-Gurobi leiteten, war die Konsistenz mit der HorusLP-Kern-API. Indem die minimalistische Struktur von HorusLP konsistent bleibt, kann ein Benutzer eines Open-Source-Solvers leicht auf die Verwendung von Gurobi umsteigen, indem er die Gurobi-API installiert und die Importanweisungen ändert.

Für einfache Modelle benötigen HorusLP-basierte Modelle mehr Codezeilen als die zwingende Verwendung der Python-API. Da der Entwicklungsprozess jedoch weitergeht und die Modelle komplexer werden, werden die objektorientierten und deklarativen Designs der HorusLP-API das Debugging und die Entwicklung erleichtern. Die Objektorientierung macht das Modell auch lesbarer, da die Modelldefinition die Ziele, Einschränkungen und Variablen usw. zentralisiert und klar abgrenzt.

Lassen Sie uns ohne weiteres in einige Codebeispiele eintauchen!

Codebeispiele

Grundlegende HorusLP-API

Da HorusLP-Gurobi die API konsistent hält, kann der Code aus dem HorusLP-Core-Tutorial mit einer einfachen Änderung der Importe übernommen werden. Um HoruLP-Gurobi verwenden zu können, müssen Sie jedoch sicherstellen, dass Sie den Gurobi-Optimierer und die Python-Schnittstelle von Gurobi installiert haben. Sie können Gurobi erhalten, indem Sie sich hier mit ihnen in Verbindung setzen.

Sobald Sie Gurobi installiert haben, können wir mit der Programmierung mit HorusLP-Gurobi beginnen! Beginnen wir mit der Installation des erforderlichen Pakets:

 Pip install horuslp horuslp-gurobi

Sobald die Installation abgeschlossen ist, können wir mit der Verwendung von HorusLP-Gurobi beginnen! Erinnern Sie sich an das Beispiel Rucksackproblem von früher. Wir können HorusLP-Gurobi verwenden, um das Problem wie folgt zu modellieren:

Importieren Sie zunächst die relevanten Bibliotheken.

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

Definieren Sie einige Variablen.

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

Nun können wir die Constraints mit der Constraints-Klasse definieren.

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Wir können dann das Ziel auf ähnliche Weise umsetzen.

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Und schließlich können wir das Problem definieren.

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

Und wir instanziieren das Problem und rufen die Lösungsfunktion auf. Hier geschieht die Magie.

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

Führen Sie den Code aus und Sie sollten die folgende Ausgabe sehen:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% KnapsackProblem: Optimal camera -0.0 figurine 1.0 cider -0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': -0.0, 'figurine': 1.0, 'cider': -0.0, 'horn': 1.0}

Der erste Teil ist der Gurobi-Solver und der zweite Teil ist die Ausgabe von HorusLP. Wie Sie sehen können, empfiehlt der Algorithmus, dass wir die Figur und das Horn nehmen, was zu 14 Pfund an Gegenständen mit einem Wert von 17 $ führt.

Einer der Vorteile der Verwendung von HorusLP mit Gurobi besteht darin, dass Sie viele Informationen „kostenlos“ erhalten. Viele der Informationen, die man sich normalerweise während der Entwicklung ansehen möchte, wie z. B. der Wert jeder Variablen, der endgültige Zielwert und die Beschränkungswerte, werden automatisch berechnet und in einem leicht lesbaren Format ausgegeben.

Wenn Sie den vorherigen Artikel über den HorusLP-Kern gelesen haben, werden Sie feststellen, dass dies fast genau dieselbe API ist. Um die API einfach zu halten, sind die Schnittstellen von HorusLP-Kern und HorsLP-Gurobi identisch, wobei die Unterschiede zwischen den Lösern in der Implementierung der Oberklasse abstrahiert werden.

Daher überlassen wir die Einführung von HorusLP diesem einfachen Beispiel; Komplexere Beispiele, die erweiterte Funktionen von HorusLP demonstrieren, finden Sie im vorherigen Artikel.

Gurobi-Funktionen

Gurobi bietet viele erweiterte Funktionen zur Lösung komplexer Probleme. Auf die meisten Funktionen kann über das Model-Objekt zugegriffen werden. Um eine vollständige Kompatibilität mit der Gurobi-API zu ermöglichen, ist das Modellobjekt von der Problemklasse als model leicht zugänglich.

Wenn Sie beispielsweise die MPS-Datei des Rucksackmodells schreiben möchten, können Sie in Gurobi so etwas wie m.write('knapsack.mps') schreiben. Während Sie HorusLP-Gurobi verwenden, können Sie einfach:

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

Und Sie sollten die MPS-Datei in Ihrem Arbeitsverzeichnis sehen.

Sie können diese Schnittstelle verwenden, um auf erweiterte Gurobi-Funktionen wie das Berechnen von IIS, das Erstellen von Rückrufen oder das Geben variabler Hinweise zuzugreifen.

Erweiterte Gurobi-Funktionen zu Ihren Diensten

Heute haben wir uns eine Version der HorusLP-Bibliothek angesehen, die auf der Gurobi-Python-API aufbaut. Zusätzlich zu den Berichts- und Debugging-Funktionen des zentralen HorusLP haben Sie jetzt Zugriff auf alle erweiterten Funktionen von Gurobi, die nahtlos durch die Integration mit der Python-API von Gurobi zugänglich sind.

Wenn Sie ein aktueller Gurobi-Benutzer sind oder jemand daran interessiert ist, die Gurobi-Optimierung zu verwenden, hoffe ich, dass Sie HorusLP ausprobieren! Auf GitHub können Sie Beispielcode finden, Vorschläge machen oder zu HorusLP-Gurobi beitragen.