HorusLP-Gurobi: Arhitectură de optimizare la nivel înalt pentru Gurobi

Pe măsură ce tehnologiile de optimizare devin mai sofisticate, solutorii comerciali au început să joace un rol din ce în ce mai important în industrie. În comparație cu soluțiile open-source, soluțiile comerciale tind să aibă mai multe caracteristici pentru rezolvarea modelelor complexe de optimizare, cum ar fi presolverea avansată, pornirea la cald și rezolvarea distribuită.

Unul dintre cei mai populari soluționatori comerciali de pe piață este Gurobi, numit după cofondatorii Zonghao Gu, Edward Rothberg și Robert Bixby, fiecare pionier în spațiul soluțiilor comerciale. Gurobi a susținut multe proiecte de optimizare de profil înalt în istoria recentă, inclusiv proiectul de alocare a lățimii de bandă al FCC și proiectul de realocare a prizonierilor de stat din Pennsylvania.

Astăzi, ne vom uita la modul în care HorusLP, un pachet software care oferă o interfață declarativă la nivel înalt pentru modelarea de optimizare, se integrează cu API-ul Gurobi pentru a oferi utilizatorilor o experiență intuitivă de modelare, valorificând în același timp cele mai avansate funcții Gurobi.

Optimizare: o reîmprospătare rapidă

Pentru cei care nu sunt familiarizați cu optimizarea sau cercetarea operațională, optimizarea se referă la o colecție de tehnici matematice care găsesc valorile optime ale variabilelor într-un sistem de ecuații supus unui sistem de constrângeri. Dacă propoziția de mai sus sună puțin uscată, poate un exemplu va ajuta la ilustrare.

Să presupunem că aveți un rucsac cu o capacitate de transport de 15 kg. Aveți în față câteva articole, fiecare cu o anumită greutate și valoare monetară:

1. Camera: greutate 2 lbs, valoare 5 USD
2. Figurină: greutate 4 lbs, valoare 7 USD
3. Cidru: greutate 7 lbs, valoare 2 USD
4. Claxon: greutate 10 lbs, valoare 10 USD.

Doriți să alegeți articole pe care să le puneți în rucsac astfel încât greutatea totală să rămână sub 15 lbs, dar valoarea este maximizată. (Dacă aveți nevoie de mai mult context cu privire la motivul pentru care punem obiecte de mare valoare într-un rucsac, sunteți încurajat să vă folosiți imaginația pentru o narațiune. Narațiunile candidaților bune includ salvarea lucrurilor dintr-un incendiu și licitațiile imobiliare... sau unele activități nefaste pe care le avem aș prefera să nu menționez.)

Putem formula problema ca următoarea problemă de optimizare:

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

Odată ce am formulat această problemă, putem aplica tehnici de optimizare pentru a găsi cele mai bune articole de plasat în rucsac. Puteți găsi un exemplu de soluție din articolele mele anterioare despre rezolvarea problemelor de optimizare folosind Python și rezolvarea problemelor de optimizare folosind API-ul principal HorusLP.

Tehnica matematică de bază este destul de fascinantă, dar în afara domeniului de aplicare al acestui articol. Dacă doriți să aflați mai multe, vă recomand să căutați aici și aici, ambele prin amabilitatea lui Gurobi.

Gurobi

În timp ce primele probleme de optimizare au fost rezolvate de echipe de matematicieni care lucrau cu calculatoare, cele mai multe probleme de optimizare de astăzi sunt rezolvate folosind un software specializat numit rezolvatori. În timp ce majoritatea rezolutorilor sunt în general capabili să găsească soluții pentru majoritatea problemelor de programare liniară și întregi bine formulate, unii rezolutori sunt mult mai capabili decât alții. Ei pot rezolva clase de probleme pe care alții nu le pot rezolva, pot rezolva probleme mai rapid prin aplicarea matematicii de ultimă oră sau pot rezolva probleme mari și dificile folosind computere distribuite. Cele mai avansate caracteristici sunt furnizate de obicei în solutoarele comerciale dezvoltate și întreținute de companii specializate în construirea celor mai rapide și mai sofisticate solutoare.

