Architekturoptimierungsalgorithmen mit HorusLP

Operations Research und konvexe Optimierung sind ein Gebiet der angewandten Mathematik, das im Laufe der Jahre weitreichende kommerzielle Anwendungen gefunden hat. Als Rechenleistung erschwinglicher und allgemein verfügbar wurde, begannen die Forscher, immer ausgefeiltere Optimierungsalgorithmen zu entwickeln, um ihnen zu helfen, bessere Entscheidungen zu treffen. Heute treiben Anwendungen, die auf Operations Research basieren, alles voran, von der Routenführung in der globalen Logistik bis hin zur Glättung der Stromerzeugung in der Energiewirtschaft.

Da die zugrunde liegende Technologie immer komplexer wurde, wurde eine neue Reihe von Tools entwickelt, die Forschern und Entwicklern helfen sollen, produktiver zu arbeiten. Diese Tools, wie AMPL, CVXPY und PuLP, ermöglichen es Entwicklern, Optimierungsalgorithmen schnell zu definieren, zu erstellen und auszuführen und mit einer Vielzahl von Solvern zu interagieren.

Während Optimierungstechnologien und Geschäftsanforderungen immer ausgefeilter werden, sind die meisten dieser Tools mehr oder weniger gleich geblieben und haben sich nicht schnell genug weiterentwickelt, um die Anforderungen der Branche zu erfüllen. Daher erfordert das Entwickeln, Verwalten, Debuggen und Optimieren dieser Algorithmen häufig einen großen kognitiven Overhead, insbesondere in einem schnelllebigen Geschäftsumfeld.

Heute möchte ich HorusLP vorstellen, eine Python-Optimierungsbibliothek, die bei der Architektur von Workflows zur Entwicklung von Algorithmen hilft. Wir werden über die Probleme sprechen, die das Tool lösen soll, dann einen schnellen Überblick über die Python-Bibliothek geben und einige Beispiel-Optimierungsalgorithmen erstellen.

Probleme, mit denen Entwickler von Optimierungsalgorithmen konfrontiert sind

Eines der ständigen Probleme, mit denen die meisten Entwickler konfrontiert sind, ist das Gleichgewicht zwischen dem Erstellen einer wartbaren, effizienten, idiomatischen Software und der Bereitstellung eines Produkts innerhalb der Zeitvorgaben des Projekts. Unabhängig davon, ob Sie an einer browserbasierten Anwendung, einer Web-API oder einem Mikrodienst zur Benutzerauthentifizierung arbeiten, gibt es oft einen Kompromiss zwischen dem „richtigen“ und dem „schnellen“ Weg, um Ihre Ziele zu erreichen. Dieser inhärente Kompromiss wird mit zunehmender Produktkomplexität deutlicher.

In den meisten Disziplinen kann ein Entwickler dieses Problem lösen, indem er ein Framework oder eine Bibliothek auswählt, die bei der Architektur hilft. Im Web-Frontend wählen viele Entwickler React oder Angular; In der Welt der API-Entwicklung können Softwareentwickler unter vielen anderen zwischen Django, ASP.NET MVC oder Play wählen. Wenn es jedoch um den bescheidenen Entwickler von Optimierungsalgorithmen geht, gibt es nur sehr wenige Architekturwerkzeuge, die helfen, die architektonische Komplexität zu bewältigen. Dem Entwickler bleibt es überlassen, Variablen, Einschränkungen und verschiedene Ziele selbst zu verwalten. Darüber hinaus sind Operations-Research-Algorithmen im Allgemeinen schwer zu überprüfen, was das Problem verschärft.

Der Hauptzweck von HorusLP besteht darin, einen architektonischen Rahmen für die Entwicklung von Optimierungsalgorithmen bereitzustellen. Durch die Bereitstellung struktureller Konsistenz erleichtert das Framework die Organisation und ermöglicht es Entwicklern, sich auf das zu konzentrieren, was sie am besten können: das Erstellen von Algorithmen.

Typische Herausforderungen im Optimierungs-Workflow

Bei der Entwicklung von ODER-Algorithmen gibt es mehrere Hauptursachen für Komplexität:

Komplexität aus Variablen

• Variablen müssen oft hinzugefügt werden, um zusätzliche Geschäftsanforderungen zu erfüllen, und es gibt keine einfache Möglichkeit, sie für die spätere Verwendung in Modelldefinitionen und Berichten zu verfolgen.
• Verwandte Variablen müssen gruppiert und nachverfolgt werden, und es gibt keine offensichtliche Möglichkeit, sie zu verwalten.

