Gemischt-ganzzahlige Programmierung: Ein Leitfaden zur computergestützten Entscheidungsfindung

Operations Research, die Wissenschaft der Verwendung von Computern, um optimale Entscheidungen zu treffen, wurde in vielen Bereichen der Software eingesetzt und angewendet. Um nur einige Beispiele zu nennen: Logistikunternehmen verwenden es, um die optimale Route von Punkt A nach Punkt B zu bestimmen, Energieunternehmen verwenden es, um Stromerzeugungspläne zu bestimmen, und Fertigungsunternehmen verwenden es, um optimale Personalmuster für ihre Fabriken zu finden.

Heute werden wir die Leistungsfähigkeit von Operations Research untersuchen, indem wir ein hypothetisches Problem durchgehen. Insbesondere werden wir die gemischt-ganzzahlige Programmierung (MIP) verwenden, um das optimale Personalbesetzungsmuster für eine hypothetische Fabrik zu bestimmen.

Operations Research-Algorithmen

Bevor wir uns mit unserem Beispielproblem befassen, ist es hilfreich, einige grundlegende Konzepte des Operations Research durchzugehen und ein wenig über die Tools zu erfahren, die wir heute verwenden werden.

Lineare Programmieralgorithmen

Lineare Programmierung ist eine Operations-Research-Technik, die verwendet wird, um das beste Ergebnis in einem mathematischen Modell zu bestimmen, bei dem das Ziel und die Einschränkungen als ein System linearer Gleichungen ausgedrückt werden. Ein beispielhaftes lineares Programmiermodell könnte so aussehen:

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

In unserem sehr einfachen Beispiel können wir sehen, dass das optimale Ergebnis 5 ist, mit a = 2 und b = 3. Obwohl dies ein ziemlich triviales Beispiel ist, können Sie sich wahrscheinlich ein lineares Programmiermodell vorstellen, das Tausende von Variablen und Hunderte von Einschränkungen verwendet .

Ein gutes Beispiel könnte ein Investment-Portfolio-Problem sein, bei dem Sie in Pseudo-Code so etwas wie das Folgende erhalten könnten:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

Was ziemlich komplex und schwer von Hand oder durch Versuch und Irrtum zu lösen wäre. Operations Research-Software verwendet mehrere Algorithmen, um diese Probleme schnell zu lösen. Wenn Sie sich für die zugrunde liegenden Algorithmen interessieren, empfehle ich Ihnen, sich hier über die Simplex-Methode und hier über die Interior-Point-Methode zu informieren.

Ganzzahlige Programmieralgorithmen

Die ganzzahlige Programmierung ist wie die lineare Programmierung mit der zusätzlichen Erlaubnis, dass einige oder alle Variablen ganzzahlige Werte sein können. Auch wenn dies auf den ersten Blick nicht wie eine große Verbesserung erscheinen mag, ermöglicht es uns, viele Probleme zu lösen, die mit linearer Programmierung allein ungelöst geblieben wären.

Eines dieser Probleme ist das Rucksackproblem, bei dem wir eine Reihe von Gegenständen mit zugewiesenen Werten und Gewichten erhalten und gebeten werden, die höchstwertige Kombination von Gegenständen zu finden, die in unseren Rucksack passt. Ein lineares Programmiermodell wird dies nicht lösen können, da es keine Möglichkeit gibt, die Idee auszudrücken, dass Sie entweder einen Gegenstand in Ihren Rucksack stecken können oder nicht, aber Sie können nicht einen Teil eines Gegenstands in Ihren Rucksack stecken – jede Variable ist eine Stetigkeit Variable!

Ein beispielhaftes Rucksackproblem könnte die folgenden Parameter haben:

Und das MIP-Modell sieht folgendermaßen aus:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

Die optimale Lösung ist in diesem Fall a=0, b=1, c=0, d=1, wobei der Wert des Gesamtelements 17 ist.

Das Problem, das wir heute lösen werden, erfordert auch ganzzahlige Programmierung, da ein Mitarbeiter in einer Fabrik entweder für eine Schicht eingeplant werden kann oder nicht – der Einfachheit halber können Sie einen Mitarbeiter in dieser Fabrik nicht für 2/3 einer Schicht einplanen.

Um eine ganzzahlige Programmierung zu ermöglichen, werden mehrere mathematische Algorithmen verwendet. Wenn Sie sich für die zugrunde liegenden Algorithmen interessieren, empfehle ich Ihnen, den Schnittebenen-Algorithmus und den Branch-and-Bound-Algorithmus hier zu studieren.

Beispielproblem: Zeitplanung

Problembeschreibung

Heute werden wir das Problem der Personalbesetzung einer Fabrik untersuchen. Als Werksleitung möchten wir die Arbeitskosten minimieren, aber wir möchten sicherstellen, dass jede Schicht ausreichend abgedeckt ist, um den Produktionsbedarf zu decken.

Angenommen, wir haben fünf Schichten mit den folgenden Personalanforderungen:

Angenommen, wir haben die folgenden Worker:

Um das Problem einfach zu halten, nehmen wir für den Moment an, dass es nur um Verfügbarkeit und Kosten geht.

Unsere Werkzeuge

