Arhitectarea algoritmilor de optimizare cu HorusLP

Cercetarea operațională și optimizarea convexă este un domeniu al matematicii aplicate care a găsit aplicații comerciale ample de-a lungul anilor. Pe măsură ce puterea de calcul a devenit mai accesibilă și disponibilă pe scară largă, cercetătorii au început să construiască algoritmi de optimizare din ce în ce mai sofisticați pentru a-i ajuta să ia decizii mai bune. Astăzi, aplicațiile bazate pe cercetarea operațională alimentează totul, de la rutare în logistica globală până la netezirea producției de electricitate în industria energetică.

Pe măsură ce tehnologia de bază a crescut în complexitate, a fost creat un nou set de instrumente pentru a ajuta cercetătorii și dezvoltatorii să lucreze mai productiv. Aceste instrumente, cum ar fi AMPL, CVXPY și PuLP, permit dezvoltatorilor să definească, să construiască și să ruleze rapid algoritmi de optimizare și să interfațeze cu o mare varietate de soluții.

Cu toate acestea, în timp ce tehnologiile de optimizare și nevoile de afaceri continuă să crească în sofisticare, majoritatea acestor instrumente au rămas mai mult sau mai puțin aceleași și nu au evoluat suficient de repede pentru a satisface nevoile industriei. Ca rezultat, dezvoltarea, gestionarea, depanarea și reglarea acestor algoritmi necesită adesea o cantitate mare de cheltuieli cognitive, mai ales într-un mediu de afaceri în mișcare rapidă.

Astăzi, aș dori să vă prezint HorusLP, o bibliotecă de optimizare Python care ajută la arhitectura fluxurilor de lucru de dezvoltare a algoritmilor. Vom vorbi despre problemele pe care instrumentul este proiectat să le rezolve, apoi vom oferi o privire de ansamblu rapidă asupra bibliotecii Python și vom construi câteva exemple de algoritmi de optimizare.

Probleme cu care se confruntă dezvoltatorii de algoritmi de optimizare

Una dintre problemele perene cu care se confruntă majoritatea dezvoltatorilor este echilibrul dintre construirea unui software ușor de întreținut, eficient, idiomatic și livrarea unui produs în limitele de timp ale proiectului. Indiferent dacă lucrați la o aplicație bazată pe browser, un API web sau un microserviciu de autentificare a utilizatorului, există adesea un compromis între modul „corect” și modul „rapid” de a vă îndeplini obiectivele. Acest compromis inerent devine mai evident pe măsură ce complexitatea produsului crește.

În majoritatea disciplinelor, un dezvoltator poate atenua această problemă alegând un cadru sau o bibliotecă care ajută la arhitectură. În front-end-ul orientat către web, mulți dezvoltatori aleg React sau Angular; în lumea dezvoltării API, inginerii software pot alege dintre Django, ASP.NET MVC sau Play, printre multe altele. Cu toate acestea, când vine vorba de umilul dezvoltator de algoritmi de optimizare, există foarte puține instrumente de arhitectură care să ajute la gestionarea complexității arhitecturale. Dezvoltatorul este lăsat să gestioneze singur variabilele, constrângerile și diversele obiective. În plus, algoritmii de cercetare operațională sunt în general dificil de introspectat, exacerbând problema.

Scopul principal al HorusLP este de a oferi un cadru arhitectural pentru dezvoltarea algoritmilor de optimizare. Oferind consistență structurală, cadrul facilitează organizarea și permite dezvoltatorilor să se concentreze pe ceea ce fac ei cel mai bine: construirea de algoritmi.

Provocări tipice ale fluxului de lucru de optimizare

Există mai multe surse majore de complexitate atunci când se dezvoltă algoritmi SAU:

Complexitate din variabile

• Adesea, variabilele trebuie adăugate pentru a se potrivi cerințelor comerciale suplimentare și nu există o modalitate ușoară de a le urmări pentru a fi utilizate în definițiile modelelor și raportarea ulterioară.
• Variabilele înrudite trebuie grupate și urmărite și nu există o modalitate evidentă de a le gestiona.

Complexitate din constrângeri

• Constrângerile trebuie adăugate și eliminate pentru a suporta diverse scenarii și pentru a efectua depanare, dar nu există un loc evident pentru a adăuga sau elimina constrângeri.
• Constrângerile sunt adesea legate/dependente unele de altele și nu există o modalitate naturală de a-și exprima relațiile.

Complexitate din obiective