Komplexität durch Einschränkungen

• Einschränkungen müssen hinzugefügt und entfernt werden, um verschiedene Szenarien zu unterstützen und das Debuggen durchzuführen, aber es gibt keinen offensichtlichen Ort zum Hinzufügen oder Entfernen von Einschränkungen.
• Einschränkungen sind oft miteinander verbunden/abhängig, und es gibt keine natürliche Möglichkeit, ihre Beziehungen auszudrücken.

Komplexität durch Ziele

• Objektive Ausdrücke können unhandlich werden, wenn sie mehrere Komponenten haben. Dies kann noch verstärkt werden, wenn die verschiedenen Komponenten gewichtet werden und die Gewichtungen basierend auf den Geschäftsanforderungen angepasst werden müssen.

Komplexität durch Debugging

• Es gibt keine einfache Möglichkeit, die Ergebnisse des Modells während der Entwicklung anzuzeigen. Ein Entwickler muss explizit neue Variablen und Beschränkungswerte drucken, um die Ergebnisse zu sehen. Dies führt zu doppeltem Code und einer langsameren Entwicklung.
• Wenn das Hinzufügen einer Einschränkung dazu führt, dass das Modell undurchführbar wird, ist es möglicherweise nicht offensichtlich, warum die Einschränkung dazu geführt hat, dass das Modell undurchführbar wurde. Normalerweise müssen Entwickler verschiedene Einschränkungen beseitigen und durch Versuch und Irrtum nach der Inkompatibilität suchen

HorusLP hofft, diese Herausforderungen besser beherrschbar zu machen, indem es Strukturen, Tools und Best Practices bereitstellt, um die Entwicklerproduktivität und die Wartbarkeit des Produkts zu verbessern.

HorusLP Tutorial: Optimierungsalgorithmus und Überblick über die API

Lassen Sie uns ohne weiteres eintauchen und sehen, was die HorusLP-Bibliothek für Sie tun kann!

Da HorusLP auf Python und PuLP basiert, möchten wir sie mit pip installieren. Führen Sie Folgendes in Ihrer Befehlszeile aus:

 Pip install horuslp pulp

Sobald die Installation abgeschlossen ist, können wir fortfahren und eine Python-Datei öffnen. Wir werden das Rucksackproblem aus meinem früheren Artikel über Operations Research implementieren.

Die HorusLP-Bibliothek hat eine sehr einfache deklarative API und sehr wenig Boilerplate. Beginnen wir mit dem Importieren der erforderlichen Klassen und Variablen:

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

Nachdem wir alle Variablen importiert haben, definieren wir die Variablen, die wir für dieses Problem benötigen. Dazu erstellen wir eine Variablenmanager-Unterklasse und füllen sie mit den binären Variablen:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

Nachdem die Variablen nun definiert sind, definieren wir die Einschränkungen. Wir erstellen Constraints, indem wir die Hauptconstraint-Klasse in Unterklassen umwandeln und ihre „define“-Funktion implementieren.

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

In der Define-Funktion können Sie die benötigten Variablen namentlich erfragen. Das Framework findet die Variable im Variablenmanager und übergibt sie an die Define-Funktion.

Nachdem die Einschränkung implementiert wurde, können wir das Ziel implementieren. Da es sich um ein einfaches Ziel handelt, verwenden wir ObjectiveComponent :

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Die Define-Funktion hat einen sehr ähnlichen Aufbau wie die Define-Funktion der Constraint-Klasse. Anstatt einen Einschränkungsausdruck zurückzugeben, geben wir jedoch einen affinen Ausdruck zurück.

Nachdem nun die Variablen, Einschränkungen und Ziele definiert sind, definieren wir das Modell:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

Um das Modell zu erstellen, erstellen wir eine Klasse, die eine Unterklasse der Klasse Problem ist, und spezifizieren die Variablen, Ziele, Einschränkungen und den Sinn. Mit dem angegebenen Problem können wir das Problem lösen:

 prob = KnapsackProblem() prob.solve()

Nach der Lösung können wir die Ergebnisse mit der Funktion print_results der Problemklasse drucken. Wir können auch auf den Wert bestimmter Variablen zugreifen, indem wir uns die Klasse result_variables .

 prob.print_results() print(prob.result_variables)

