Operačný výskum a konvexná optimalizácia je oblasť aplikovanej matematiky, ktorá si v priebehu rokov našla široké komerčné využitie. Keď sa výpočtový výkon stal dostupnejším a široko dostupnejším, začali vedci vytvárať čoraz sofistikovanejšie optimalizačné algoritmy, ktoré im pomáhajú robiť lepšie rozhodnutia. Aplikácie založené na operačnom výskume dnes napájajú všetko od smerovania v globálnej logistike po plynulej výroby elektriny v energetickom priemysle.

Pretože sa zložitosť základnej technológie zhoršovala, bola vytvorená nová sada nástrojov, ktorá pomáha výskumníkom a vývojárom produktívnejšie pracovať. Tieto nástroje, ako sú AMPL, CVXPY a PuLP, umožňujú vývojárom rýchlo definovať, zostaviť a spustiť optimalizačné algoritmy a prepojiť ich so širokou škálou riešiteľov.

Avšak zatiaľ čo optimalizačné technológie a obchodné potreby neustále rastú v sofistikovanosti, väčšina z týchto nástrojov zostala viac-menej rovnaká a nevyvíjali sa dostatočne rýchlo, aby vyhovovali potrebám odvetvia. Výsledkom je, že vývoj, správa, ladenie a ladenie týchto algoritmov často vyžaduje veľké množstvo kognitívnych réžií, najmä v rýchlo sa rozvíjajúcom obchodnom prostredí.

Dnes by som rád predstavil HorusLP , do Knižnica optimalizácie Pythonu ktorý pomáha s architektúrou pracovných tokov vývoja algoritmov. Povieme si o problémoch, ktoré je nástroj určený na riešenie, potom poskytneme rýchly prehľad o knižnici Python a zostavíme niekoľko príkladov optimalizačných algoritmov.

Problémy, ktorým čelia vývojári optimalizačného algoritmu

Jedným z trvalých problémov, ktorým väčšina vývojárov čelí, je rovnováha medzi vytvorením udržovateľného, ​​efektívneho idiomatického softvéru a dodaním produktu v časových obmedzeniach projektu. Či už pracujete na aplikácii založenej na prehliadači, webovom rozhraní API alebo mikroslužbe na overenie totožnosti používateľa, medzi „správnym“ spôsobom a „rýchlym“ spôsobom dosiahnutia vašich cieľov často dôjde k kompromisu. Tento inherentný kompromis sa stáva výraznejším s rastúcou zložitosťou produktu.

Vo väčšine disciplín môže vývojár tento problém zmierniť výberom rámca alebo knižnice, ktorá pomáha s architektúrou. Mnoho vývojárov v prostredí front-end orientovaných na web volí React alebo Angular; vo svete vývoja API si môžu softvéroví inžinieri okrem iných zvoliť Django, ASP.NET MVC alebo Play. Pokiaľ však ide o vývojára skromných optimalizačných algoritmov, existuje len veľmi málo nástrojov architektúry, ktoré by pomohli zvládnuť architektonickú zložitosť. Vývojár má možnosť spravovať premenné, obmedzenia a rôzne ciele sám. A čo viac, algoritmy operačného výskumu sú vo všeobecnosti ťažko preskúmateľné, čím sa problém prehlbuje.

Hlavným účelom HorusLP je poskytnúť architektonický rámec pre vývoj optimalizačných algoritmov. Poskytnutím štruktúrnej konzistencie rámec uľahčuje organizáciu a umožňuje vývojárom sústrediť sa na to, čo im ide najlepšie: na tvorbu algoritmov.

Typické výzvy pre optimalizačný pracovný postup

Pri vývoji algoritmov OR existuje niekoľko hlavných zdrojov zložitosti:

Zložitosť z premenných

• Aby bolo možné vyhovieť ďalším obchodným požiadavkám, musia byť často pridané premenné a neexistuje jednoduchý spôsob, ako ich sledovať na použitie v definíciách modelov a v neskorších správach.
• Súvisiace premenné je potrebné zoskupiť a sledovať a neexistuje zrejmý spôsob ich správy.

Zložitosť z obmedzení