• Expresiile obiective pot deveni greoaie dacă au mai multe componente. Acest lucru poate fi exacerbat dacă diferitele componente sunt ponderate, iar ponderile trebuie ajustate în funcție de cerințele afacerii.

Complexitate din depanare

• Nu există o modalitate ușoară de a vedea rezultatele modelului în timpul dezvoltării. Un dezvoltator trebuie să imprime în mod explicit noi variabile și valori de constrângere pentru a vedea rezultatele. Acest lucru duce la duplicarea codului și la o dezvoltare mai lentă.
• Când adăugarea unei constrângeri face ca modelul să devină infezabil, poate să nu fie evident de ce constrângerea a făcut ca modelul să devină infezabil. De obicei, dezvoltatorii trebuie să elimine diverse constrângeri și să caute incompatibilitatea prin încercare și eroare

HorusLP speră să facă aceste provocări mai ușor de gestionat, oferind structură, instrumente, cele mai bune practici pentru a îmbunătăți productivitatea dezvoltatorului și mentenabilitatea produsului.

Tutorial HorusLP: Algoritmul de optimizare și prezentarea generală a API-ului

Fără alte prelungiri, haideți să ne aruncăm și să vedem ce poate face biblioteca HorusLP pentru dvs.!

Deoarece HorusLP se bazează pe Python și PuLP, vom dori să le instalăm folosind pip. Rulați următoarele în linia de comandă:

 Pip install horuslp pulp

Odată ce instalarea este completă, să mergem mai departe și să deschidem un fișier Python. Vom implementa problema rucsacului din articolul meu anterior despre cercetarea operațională.

Biblioteca HorusLP are un API declarativ foarte simplu și foarte puțin boilerplate. Să începem prin a importa clasele și variabilele necesare:

 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

Odată ce am importat toate variabilele, să definim variabilele de care avem nevoie pentru această problemă. Facem acest lucru creând o subclasă manager de variabile și populând-o cu variabilele binare:

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

Acum că variabilele sunt definite, să definim constrângerile. Creăm constrângeri subclasând clasa principală de constrângeri și implementând funcția ei „define”.

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

În funcția define, puteți cere variabilele necesare după nume. Cadrul va localiza variabila în managerul de variabile și o va trece în funcția define.

După ce constrângerea este implementată, putem implementa obiectivul. Deoarece este un obiectiv simplu, vom folosi ObjectiveComponent :

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

Funcția define are o configurație foarte similară cu funcția define a clasei de constrângeri. Totuși, în loc să returnăm o expresie de constrângere, returnăm o expresie afină.

Acum că variabilele, constrângerile și obiectivele sunt definite, să definim modelul:

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

Pentru a construi modelul, creăm o clasă care este o subclasă a clasei Problem și specificăm variabilele, obiectivele, constrângerile și sensul. Cu problema specificată, putem rezolva problema:

 prob = KnapsackProblem() prob.solve()

După rezolvare, putem tipări rezultatele utilizând funcția print_results a clasei probleme. De asemenea, putem accesa valoarea unor variabile specifice analizând clasa result_variables .

 prob.print_results() print(prob.result_variables)

Rulați scriptul și ar trebui să vedeți următoarea ieșire:

 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}

Ar trebui să vedeți starea problemei, valoarea finală a variabilelor, valoarea obiectivă și valoarea expresiei constrângerii. De asemenea, vedem valorile rezultate ale variabilelor ca un dicționar.

Și iată-o, prima noastră problemă HorusLP în aproximativ 35 de linii!

În exemplele următoare, vom explora câteva caracteristici mai sofisticate ale bibliotecii HorusLP.

Utilizarea VariableGroups

Uneori, variabilele sunt legate și aparțin unui grup logic. În cazul problemei rucsacului, toate variabilele pot fi plasate într-un grup de obiecte. Putem refactoriza codul pentru a folosi grupul de variabile. Asigurați-vă că salvați codul din secțiunea anterioară, deoarece ne vom referi la el în tutorialele ulterioare!

Modificați instrucțiunile de import astfel:

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

Acum trebuie să schimbăm și declarațiile variabilelor din rucsac astfel:

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

Primul argument este numele grupului de variabile, a doua variabilă este o listă de nume pentru variabilele din acel grup.

Acum trebuie să schimbăm constrângerile și definițiile obiective. În loc să cerem numele individuale, vom vedea grupul de variabile, care va fi transmis ca un dicționar în care cheile sunt numele și valorile sunt variabilele. Modificați definițiile constrângerii și obiectivelor astfel:

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