Gurobi este unul dintre liderii de pe piața soluțiilor comerciale, utilizat de segmente mari ale comunității de optimizare, inclusiv guverne, instituții academice și companii care operează în industrii, de la finanțe la logistică. În ceea ce privește viteza, gurobi depășește constant în mai multe benchmark-uri utilizate pentru a judeca solutorii comerciali și open source.

Gurobi vine și cu un API Python puternic care vă permite să construiți modele din Python. Această caracteristică oferă modelatorilor acces la toate bibliotecile utile Python de manipulare a datelor în timpul construcției modelului, ceea ce ajută foarte mult în procesul lor. Ca o demonstrație a API-ului gurobi Python, iată cum puteți modela problema rucsacului:

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

Rularea exemplului vă va oferi următorul rezultat:

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

HorusLP

HorusLP este o bibliotecă de modelare de optimizare care a fost construită pe experiențe de dezvoltare a algoritmilor de optimizare. Bibliotecile de modelare disponibile în prezent nu au instrumentele necesare pentru a lucra cu tipul de probleme complexe, cu mai multe fațete, care sunt întâlnite de obicei de aplicațiile comerciale ale cercetării operaționale.

În timp ce majoritatea bibliotecilor de optimizare oferă o interfață imperativă de nivel scăzut, pe măsură ce modelele de optimizare devin mai complexe, sunt necesare instrumente mai bune pentru a gestiona complexitatea. HorusLP este o bibliotecă care oferă instrumente de nivel superior pentru a gestiona aceste complexități. HorusLP oferă, de asemenea, instrumente puternice de depanare și raportare care permit o dezvoltare și o iterare mai rapidă.

În esență, HorusLP este o bibliotecă orientată pe obiecte care oferă arhitectura atât de necesară în jurul modelelor de optimizare. Utilizând sintaxa orientată pe obiecte Python, biblioteca HorusLP oferă o structură în jurul căreia modelele de optimizare pot fi optimizate. Rezultatul este o bază de cod care este decuplată, modulară și ușor de citit.

Dacă doriți o introducere mai detaliată a bibliotecii de bază HorusLP cu mostre de cod, puteți găsi un tutorial aici.

Integrarea HorusLP-Gurobi

În timp ce API-ul de bază al HorusLP oferă un API convenabil, de nivel înalt pentru construirea de modele de optimizare, este construit pe PuLP, care, deși este capabil să folosească Gurobi ca solutor, nu are acces la unele dintre capabilitățile mai avansate ale lui Gurobi.

HorusLP-Gurobi este o versiune a API-ului HorusLP construită folosind API-ul Python al lui Gurobi. Acest lucru permite utilizatorului acces direct la funcțiile avansate ale Gurobi, păstrând în același timp consecvența API-ului HorusLP.

Una dintre filozofiile cheie care au ghidat dezvoltarea HorusLP-Gurobi a fost coerența cu API-ul de bază HorusLP. Păstrând structura minimalistă a HorusLP consecventă, un utilizator al unui solutor open source poate trece cu ușurință la utilizarea Gurobi instalând API-ul Gurobi și schimbând instrucțiunile de import.

Pentru modelele simple, modelele bazate pe HorusLP vor lua mai multe linii de cod decât simpla utilizare a API-ului Python în mod imperativ. Cu toate acestea, pe măsură ce procesul de dezvoltare continuă și pe măsură ce modelele devin mai complexe, design-urile orientate pe obiecte și declarative ale API-ului HorusLP vor facilita depanarea și dezvoltarea. Orientarea obiectelor va face, de asemenea, modelul mai lizibil, deoarece definiția modelului creează centralizări și delimitează clar obiectivele, constrângerile și variabilele etc.