Führen Sie das Skript aus, und Sie sollten die folgende Ausgabe sehen:

 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}

Sie sollten den Problemstatus, den Endwert der Variablen, den Zielwert und den Wert des Einschränkungsausdrucks sehen. Wir sehen auch die resultierenden Werte der Variablen als Wörterbuch.

Und da haben wir es, unser erstes HorusLP-Problem in ungefähr 35 Zeilen!

In den kommenden Beispielen werden wir einige anspruchsvollere Funktionen der HorusLP-Bibliothek untersuchen.

Verwendung von Variablengruppen

Manchmal sind Variablen verwandt und gehören zu einer logischen Gruppe. Beim Rucksackproblem können alle Variablen in eine Objektgruppe gestellt werden. Wir können den Code umgestalten, um die Variablengruppe zu verwenden. Stellen Sie sicher, dass Sie den Code aus dem vorherigen Abschnitt speichern, da wir in nachfolgenden Tutorials darauf verweisen werden!

Ändern Sie die Importanweisungen wie folgt:

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

Jetzt müssen wir auch die Knapsack-Variablendeklarationen wie folgt ändern:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

Das erste Argument ist der Name der Variablengruppe, die zweite Variable ist eine Liste mit Namen für die Variablen innerhalb dieser Gruppe.

Jetzt müssen wir die Einschränkung und die objektiven Definitionen ändern. Anstatt nach den einzelnen Namen zu fragen, fragen wir nach der Variablengruppe, die als Wörterbuch übergeben wird, in dem die Schlüssel die Namen und die Werte die Variablen sind. Ändern Sie die Beschränkungs- und Zieldefinitionen wie folgt:

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

Jetzt können wir dieselbe Problemdefinition verwenden und Befehle ausführen:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

Sie sollten dies in Ihrer Ausgabe sehen:

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

Verwalten mehrerer Einschränkungen

Modelle mit einer einzigen Einschränkung sind relativ selten. Wenn Sie mit mehreren Einschränkungen arbeiten, ist es gut, alle Einschränkungen an einem Ort zu haben, damit sie einfach nachverfolgt und verwaltet werden können. HorusLP macht das natürlich.

Nehmen wir zum Beispiel an, wir wollten sehen, wie sich die Ergebnisse ändern würden, wenn wir das Modell dazu zwingen würden, unserem Rucksack eine Kamera hinzuzufügen. Wir würden eine zusätzliche Einschränkung implementieren und sie unserer Problemdefinition hinzufügen.

Kehren Sie zu dem Modell zurück, das wir im ersten Tutorial implementiert haben. Fügen Sie die folgende Einschränkung hinzu:

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

Um die Einschränkung zum Modell hinzuzufügen, müssen wir sie einfach wie folgt zur Problemdefinition hinzufügen:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

Führen Sie das Problem aus, und Sie sollten die folgende Ausgabe sehen:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Sie sollten die neue Beschränkung sehen, die in der Standardausgabe gedruckt wird, und die geänderten optimalen Variablenwerte.

Verwalten von abhängigen Beschränkungen und Beschränkungsgruppen

Constraints sind oft miteinander verwandt, entweder weil sie voneinander abhängig sind oder weil sie logischerweise zur selben Gruppe gehören.

Wenn Sie beispielsweise eine Einschränkung festlegen möchten, um die Summe des Absolutwerts eines Satzes von Variablen zu begrenzen, müssen Sie zuerst Einschränkungen angeben, um die Absolutwertbeziehungen zwischen den beabsichtigten Variablen auszudrücken, und dann die Absolutwertgrenzen angeben. Manchmal müssen Sie ähnliche Einschränkungen auf eine Gruppe von Variablen anwenden, um eine bestimmte Beziehung zwischen Variablen auszudrücken.

Um diese Gruppierungen auszudrücken, können wir die abhängige Einschränkungsfunktion unserer Einschränkungsdefinitionen verwenden. Um zu sehen, wie die abhängige Einschränkungsfunktion verwendet werden kann, refaktorisieren Sie die SizeConstraint des vorherigen Problems wie folgt:

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Um nun zu testen, ob abhängige Einschränkungen automatisch implementiert werden, nehmen wir die MustHaveItemConstraint aus der Problemdefinition:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

Und führen Sie den Code erneut aus, und Sie sollten Folgendes in stdout sehen:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Sieht so aus, als wäre die MustHaveItemConstraint implementiert! Ein komplexeres Beispiel dafür, wie abhängige Beschränkungen verwendet werden können, finden Sie im Besetzungsbeispiel am Ende des Lernprogramms.