Für das heutige Problem verwenden wir eine Open-Source-Branch-and-Cut-Software namens CBC. Wir werden mit PuLP, einer beliebten Modellierungsbibliothek für Operations Research für Python, mit dieser Software kommunizieren. Informationen dazu finden Sie hier.

PuLP ermöglicht es uns, MIP-Modelle auf sehr pythonische Weise zu erstellen und lässt sich gut in bestehenden Python-Code integrieren. Dies ist sehr nützlich, da einige der beliebtesten Datenmanipulations- und Analysetools in Python geschrieben sind und die meisten kommerziellen Operations Research-Systeme vor und nach der Optimierung eine umfangreiche Datenverarbeitung erfordern.

Um die Einfachheit und Eleganz von PuLP zu demonstrieren, hier ist das Rucksackproblem von früher und in PuLP gelöst:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

Führen Sie dies aus, und Sie sollten die Ausgabe erhalten:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Nun zu unserem Planungsproblem!

Codierung unserer Lösung

Die Codierung unserer Lösung ist ziemlich einfach. Zuerst wollen wir unsere Daten definieren:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] 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 } }

Als nächstes wollen wir das Modell definieren:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

Und jetzt bitten wir es nur noch, die Ergebnisse zu lösen und auszudrucken!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

Sobald Sie den Code ausführen, sollten Sie die folgenden Ausgaben sehen:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Erhöhen Sie die Schwierigkeit ein wenig: Zusätzliche Einschränkungen

Obwohl das vorherige Modell interessant und nützlich war, demonstriert es die Leistungsfähigkeit der gemischt-ganzzahligen Programmierung nicht vollständig. Wir könnten auch einfach eine for -Schleife schreiben, um die billigsten x Arbeiter für jede Schicht zu finden, wobei x die Anzahl der Arbeiter ist, die für eine Schicht benötigt werden. Um zu demonstrieren, wie MIP verwendet werden kann, um ein Problem zu lösen, das auf zwingende Weise schwierig zu lösen wäre, wollen wir untersuchen, was passieren würde, wenn wir ein paar zusätzliche Einschränkungen hinzufügen würden.

Zusätzliche Einschränkungen

Angenommen, aufgrund neuer arbeitsrechtlicher Vorschriften können keine Arbeiter mehr als 2 Schichten zugewiesen werden. Um der erhöhten Arbeit Rechnung zu tragen, haben wir die Hilfe der Dothraki Staffing Group rekrutiert, die bis zu 10 Dothraki-Arbeiter für jede Schicht zu einem Preis von 40 USD pro Schicht bereitstellen wird.

Nehmen wir außerdem an, dass Cersei und Jaime aufgrund einiger anhaltender zwischenmenschlicher Konflikte außerhalb unserer Fabrik nicht in der Lage sind, neben Daenerys oder Jon in Schichten zu arbeiten. Außerdem können Jaime und Cersei keine Schichten zusammen arbeiten. Schließlich kann Arya, die besonders komplexe zwischenmenschliche Beziehungen hat, nicht in derselben Schicht mit Jaime, Cersei oder Melisandre arbeiten.

Das Hinzufügen dieser beiden neuen Beschränkungen und Ressourcen macht das Problem keineswegs unlösbar durch zwingende Mittel, aber es macht die Lösung viel schwieriger, da man die Opportunitätskosten der Einplanung eines Arbeiters für eine bestimmte Schicht berücksichtigen muss.

Lösung

Bei der gemischt-ganzzahligen Programmierung ist es jedoch viel einfacher. Wir müssen unseren Code einfach wie folgt ändern:

Definieren Sie die Sperrliste und einige Einschränkungen:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Füllen Sie Variablen zum Implementieren der Einschränkungen für das Verbot und die maximale Schicht:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Fügen Sie die Dothraki-Variablen hinzu:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Wir benötigen auch eine leicht modifizierte Schleife für die Berechnung der Schicht- und Sperranforderungen:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

Und schließlich, um die Ergebnisse auszudrucken:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

Und wir sollten startklar sein. Führen Sie den Code aus und Sie sollten die Ausgabe wie folgt sehen:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

Und da haben wir es, ein Ergebnis, das die Liste der verbotenen Arbeiter respektiert, Arbeitsvorschriften befolgt und Dothraki-Arbeiter vernünftig einsetzt.

Fazit

Heute haben wir die Verwendung von gemischt-ganzzahliger Programmierung untersucht, um bessere Entscheidungen zu treffen. Wir diskutierten die zugrunde liegenden Algorithmen und Techniken, die in der Betriebsforschung verwendet werden, und betrachteten ein Beispielproblem, das repräsentativ dafür ist, wie gemischt-ganzzahlige Programmierung in der realen Welt verwendet wird.

Ich hoffe, dieser Artikel hat Sie dazu inspiriert, mehr über Operations Research zu erfahren und darüber nachzudenken, wie diese Technologie auf Ihre Projekte angewendet werden kann. Wir haben nur die Spitze des Eisbergs gesehen, wenn es um die spannende Welt der Optimierungsalgorithmen und des Operations Research geht.

Den gesamten Code zu diesem Artikel finden Sie auf GitHub. Wenn Sie mehr diskutieren möchten, teilen Sie unten Ihre Kommentare!