Acum putem folosi aceeași definiție a problemei și rulăm comenzi:

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

Ar trebui să vedeți acest lucru în rezultatul dvs.:

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

Gestionarea constrângerilor multiple

Modelele cu o singură constrângere sunt relativ rare. Când lucrați cu constrângeri multiple, este bine să aveți toate constrângerile într-un singur loc, astfel încât să poată fi urmărite și gestionate cu ușurință. HorusLP face asta natural.

Să presupunem, de exemplu, că dorim să vedem cum s-ar schimba rezultatele dacă am forța modelul să adauge o cameră la rucsac. Am implementa o constrângere suplimentară și am adăuga-o la definiția problemei noastre.

Reveniți la modelul pe care l-am implementat în primul tutorial. Adăugați următoarea constrângere:

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

Pentru a adăuga constrângerea la model, trebuie pur și simplu să o adăugăm la definiția problemei astfel:

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

Rulați problema și ar trebui să vedeți următoarea ieșire:

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

Ar trebui să vedeți noua constrângere tipărită în stdout și valorile variabilei optime modificate.

Gestionarea constrângerilor dependente și a grupurilor de constrângeri

Constrângerile sunt adesea legate între ele fie pentru că sunt dependente una de cealaltă, fie pentru că aparțin, în mod logic, aceluiași grup.

De exemplu, dacă doriți să setați o constrângere pentru a limita suma valorii absolute a unui set de variabile, trebuie mai întâi să specificați constrângeri pentru a exprima relațiile de valoare absolută dintre variabilele dorite și apoi să specificați limitele valorii absolute. Uneori, trebuie să aplicați constrângeri similare unui grup de variabile pentru a exprima o relație specifică între variabile.

Pentru a exprima aceste grupări, putem folosi caracteristica de constrângeri dependente a definițiilor noastre de constrângeri. Pentru a vedea cum poate fi utilizată caracteristica de constrângere dependentă, refactorizați SizeConstraint a problemei anterioare astfel:

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

Și acum pentru a testa că constrângerile dependente sunt implementate automat, să scoatem MustHaveItemConstraint din definiția problemei:

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

Și rulați din nou codul și ar trebui să vedeți următoarele în stdout:

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

Se pare că MustHaveItemConstraint este implementat! Pentru un exemplu mai complex despre cum poate fi utilizată constrângerea dependentă, consultați exemplul de personal de la sfârșitul tutorialului.

Gestionarea mai multor obiective ponderate

Adesea, în timpul dezvoltării algoritmilor noștri de optimizare, vom întâlni o expresie obiectivă compusă din mai multe părți. Ca parte a experimentului nostru, putem modifica cântărirea diferitelor componente obiective pentru a influența algoritmul spre rezultatul dorit. CombinedObjective oferă o modalitate curată și simplă de a exprima acest lucru.

Să presupunem că dorim să modificăm algoritmul pentru a alege figurina și cidrul. Să refactorăm codul din secțiunea anterioară pentru a folosi CombinedObjective .

Mai întâi, importați clasa CombinedObjective astfel:

 from horuslp.core import CombinedObjective

Putem implementa o componentă obiectiv independentă astfel:

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

Acum putem combina obiectivul valoric și obiectivul cidru/figurină prin implementarea unui CombinedObjective :

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

Acum să schimbăm definiția problemei astfel:

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

Rulați problema și ar trebui să vedeți următoarea ieșire:

 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

Rezultatul va sublinia valoarea obiectivului combinat, valoarea fiecăreia dintre componentele obiectivului, ponderea și, desigur, valoarea tuturor constrângerilor.

Găsirea constrângerilor incompatibile

Când dezvoltăm algoritmi, întâlnim adesea modele imposibil de realizat. Dacă modelul este complex, poate fi dificil să se determine de ce modelul este brusc imposibil de fezabil. HorusLP are un instrument la îndemână pentru a vă ajuta în aceste cazuri.

Să presupunem că adăugăm constrângeri și am ajuns la următorul set de constrângeri:

 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

Avem câteva constrângeri cu privire la dimensiunea totală a articolelor din rucsac, o constrângere care impune ca cidrul să fie în rucsac și un set incompatibil de constrângeri care necesită ca camera să fie atât în ​​rucsac, cât și nu în rucsac. (Desigur, într-un algoritm din lumea reală, constrângerile nu sunt de obicei la fel de evidente și implică relații variabile complexe și constrângeri.)