• Je potrebné pridať a odstrániť obmedzenia, aby sa podporili rôzne scenáre a vykonalo ladenie, ale neexistuje zrejmé miesto na pridanie alebo odstránenie obmedzení.
• Obmedzenia často navzájom súvisia / závisia a neexistuje žiadny prirodzený spôsob vyjadrenia ich vzťahov.

Zložitosť z cieľov

• Objektívne výrazy sa môžu stať nepraktickými, ak majú viac zložiek. To sa môže zhoršiť, ak sa vážia rôzne komponenty a váhy je potrebné upraviť na základe obchodných požiadaviek.

Zložitosť z ladenia

• Počas vývoja nie je ľahký spôsob, ako vidieť výsledky modelu. Ak chce vývojár vidieť výsledky, musí explicitne vytlačiť nové premenné a hodnoty obmedzení. To vedie k duplicitnému kódu a pomalšiemu vývoju.
• Keď pridanie obmedzenia spôsobí, že model sa stane nerealizovateľným, nemusí byť zrejmé, prečo toto obmedzenie spôsobilo, že model sa stal nerealizovateľným. Vývojári zvyčajne musia odstrániť rôzne obmedzenia a hľadať nekompatibilitu metódou pokus-omyl

Spoločnosť HorusLP dúfa, že tieto výzvy bude možné lepšie zvládnuť poskytnutím štruktúry, nástrojov a osvedčených postupov na zlepšenie produktivity vývojárov a udržiavateľnosti produktu.

Výukový program HorusLP: Optimalizačný algoritmus a prehľad API

Bez ďalších okolkov sa ponoríme a uvidíme, čo pre vás knižnica HorusLP môže urobiť!

Pretože HorusLP je založený na Pythone a PuLP, budeme ich chcieť nainštalovať pomocou pipu. V príkazovom riadku spustite nasledovné:

Pip install horuslp pulp

Po dokončení inštalácie poďme otvoriť súbor Python. Budeme realizovať problém s batohom z môjho predchádzajúci článok o operačnom výskume .

Knižnica HorusLP má veľmi jednoduché deklaratívne API a veľmi malý štandardný štítok. Začnime importom potrebných tried a premenných:

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

Po importovaní všetkých premenných definujme premenné, ktoré pre tento problém potrebujeme. Robíme to tak, že vytvoríme podtriedu správcu premenných a naplníme ju binárnymi premennými:

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

Teraz, keď sú premenné definované, definujme obmedzenia. Obmedzenia vytvárame podtriedou hlavnej triedy obmedzení a implementáciou jej funkcie „definovať“.

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

Vo funkcii define môžete požiadať o požadované premenné podľa názvu. Rámec vyhľadá premennú v správcovi premenných a odovzdá ju do funkcie define.

Po zavedení obmedzenia môžeme cieľ implementovať. Pretože ide o jednoduchý cieľ, použijeme ObjectiveComponent:

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

Funkcia define má veľmi podobné nastavenie ako funkcia definovania triedy obmedzení. Namiesto vrátenia obmedzujúceho výrazu však vrátime afinný výraz.

Teraz, keď sú definované premenné, obmedzenia a ciele, definujme model:

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

Na zostavenie modelu vytvoríme triedu, ktorá je podtriedou triedy Problém, a zadáme premenné, ciele, obmedzenia a zmysel. Po zadaní problému môžeme problém vyriešiť:

prob = KnapsackProblem() prob.solve()

Po vyriešení môžeme výsledky vytlačiť pomocou triedy problémov print_results funkcia. K hodnote konkrétnych premenných môžeme tiež získať prístup pomocou znakov result_variables trieda.

prob.print_results() print(prob.result_variables)

Spustite skript a mal by sa zobraziť nasledujúci výstup:

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}

Mali by ste vidieť stav problému, konečnú hodnotu premenných, objektívnu hodnotu a hodnotu výrazu obmedzenia. Výsledné hodnoty premenných vidíme aj ako slovník.

A máme to, náš prvý problém s HorusLP v asi 35 riadkoch!

V nasledujúcich príkladoch preskúmame niektoré sofistikovanejšie funkcie knižnice HorusLP.

Používanie skupín premenných