Verwalten mehrerer gewichteter Ziele

Während der Entwicklung unserer Optimierungsalgorithmen stoßen wir häufig auf einen objektiven Ausdruck, der aus mehreren Teilen besteht. Als Teil unserer Experimente können wir die Gewichtung verschiedener objektiver Komponenten ändern, um den Algorithmus auf das gewünschte Ergebnis auszurichten. Das CombinedObjective bietet eine saubere und einfache Möglichkeit, dies auszudrücken.

Angenommen, wir wollten den Algorithmus beeinflussen, um die Figur und den Apfelwein auszuwählen. Lassen Sie uns den Code aus dem vorherigen Abschnitt umgestalten, um CombinedObjective zu verwenden.

Importieren Sie zuerst die CombinedObjective -Klasse wie folgt:

 from horuslp.core import CombinedObjective

Wir können eine unabhängige Zielkomponente wie folgt implementieren:

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

Jetzt können wir das Wertziel und das Apfelwein-/Figurenziel kombinieren, indem wir ein CombinedObjective implementieren:

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

Ändern wir nun die Problemdefinition wie folgt:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

Führen Sie das Problem aus, und Sie sollten die folgende Ausgabe sehen:

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

Die Ausgabe skizziert den kombinierten Zielwert, den Wert jeder der Zielkomponenten, die Gewichtung und natürlich den Wert aller Einschränkungen.

Inkompatible Constraints finden

Bei der Entwicklung von Algorithmen stoßen wir oft auf undurchführbare Modelle. Wenn das Modell komplex ist, kann es schwierig sein, festzustellen, warum das Modell plötzlich nicht mehr durchführbar ist. HorusLP hat ein praktisches Tool, um Ihnen in diesen Fällen zu helfen.

Angenommen, wir fügen Einschränkungen hinzu und erhalten am Ende die folgenden Einschränkungen:

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Wir haben ein paar Einschränkungen hinsichtlich der Gesamtgröße der Gegenstände im Rucksack, eine Einschränkung, die erfordert, dass Apfelwein im Rucksack sein muss, und eine Reihe von inkompatiblen Einschränkungen, die erfordern, dass die Kamera sowohl im Rucksack als auch nicht im Rucksack sein muss. (Natürlich sind die Einschränkungen in einem realen Algorithmus normalerweise nicht so offensichtlich und beinhalten komplexe Variablenbeziehungen und Einschränkungen.)

Nehmen wir auch an, dass die Einschränkungen auf folgende Weise gruppiert sind, was die Erkennung möglicherweise erschwert:

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

Hier die Problemdefinition:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

Führen Sie das Problem aus, und Sie sollten das folgende Ergebnis sehen:

 KnapsackProblem: Infeasible

Ach nein! Was machen wir? Wenn wir die meisten Tools verwenden, müssen wir uns auf eine schwierige Debugging-Sitzung einlassen, in der wir die potenziell widersprüchlichen Einschränkungen nacheinander eingrenzen. Glücklicherweise verfügt HorusLP über eine Inkompatibilitätssuchfunktion, mit der Sie die inkompatiblen Einschränkungen schneller eingrenzen können. Der einfachste Weg, die Inkompatibilitätssuchfunktion zu verwenden, besteht darin, den print_results -Aufruf folgendermaßen zu ändern:

 prob.print_results(find_infeasible=True)

So einfach ist das! Führen Sie den Code aus, und jetzt sollten Sie Folgendes als Ausgabe sehen:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

Toll! Jetzt haben wir festgestellt, dass MustHaveItemConstraint nicht die Ursache der Undurchführbarkeit ist und dass das Problem auf CombinedConstraints1 und CombinedConstraints2 zurückzuführen ist.

Das gibt uns einige Informationen, aber zwischen den kombinierten Einschränkungen gibt es vier abhängige Einschränkungen. Können wir feststellen, welche der vier Einschränkungen nicht kompatibel sind? Nun ja. Ändern Sie Ihren print_results -Aufruf folgendermaßen:

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

Dadurch erweitert die Undurchführbarkeitssuche die abhängigen Einschränkungen, sodass wir ein viel genaueres Bild davon erhalten, was die Undurchführbarkeit verursacht. Führen Sie dies aus und Sie sollten die folgende Ausgabe sehen:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