Să presupunem, de asemenea, că constrângerile sunt grupate în felul următor, făcând probabil detectarea mai dificilă:

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

Iată definiția problemei:

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

Rulați problema și ar trebui să vedeți următorul rezultat:

 KnapsackProblem: Infeasible

Oh nu! Ce facem? Dacă folosim majoritatea instrumentelor, trebuie să ne lansăm într-o sesiune dificilă de depanare în care limităm una câte una constrângerile potențial conflictuale. Din fericire, HorusLP are o funcție de căutare a incompatibilității pentru a vă ajuta să restrângeți mai rapid constrângerile incompatibile. Cel mai simplu mod de a utiliza funcția de căutare a incompatibilității este să modificați apelul print_results astfel:

 prob.print_results(find_infeasible=True)

Simplu ca asta! Rulați codul și acum ar trebui să vedeți următoarele ca rezultat:

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

Grozav! Acum am stabilit că MustHaveItemConstraint nu este cauza infezabilității și că problema se datorează CombinedConstraints1 și CombinedConstraints2 .

Asta ne oferă câteva informații, dar între constrângerile combinate există patru constrângeri dependente. Putem identifica care dintre cele patru constrângeri sunt incompatibile? Ei bine, da. Modificați apelul print_results astfel:

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

Acest lucru va face ca căutarea de infezabilitate să extindă constrângerile dependente, astfel încât să obținem o imagine mult mai granulară a ceea ce cauzează infezabilitatea. Rulați acest lucru și ar trebui să vedeți următoarea ieșire:

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

Deși este tentant să rulați căutarea profundă a infezabilității de fiecare dată, pentru probleme realiste cu un număr mare de constrângeri totale, căutarea profundă a infezabilității poate deveni foarte consumatoare de resurse și consumatoare de timp. Prin urmare, cel mai bine este să rulați căutarea de bază a infezabilității pentru a restrânge posibilitatea și a rula căutarea profundă a infezabilității pe un subset mai mic după ce ați efectuat o investigație manuală.

Construirea de algoritmi din fișiere de date

Când construim modele, rareori avem luxul de a codifica fiecare constrângere și variabilă. Adesea, programul nostru trebuie să fie suficient de flexibil pentru a schimba modelul în funcție de datele de intrare. Să presupunem că în loc de intrare codificată am vrut să ne construim problema rucsacului din următorul 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 }

Putem face acest lucru bazându-ne pe suportul kwargs pentru funcția „definire” pe care o implementăm pentru constrângeri și obiective.

Să modificăm codul din problema simplă a rucsacului (problema pe care am implementat-o ​​în secțiunea 1 a tutorialului). Mai întâi, să punem șirul JSON în fișier. Desigur, l-am citi în mod normal dintr-o sursă externă, dar de dragul simplității, să păstrăm totul într-un singur fișier. Adăugați următoarele la codul dvs.:

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

Să ne asigurăm, de asemenea, că programul nostru ar putea să-l analizeze. Adăugați următoarele la extrasele dvs. de import:

 Import json

Acum, să modificăm codul nostru de configurare variabilă astfel:

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

Aceasta va defini o variabilă pentru fiecare dintre elementele din JSON și o va numi corespunzător.

Să modificăm constrângerile și definițiile obiectivelor astfel:

 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)

Cerând **kwargs în loc de variabile specifice, funcția define obține un dicționar care conține toate variabilele după nume. Funcția de definire a constrângerii poate apoi accesa variabilele din dicționar.

Notă: Pentru grupurile de variabile, va fi un dicționar imbricat unde primul nivel este numele grupului și al doilea nivel este numele variabilei.

Restul este destul de simplu:

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

Rulați acest program și ar trebui să vedeți următoarea ieșire:

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

Definirea valorilor personalizate în HorusLP

Uneori, atât pentru depanare, cât și pentru raportare, vom construi valori personalizate care nu sunt exprimate direct în obiectiv sau ca o constrângere. HorusLP are o caracteristică pentru a simplifica specificarea valorilor personalizate.

Să presupunem că dorim să ținem evidența câte fructe punea modelul din secțiunea anterioară în rucsac. Pentru a urmări acest lucru, putem defini o valoare personalizată. Să începem prin a importa clasa de bază Metrics:

 From horuslp.core import Metric

Acum să definim valoarea personalizată:

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