Premenné niekedy súvisia a patria do logickej skupiny. V prípade problému s batohom môžu byť všetky premenné umiestnené do skupiny objektov. Môžeme refaktorovať kód, aby sme mohli použiť skupinu premenných. Uistite sa, že ste uložili kód z predchádzajúcej časti, pretože na neho budeme odkazovať v nasledujúcich tutoriáloch!

Zmeňte príkazy na import takto:

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

Teraz tiež musíme zmeniť deklarácie premenných batohov takto:

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

Prvým argumentom je názov skupiny premenných, druhým premenným zoznam mien premenných v rámci tejto skupiny.

Teraz musíme zmeniť obmedzenie a objektívne definície. Namiesto toho, aby sme sa pýtali na jednotlivé mená, urobíme to ako pre skupinu premenných, ktorá sa odovzdá ako slovník, kde kľúče sú názvy a hodnoty sú premenné. Zmeňte obmedzenie a objektívne definície takto:

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']

Teraz môžeme použiť rovnakú definíciu problému a spúšťať príkazy:

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

Mali by ste to vidieť vo svojom výstupe:

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}}

Správa viacerých obmedzení

Modely s jediným obmedzením sú pomerne zriedkavé. Pri práci s viacerými obmedzeniami je dobré mať všetky obmedzenia na jednom mieste, aby ich bolo možné ľahko sledovať a spravovať. HorusLP to robí prirodzeným.

Predpokladajme napríklad, že sme chceli zistiť, ako by sa zmenili výsledky, ak by sme model prinútili pridať k nášmu batohu fotoaparát. Implementovali by sme ďalšie obmedzenie a pridali by sme ho do našej definície problému.

Vráťte sa k modelu, ktorý sme implementovali v prvom návode. Pridajte nasledujúce obmedzenie:

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

Ak chcete pridať obmedzenie do modelu, jednoducho ho musíme pridať do definície problému takto:

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

Spustite problém a mal by sa zobraziť nasledujúci výstup:

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

Mali by ste vidieť nové obmedzenie, ktoré sa tlačí v štandardnom výstupe, a zmenené hodnoty optimálnych premenných.

Správa závislých obmedzení a skupín obmedzení

Obmedzenia navzájom často súvisia buď preto, že sú na sebe navzájom závislé, alebo preto, že logicky patria do rovnakej skupiny.

Napríklad, ak chcete nastaviť obmedzenie na obmedzenie súčtu absolútnej hodnoty množiny premenných, musíte najskôr určiť obmedzenia na vyjadrenie vzťahov absolútnej hodnoty medzi zamýšľanými premennými a potom určiť limity absolútnej hodnoty. Niekedy musíte na skupinu premenných uplatniť podobné obmedzenia, aby ste vyjadrili konkrétny vzťah medzi premennými.

Na vyjadrenie týchto zoskupení môžeme použiť funkciu závislých obmedzení v našich definíciách obmedzení. Ak chcete zistiť, ako je možné použiť funkciu závislého obmedzenia, urobte refaktor pomocou SizeConstraint predchádzajúceho problému takto:

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

A teraz na otestovanie, že závislé obmedzenia sa implementujú automaticky, si vezmime MustHaveItemConstraint z definície problému:

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

A znova spustite kód a v štandardnom výstupe by ste mali vidieť toto:

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

Vyzerá to ako MustHaveItemConstraint je implementovaný! Komplexnejší príklad použitia závislých obmedzení nájdete v príklade personálneho zabezpečenia na konci tutoriálu.

Správa viacerých vážených cieľov

Počas vývoja našich optimalizačných algoritmov sa často stretneme s objektívnym vyjadrením zloženým z viacerých častí. V rámci nášho experimentovania môžeme zmeniť váženie rôznych objektívnych zložiek tak, aby sa algoritmus posunul k požadovanému výsledku. The CombinedObjective poskytuje čistý a jednoduchý spôsob, ako to vyjadriť.

Predpokladajme, že sme chceli zaujať algoritmus, aby sme vybrali figúrku a jablkový mušt. Opätovne upravme kód z predchádzajúcej časti na použitie CombinedObjective.

Najskôr importujte CombinedObjective trieda takto:

from horuslp.core import CombinedObjective

Môžeme implementovať nezávislý objektívny komponent takto:

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