Obwohl es verlockend ist, jedes Mal eine gründliche Unmachbarkeitssuche durchzuführen, kann die tiefe Unmachbarkeitssuche bei realistischen Problemen mit einer großen Anzahl von Gesamtbeschränkungen sehr ressourcenintensiv und zeitaufwändig werden. Daher ist es am besten, die grundlegende Undurchführbarkeitssuche auszuführen, um die Möglichkeit einzugrenzen, und die umfassende Undurchführbarkeitssuche auf einer kleineren Teilmenge auszuführen, nachdem einige manuelle Untersuchungen durchgeführt wurden.

Erstellen von Algorithmen aus Datendateien

Beim Erstellen von Modellen haben wir selten den Luxus, jede Einschränkung und Variable fest zu codieren. Oft muss unser Programm flexibel genug sein, um das Modell abhängig von den Eingabedaten zu ändern. Angenommen, wir wollten unser Rucksackproblem anstelle einer fest codierten Eingabe aus dem folgenden JSON erstellen:

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

Wir können dies tun, indem wir uns auf die Unterstützung der Kwargs für die „define“-Funktion verlassen, die wir für Einschränkungen und Ziele implementieren.

Ändern wir den Code des einfachen Rucksackproblems (das Problem, das wir in Abschnitt 1 des Tutorials implementiert haben). Zuerst fügen wir die JSON-Zeichenfolge in die Datei ein. Natürlich würden wir es normalerweise von einer externen Quelle lesen, aber der Einfachheit halber behalten wir alles in einer Datei. Fügen Sie Ihrem Code Folgendes hinzu:

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

Stellen wir auch sicher, dass unser Programm es analysieren kann. Fügen Sie Ihren Importanweisungen Folgendes hinzu:

 Import json

Lassen Sie uns nun unseren Variablen-Setup-Code folgendermaßen ändern:

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

Dadurch wird eine Variable für jedes der Elemente im JSON definiert und entsprechend benannt.

Ändern wir die Einschränkung und die objektiven Definitionen wie folgt:

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

Indem nach **kwargs anstelle bestimmter Variablen gefragt wird, erhält die Funktion define ein Wörterbuch, das alle Variablen mit Namen enthält. Die Einschränkungsdefinitionsfunktion kann dann auf die Variablen aus dem Wörterbuch zugreifen.

Hinweis: Bei Variablengruppen handelt es sich um ein verschachteltes Wörterbuch, bei dem die erste Ebene der Gruppenname und die zweite Ebene der Variablenname ist.

Der Rest ist ziemlich einfach:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Führen Sie dieses Programm aus und Sie sollten die folgende Ausgabe sehen:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

Benutzerdefinierte Metriken in HorusLP definieren

Manchmal erstellen wir sowohl für Debugging- als auch für Berichtszwecke benutzerdefinierte Metriken, die nicht direkt im Ziel oder als Einschränkung ausgedrückt werden. HorusLP verfügt über eine Funktion, die die Angabe benutzerdefinierter Metriken vereinfacht.

Angenommen, wir wollten verfolgen, wie viele Früchte das Modell aus unserem vorherigen Abschnitt in den Rucksack steckt. Um dies zu verfolgen, können wir eine benutzerdefinierte Metrik definieren. Beginnen wir mit dem Importieren der Metrics-Basisklasse:

 From horuslp.core import Metric

Lassen Sie uns nun die benutzerdefinierte Metrik definieren:

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

Wie Sie sehen können, sieht die definierte Schnittstelle denen der Constraint- und Objective-Komponentenklasse sehr ähnlich. Wenn Sie das Tutorial bisher befolgt haben, sollte Ihnen das ziemlich vertraut sein.

Jetzt müssen wir die Metrik zur Problemdefinition hinzufügen. Die Schnittstelle ist auch hier wieder sehr ähnlich der Constraint-Definition:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

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

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

Unten sehen Sie die Anzahl der aufgedruckten Früchte.

Durcharbeiten eines komplexeren Problems: Zwei Rucksäcke

Lassen Sie uns ein etwas komplexeres Beispiel durcharbeiten. Angenommen, wir haben statt eines einzigen Rucksacks eine Tasche und einen Koffer. Wir haben auch zwei Klassen von Objekten, langlebig und zerbrechlich. Der Koffer, der mehr Schutz bietet, kann sowohl zerbrechliche als auch langlebige Güter aufnehmen. Die Tasche hingegen kann nur langlebige Güter aufnehmen. Nehmen Sie außerdem an, dass die Daten für die Elemente im folgenden JSON angegeben sind:

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