După cum puteți vedea, interfața definită arată foarte asemănătoare cu cele ale clasei de componente constrângeri și obiective. Dacă ați urmat tutorialul până acum, acesta ar trebui să vă fie destul de familiar.

Acum trebuie să adăugăm metrica la definiția problemei. Interfața de aici din nou este foarte similară cu definiția constrângerii:

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

Rulați acest lucru și ar trebui să vedeți următoarea ieșire:

 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

Puteți vedea numărul de fructe imprimat în partea de jos.

Lucrul la o problemă mai complexă: două rucsacuri

Să analizăm un exemplu puțin mai complex. Să presupunem că în loc de un singur rucsac, avem o geantă și o valiză. Avem și două clase de obiecte, durabile și fragile. Valisa, fiind mai protectoare, poate ține atât bunuri fragile, cât și durabile. Geanta, pe de altă parte, poate ține doar bunuri de folosință îndelungată. Să presupunem, de asemenea, că datele pentru articole sunt date în următorul 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 }

Să vedem cum se schimbă acest model. Să începem cu o tablă goală, deoarece modelul va fi destul de diferit. Începeți cu configurarea problemei:

 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)

Acum să setăm variabilele. Vom configura o variabilă binară pentru fiecare combinație posibilă de articol/recipient.

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

Acum vrem să implementăm constrângeri de greutate atât pentru valiză, cât și pentru geantă.

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

Acum trebuie să implementăm o constrângere puțin mai complexă - constrângerea care asigură că un articol nu intră atât în ​​valiză, cât și în geantă - și anume, dacă variabila „în valiză” este 1, atunci „în geantă” variabila trebuie să fie zero și invers. Desigur, vrem să ne asigurăm că permitem și cazurile în care articolul nu ajunge în niciun container.

Pentru a adăuga această constrângere, trebuie să iterăm peste toate articolele durabile, să găsim variabila „în valiză” și variabila „în geantă” și să afirmăm că suma acestor variabile este mai mică de 1.

Putem defini dinamic constrângeri dependente destul de ușor în HorusLP:

 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

Acum că constrângerile sunt definite, să construim obiectivul. Obiectivul este simplu suma tuturor valorilor pe care le obținem de la toate articolele care se află în containere. Prin urmare:

 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

Să definim, de asemenea, câteva valori personalizate, astfel încât să putem vedea dintr-o privire câtă greutate a fost pusă în geantă și valiză, precum și cât de mult din greutatea valizei a provenit de la bunuri de folosință îndelungată și bunuri fragile:

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

Acum avem toate piesele terminate, să instanțiem problema și să rulăm modelul:

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

Rulați acest lucru și ar trebui să vedeți următoarea ieșire în stdout-ul dvs.:

 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

Așadar, camera, ochelarii, mărul și banana intră în valiză pentru un total de 15 unități de greutate, figurina, cornul și pielea intră în geantă pentru un total de 17 greutate. Valoarea totală a mărfurilor iese la 32 de unități valorice. Interesant este că niciunul dintre bunurile de folosință îndelungată nu a ajuns în valiză, cel mai probabil pentru că geanta avea suficientă capacitate pentru a ține toate bunurile de folosință îndelungată.

Un scenariu mai mare și mai realist: problema personalului

Dacă ați ajuns până aici în tutorialul nostru HorusLP, felicitări! Acum aveți o idee bună despre cum să utilizați HorusLP.

Cu toate acestea, toate exemplele la care am lucrat au fost până acum permutări ale problemei rucsacului, iar unele dintre cerințe și parametri sunt puțin nerealiste. Să analizăm împreună încă o problemă pentru a vedea cum poate HorusLP să rezolve o problemă mai realistă. Vom rezolva problema cu personalul prezentată în a doua jumătate a articolului meu anterior Toptal.

În interesul timpului, vom merge direct la versiunea finală a modelului (cu conflicte personale, reglementări de muncă și indemnizații pentru lucrători temporari), dar implementarea modelului inițial mai simplu este disponibilă și pe GitHub.

Deci, să începem prin a configura problema:

 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

Acum să definim variabilele, care în acest caz ar fi variabile binare care determină dacă un lucrător ar trebui să-și lucreze în tura și variabile întregi care determină câți dothraki angajăm pentru fiecare tură:

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

Acum să implementăm constrângerea care ne impune să avem suficient personal pentru fiecare tură:

 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

Acum, trebuie să implementăm constrângerile care împiedică anumite persoane să lucreze între ei:

 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.

Încheierea

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!