Teraz môžeme skombinovať hodnotový cieľ a objekt cideru / figuríny implementáciou CombinedObjective:

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

Teraz poďme zmeniť definíciu problému takto:

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

Spustite problém a mal by sa zobraziť nasledujúci výstup:

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

Výstup načrtne kombinovanú objektívnu hodnotu, hodnotu každej zo zložiek objektívu, váhu a samozrejme hodnotu všetkých obmedzení.

Hľadanie nekompatibilných obmedzení

Pri vývoji algoritmov často narazíme na nerealizovateľné modely. Ak je model zložitý, môže byť náročné určiť, prečo je tento model zrazu nemožné. HorusLP má užitočný nástroj, ktorý vám v týchto prípadoch pomôže.

Predpokladajme, že sme pridali obmedzenia a skončili sme s nasledujúcou sadou obmedzení:

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 = 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera>= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Máme niekoľko obmedzení týkajúcich sa celkovej veľkosti predmetov v batohu, obmedzenia vyžadujúce, aby v batohu musel byť cider, a nekompatibilná sada obmedzení, ktoré vyžadujú, aby bola kamera v batohu aj mimo neho. (Samozrejme, v algoritme skutočného sveta obmedzenia zvyčajne nie sú také zrejmé a zahŕňajú zložité variabilné vzťahy a obmedzenia.)

Predpokladajme tiež, že obmedzenia sú zoskupené nasledujúcim spôsobom, ktorý by pravdepodobne sťažil detekciu:

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

Tu je definícia problému:

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

Spustite problém a mal by sa zobraziť nasledujúci výsledok:

KnapsackProblem: Infeasible

Ale nie! Čo urobíme? Ak používame väčšinu nástrojov, musíme sa pustiť do náročnej relácie ladenia, kde postupne zúžime potenciálne konfliktné obmedzenia. Našťastie má HorusLP funkciu vyhľadávania nekompatibility, ktorá vám pomôže rýchlejšie zúžiť nekompatibilné obmedzenia. Najjednoduchší spôsob, ako použiť funkciu hľadania nekompatibility, je zmeniť print_results volať teda:

prob.print_results(find_infeasible=True)

Také jednoduché! Spustite kód a teraz by sa mal ako výstup zobraziť nasledujúci text:

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

Skvelé! Teraz sme zistili, že MustHaveItemConstraint nie je príčinou nerealizovateľnosti a že problém je spôsobený CombinedConstraints1 a CombinedConstraints2.

To nám dáva nejaké informácie, ale medzi kombinovanými obmedzeniami existujú štyri závislé obmedzenia. Môžeme určiť, ktoré zo štyroch obmedzení sú nezlučiteľné? No áno. Upravte svoje print_results volať teda:

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

Toto umožní, aby sa pri prehľade nerealizovateľnosti rozšírili závislé obmedzenia, aby sme získali oveľa podrobnejší obraz o tom, čo je nerealizovateľné. Spustite to a mal by sa zobraziť nasledujúci výstup:

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

Aj keď je lákavé spustiť hĺbkové vyhľadávanie infeasibility zakaždým, pre realistické problémy s veľkým počtom celkových obmedzení môže byť hlboké vyhľadávanie infeasibility veľmi náročné na zdroje a časovo náročné. Preto je najlepšie vykonať základné vyhľadávanie infeasibility, aby ste zúžili možnosti, a vykonať hĺbkové vyhľadávanie infeasibility na menšej podmnožine po vykonaní manuálneho vyšetrenia.

Tvorba algoritmov z dátových súborov

Pri stavbe modelov máme zriedka luxus natvrdo kódovať všetky obmedzenia a premenné. Náš program musí byť často dostatočne flexibilný, aby zmenil model v závislosti od vstupných údajov. Predpokladajme, že namiesto pevne zakódovaného vstupu sme chceli vytvoriť náš problém s batohom z nasledujúceho 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 }

Môžeme to urobiť tak, že sa spoliehame na to, že kwargs podporí funkciu „definovania“, ktorú implementujeme pre obmedzenia a ciele.