Mal sehen, wie sich das am Modell ändert. Beginnen wir mit einem leeren Blatt, da das Modell ganz anders sein wird. Beginnen Sie mit der Einrichtung des Problems:

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

Lassen Sie uns nun die Variablen einrichten. Wir richten eine binäre Variable für jede mögliche Artikel/Container-Kombination ein.

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

Jetzt wollen wir Gewichtsbeschränkungen sowohl für den Koffer als auch für die Tasche implementieren.

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

Jetzt müssen wir eine etwas komplexere Einschränkung implementieren – die Einschränkung, die sicherstellt, dass ein Gegenstand nicht sowohl in den Koffer als auch in die Tasche wandert – das heißt, wenn die Variable „im Koffer“ 1 ist, dann die Variable „in der Tasche“. Variable muss Null sein und umgekehrt. Natürlich möchten wir sicherstellen, dass auch Fälle zugelassen werden, in denen der Gegenstand in keinem Container landet.

Um diese Einschränkung hinzuzufügen, müssen wir über alle langlebigen Gegenstände iterieren, die Variablen „im Koffer“ und die Variable „in der Tasche“ finden und behaupten, dass die Summe dieser Variablen kleiner als 1 ist.

Wir können in HorusLP ganz einfach abhängige Einschränkungen dynamisch definieren:

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

Nachdem die Einschränkungen nun definiert sind, bauen wir das Ziel. Das Ziel ist einfach die Summe aller Werte, die wir von allen Artikeln erhalten, die sich in Containern befinden. Daher:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

Lassen Sie uns auch einige benutzerdefinierte Metriken definieren, damit wir auf einen Blick sehen können, wie viel Gewicht in die Tasche und den Koffer gesteckt wurde und wie viel des Koffergewichts von Gebrauchsgütern und zerbrechlichen Gütern stammt:

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

Jetzt haben wir alle Teile fertig, lassen Sie uns das Problem instanziieren und das Modell ausführen:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Führen Sie dies aus, und Sie sollten die folgende Ausgabe in Ihrer Standardausgabe sehen:

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

So kommen Kamera, Brille, Apfel und Banane für insgesamt 15 Gewichtseinheiten in den Koffer, die Figur, das Horn und der Ledermann kommen für insgesamt 17 Gewichtseinheiten in die Tasche. Der Gesamtwert der Ware beträgt 32 Werteinheiten. Interessanterweise landete keines der Gebrauchsgüter im Koffer, höchstwahrscheinlich, weil die Tasche genug Kapazität hatte, um alle Gebrauchsgüter aufzunehmen.

Ein größeres und realistischeres Szenario: Das Personalproblem

Wenn Sie es in unserem HorusLP-Tutorial bis hierher geschafft haben, herzlichen Glückwunsch! Sie haben jetzt eine gute Vorstellung davon, wie Sie HorusLP verwenden.

Alle Beispiele, an denen wir bisher gearbeitet haben, waren jedoch Permutationen des Rucksackproblems, und einige der Anforderungen und Parameter sind etwas unrealistisch. Lassen Sie uns gemeinsam ein weiteres Problem durcharbeiten, um zu sehen, wie HorusLP ein realistischeres Problem lösen kann. Wir werden das Personalproblem lösen, das in der zweiten Hälfte meines vorherigen Toptal-Artikels beschrieben wurde.

Aus Zeitgründen werden wir uns direkt für die endgültige Version des Modells (mit persönlichen Konflikten, Arbeitsvorschriften und Zulagen für Zeitarbeiter) entscheiden, aber die Implementierung des anfänglich einfacheren Modells ist auch auf GitHub verfügbar.

Beginnen wir also mit der Einrichtung des Problems:

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Lassen Sie uns nun die Variablen definieren, die in diesem Fall binäre Variablen wären, die bestimmen, ob ein Arbeiter seine Schicht arbeiten soll, und ganzzahlige Variablen, die bestimmen, wie viele Dothrakis wir für jede Schicht einstellen:

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

Lassen Sie uns nun die Einschränkung implementieren, die von uns verlangt, für jede Schicht ausreichend Personal zu haben:

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

Jetzt müssen wir die Einschränkungen implementieren, die bestimmte Personen daran hindern, miteinander zu arbeiten:

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

Einpacken

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!