Fără alte prelungiri, să ne aruncăm în câteva exemple de cod!

Exemple de coduri

API-ul de bază HorusLP

Deoarece HorusLP-Gurobi menține API-ul consistent, codul din tutorialul principal HorusLP poate fi portat printr-o simplă modificare a importurilor. Pentru a utiliza HoruLP-Gurobi, totuși, va trebui să vă asigurați că aveți instalate optimizatorul Gurobi și interfața Python a lui Gurobi. Puteți obține Gurobi luând legătura cu ei aici.

Odată ce instalați Gurobi, putem începe cu codificarea cu HorusLP-Gurobi! Să începem prin a instala pachetul necesar:

 Pip install horuslp horuslp-gurobi

După finalizarea instalării, putem începe să folosim HorusLP-Gurobi! Amintiți-vă de exemplul problemei rucsacului de mai devreme. Putem folosi HorusLP-Gurobi pentru a modela problema după cum urmează:

Mai întâi, importați bibliotecile relevante.

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

Definiți unele variabile.

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

Acum, putem defini constrângerile folosind clasa de constrângeri.

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

Apoi putem implementa obiectivul într-un mod similar.

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

Și, în sfârșit, putem defini problema.

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

Și instanțiăm problema și apelăm funcția solve. Aici se întâmplă magia.

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

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

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

Prima parte este soluția Gurobi, iar a doua parte este rezultatul de la HorusLP. După cum puteți vedea, algoritmul recomandă să luăm figurina și cornul, rezultând 14 lire de articole cu o valoare de 17 USD.

Unul dintre avantajele utilizării HorusLP cu Gurobi este că obțineți o mulțime de informații „gratuit”. Multe dintre informațiile pe care ar dori în mod normal să le analizăm în timpul dezvoltării, cum ar fi valoarea fiecărei variabile, valoarea obiectivă finală și valorile constrângerii, sunt calculate automat și prezentate într-un format ușor de citit.

Dacă ați citit articolul anterior despre nucleul HorusLP, veți observa că acesta este aproape același API. Pentru a menține API-ul simplu, interfețele de bază HorusLP și HorsLP-Gurobi sunt identice, cu diferențe între rezolutori abstrase în implementarea superclasei.

Astfel, vom lăsa introducerea HorusLP acestui exemplu simplu; exemple mai complexe care demonstrează caracteristici avansate ale HorusLP pot fi găsite în articolul anterior.

Caracteristici Gurobi

Gurobi oferă multe funcții avansate pentru rezolvarea problemelor complexe. Majoritatea caracteristicilor sunt accesibile prin obiectul Model. Pentru a permite compatibilitatea deplină cu API-ul Gurobi, obiectul model este ușor accesibil din clasa de probleme ca model .

De exemplu, dacă doriți să scrieți fișierul MPS al modelului de rucsac, în Gurobi puteți scrie ceva de genul m.write('knapsack.mps') . În timp ce utilizați HorusLP-Gurobi, puteți pur și simplu:

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

Și ar trebui să vedeți fișierul MPS în directorul de lucru.

Puteți folosi această interfață pentru a accesa funcții Gurobi avansate, cum ar fi calcularea IIS, crearea de apeluri inverse sau oferirea de indicii variabile.

Funcții avansate Gurobi la dispoziția dumneavoastră

Astăzi ne-am uitat la o versiune a bibliotecii HorusLP construită pe API-ul Gurobi Python. În plus față de funcțiile de raportare și depanare ale nucleului HorusLP, acum aveți acces la toate funcțiile avansate ale Gurobi accesibile fără probleme prin integrarea cu API-ul Python al lui Gurobi.

Dacă sunteți un utilizator Gurobi actual sau cineva interesat să folosească optimizarea Gurobi, sper să încercați HorusLP! Puteți găsi exemplu de cod, puteți face sugestii sau puteți contribui la HorusLP-Gurobi pe GitHub.