Poďme upraviť kód z jednoduchého problému s batohom (problém, ktorý sme implementovali v časti 1 tutoriálu). Najskôr vložíme reťazec JSON do súboru. Normálne by sme to samozrejme čítali z externého zdroja, ale pre jednoduchosť si všetko uložme do jedného súboru. Pridajte do svojho kódu toto:

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 } '''

Zabezpečme tiež, aby to náš program dokázal analyzovať. Do výpisov z importu pridajte toto:

Import json

Poďme teda upraviť náš nastavovací kód premennej:

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

Toto definuje premennú pre každú z položiek v JSON a primerane ju pomenuje.

Zmeňme obmedzenie a objektívne definície takto:

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)

Požiadaním o **kwargs namiesto konkrétnych premenných sa použije znak define funkcia získa slovník obsahujúci všetky premenné podľa názvu. Funkcia definície obmedzenia potom môže pristupovať k premenným zo slovníka.

Poznámka: Pre skupiny premenných to bude vnorený slovník, kde prvá úroveň je názov skupiny a druhá úroveň je názov premennej.

Zvyšok je celkom priamy:

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

Spustite tento program a mal by sa zobraziť nasledujúci výstup:

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

Definovanie vlastných metrík v HorusLP

Niekedy budeme na účely ladenia aj vytvárania prehľadov vytvárať vlastné metriky, ktoré nie sú vyjadrené priamo v cieli alebo ako obmedzenie. HorusLP má funkciu, ktorá uľahčuje zadávanie vlastných metrík.

Predpokladajme, že sme chceli sledovať, koľko ovocia vložil model z našej predchádzajúcej časti do batohu. Aby sme to mohli sledovať, môžeme definovať vlastnú metriku. Začnime importom základnej triedy Metriky:

From horuslp.core import Metric

Teraz si definujeme vlastnú metriku:

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

Ako vidíte, definované rozhranie vyzerá veľmi podobne ako rozhranie triedy obmedzení a objektívnych komponentov. Ak ste doteraz postupovali podľa tohto návodu, malo by vám to byť celkom známe.

Teraz musíme do definície problému pridať metriku. Rozhranie je tu opäť veľmi podobné definícii obmedzenia:

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

Spustite to a mal by sa zobraziť nasledujúci výstup:

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

Počet plodov môžete vidieť dole.

Prepracovanie zložitejšieho problému: dva batohy

Poďme si predstaviť trochu zložitejší príklad. Predpokladajme, že namiesto jediného batohu máme tašku a kufor. Máme tiež dve triedy predmetov, odolné a krehké. Kufor, ktorý je viac ochranný, pojme krehký aj odolný tovar. Do tašky sa naopak zmestia iba predmety dlhodobej spotreby. Predpokladajme tiež, že údaje o položkách sú uvedené v nasledujúcom 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 }

Pozrime sa, ako to zmení model. Začnime prázdnou tabuľkou, pretože model bude úplne iný. Začnite s nastavením problému:

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)

Teraz nastavíme premenné. Nastavíme binárnu premennú pre každú možnú kombináciu položky / kontajnera.

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']]) ]

Teraz chceme zaviesť obmedzenia hmotnosti pre kufor aj tašku.

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']

Teraz musíme implementovať o niečo zložitejšie obmedzenie - obmedzenie, ktoré zaisťuje, aby položka nešla do kufra aj do vaku - to znamená, ak je premenná „v kufri“ 1, potom „vo vrecku“ premenná musí byť nula a naopak. Samozrejme sa chceme uistiť, že povoľujeme prípady, keď položka končí rovnako v jednom z kontajnerov.

Aby sme toto obmedzenie pridali, musíme iterovať všetky trvanlivé predmety, nájsť premenné „v kufri“ a „v taške“ a tvrdiť, že súčet týchto premenných je menší ako 1.

V HorusLP môžeme pomerne ľahko dynamicky definovať závislé obmedzenia:

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

Teraz, keď sú definované obmedzenia, zostavme cieľ. Cieľom je jednoduchý súčet všetkých hodnôt, ktoré dostaneme zo všetkých položiek, ktoré sú v kontajneroch. Takto:

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

Definujme tiež niektoré vlastné metriky, aby sme na prvý pohľad videli, aká veľká váha bola vložená do tašky a kufra, a tiež to, koľko z hmotnosti kufra pochádzalo z tovaru dlhodobej spotreby a krehkého tovaru:

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']])

Teraz máme všetky kúsky hotové, urobme inštanciu problému a spustime model:

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

Spustite to a vo vašom štandardnom výstupe by sa mal zobraziť nasledujúci výstup:

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

Fotoaparát, okuliare, jablko a banán teda idú do kufra na celkom 15 váhových jednotiek, figúrka, klaksón a kožiar do tašky na celkom 17 váh. Celková hodnota tovaru vychádza na 32 hodnotových jednotiek. Je zaujímavé, že žiadny z predmetov dlhodobej spotreby neskončil v kufri, pravdepodobne preto, že taška mala dostatočnú kapacitu na uloženie všetkých predmetov dlhodobej spotreby.

Väčší a realistickejší scenár: Problém s personálnym obsadením

Ak ste sa v našom výučbovom programe HorusLP dostali až sem, gratulujeme! Teraz máte dobrý nápad, ako používať HorusLP.

Všetky príklady, na ktorých sme pracovali, však boli doteraz permutáciami problému s batohom a niektoré požiadavky a parametre sú trochu nereálne. Poďme sa spoločne venovať ešte jednému problému, aby sme zistili, ako môže HorusLP vyriešiť realistickejší problém. Preberieme problém s personálnym obsadením načrtnutý v druhej polovici roku môj predchádzajúci článok o ApeeScape .

V záujme času prejdeme priamo k finálnej verzii modelu (s osobnými konfliktmi, pracovnými predpismi a dočasnými pracovnými dávkami), ale implementácia počiatočného jednoduchšieho modelu je k dispozícii aj na GitHub.

Začnime teda nastavením problému:

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

Teraz definujme premenné, ktoré by v tomto prípade boli binárne premenné určujúce, či má pracovník pracovať na zmeny, a celočíselné premenné určujúce, koľko dothrakisov si najeme na každú zmenu:

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))

Teraz implementujme obmedzenie, ktoré od nás vyžaduje, aby sme mali dostatok personálu pre každú zmenu:

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

Teraz musíme implementovať obmedzenia, ktoré bránia konkrétnym ľuďom vo vzájomnej spolupráci:

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

A nakoniec obmedzenie pracovných noriem. Tú implementujeme trochu odlišne na demonštračné účely:

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)

A teraz si stanovme ciele. Náklady na dothraki a bežné náklady na zamestnancov sa počítajú veľmi rozdielne, preto ich dáme do samostatných objektívnych zložiek:

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) ]

A teraz môžeme definovať a spustiť problém:

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()

Spustite skript a mali by ste vidieť toto:

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

Ak to porovnáte s problémom, ktorý sme implementovali v predchádzajúcom návode, mali by ste vidieť, že sa výsledky zhodujú.

Balenie

Gratulujeme k absolvovaniu nášho prvého tutoriálu HorusLP! Teraz ste kompetentným praktikom spoločnosti HorusLP.

Dúfam, že vás tento článok presvedčil o výhodách architektúry vášho Modely MIP , a že vo svojich nadchádzajúcich projektoch využijete HorusLP. Zdrojový kód HorusLP a kód všetkých tutoriálov nájdete na GitHub . Na GitHub veľmi skoro pribudne ďalšia dokumentácia HorusLP a stránka s návodom.

Pretože HorusLP je pomerne nový projekt, radi by sme sa s vami spojili a začlenili vaše podnety. Ak máte akékoľvek otázky, pripomienky alebo návrhy, napíšte mi prosím prostredníctvom ApeeScape alebo pomocou kontaktných informácií, ktoré nájdete na GitHub. Dúfam, že sa čim skor ozveš!

Pochopenie základov

Čo je HorusLP?

HorusLP je optimalizačná knižnica v Pythone, ktorá vám pomôže pri navrhovaní pracovných postupov vývoja algoritmov. Má jednoduché, deklaratívne API a veľmi malý štandard.

Aký je problém Knapsnack?

Knapsnackov problém je optimalizačný problém zameraný na kombinatorickú optimalizáciu. Pri predložení súboru položiek s rôznymi váhami a hodnotami je cieľom „toľko“ z nich „zapadnúť“ do batohu, ktorý je obmedzený a nepodlieha zmenám.