HorusLP-Gurobi: architettura di ottimizzazione di alto livello per Gurobi

Man mano che le tecnologie di ottimizzazione diventano più sofisticate, i solutori commerciali hanno iniziato a svolgere un ruolo sempre più importante nel settore. Rispetto ai solutori open source, le soluzioni commerciali tendono ad avere più funzionalità per la risoluzione di modelli di ottimizzazione complessi come il presolve avanzato, l'avvio a caldo e la risoluzione distribuita.

Uno dei solutori commerciali più popolari sul mercato è Gurobi, dal nome dei cofondatori Zonghao Gu, Edward Rothberg e Robert Bixby, ciascuno un pioniere nello spazio dei solutori commerciali. Gurobi ha alimentato molti progetti di ottimizzazione di alto profilo nella storia recente, tra cui il progetto di assegnazione della larghezza di banda della FCC e il progetto di riassegnazione dei prigionieri della prigione statale della Pennsylvania.

Oggi vedremo come HorusLP, un pacchetto software che fornisce un'interfaccia dichiarativa di alto livello per la modellazione di ottimizzazione, si integra con l'API di Gurobi per offrire agli utenti un'esperienza di modellazione intuitiva sfruttando al contempo le funzionalità più avanzate di Gurobi.

Ottimizzazione: un rapido aggiornamento

Per coloro che non hanno familiarità con l'ottimizzazione o la ricerca operativa, l'ottimizzazione si riferisce a una raccolta di tecniche matematiche che trova i valori ottimali delle variabili all'interno di un sistema di equazioni soggetto a un sistema di vincoli. Se la frase sopra suona un po' secca, forse un esempio aiuterà a illustrare.

Supponiamo di avere uno zaino con una capacità di carico di 15 libbre. Hai davanti a te alcuni articoli, ognuno con un peso e un valore monetario specifici:

1. Fotocamera: peso 2 libbre, valore $ 5
2. Figurina: peso 4 libbre, valore $ 7
3. Sidro: peso 7 libbre, valore $ 2
4. Corno: peso 10 libbre, valore $ 10.

Vuoi scegliere gli oggetti da mettere nello zaino in modo tale che il peso totale rimanga inferiore a 15 libbre ma il valore sia massimizzato. (Se hai bisogno di più contesto sul motivo per cui stiamo infilando oggetti di alto valore in uno zaino, sei incoraggiato a usare la tua immaginazione per una narrazione. Le buone narrazioni dei candidati includono il salvataggio di cose da un incendio e le aste immobiliari... o alcune attività nefaste che Preferirei non menzionare.)

Possiamo formulare il problema come il seguente problema di ottimizzazione:

 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

Una volta formulato questo problema, possiamo applicare tecniche di ottimizzazione per trovare gli articoli migliori da inserire nel nostro zaino. Puoi trovare un esempio della soluzione dai miei articoli precedenti sulla risoluzione dei problemi di ottimizzazione utilizzando Python e sulla risoluzione dei problemi di ottimizzazione utilizzando l'API principale di HorusLP.

La tecnica matematica sottostante è piuttosto affascinante, ma esula dallo scopo di questo articolo. Se vuoi saperne di più, ti consiglio di guardare qui e qui, entrambi per gentile concessione di Gurobi.

Gurobi

Mentre i primi problemi di ottimizzazione sono stati risolti da squadre di matematici che lavorano con i calcolatori, la maggior parte dei problemi di ottimizzazione oggi vengono risolti utilizzando software specializzati chiamati solutori. Mentre la maggior parte dei solutori è generalmente in grado di trovare soluzioni alla maggior parte dei problemi di programmazione lineare e intera ben formulati, alcuni risolutori sono molto più capaci di altri. Possono risolvere classi di problemi che altri non possono risolvere, risolvere problemi più rapidamente applicando matematica all'avanguardia o risolvere problemi grandi e difficili utilizzando computer distribuiti. Le funzionalità più avanzate sono solitamente fornite in solutori commerciali sviluppati e mantenuti da società specializzate nella creazione dei solutori più veloci e sofisticati.

Gurobi è uno dei leader nel mercato dei solutori commerciali, utilizzato da ampi segmenti della comunità dell'ottimizzazione, inclusi governi, istituzioni accademiche e aziende che operano in settori che vanno dalla finanza alla logistica. In termini di velocità, Gurobi supera costantemente diversi benchmark utilizzati per giudicare i solutori commerciali e open source.

Gurobi include anche una potente API Python che ti consente di creare modelli da Python. Questa funzionalità offre ai modellatori l'accesso a tutte le utili librerie di manipolazione dei dati di Python durante la costruzione del modello, il che aiuta notevolmente nel loro processo. Come dimostrazione dell'API Python di Gurobi, ecco come potresti modellare il problema dello zaino:

 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)

L'esecuzione dell'esempio ti darà il seguente output:

 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 è una libreria di modelli di ottimizzazione basata su esperienze di sviluppo di algoritmi di ottimizzazione. Le librerie di modelli attualmente disponibili non dispongono degli strumenti necessari per lavorare con il tipo di problemi complessi e sfaccettati che sono tipicamente incontrati dalle applicazioni commerciali della ricerca operativa.

Sebbene la maggior parte delle librerie di ottimizzazione offra un'interfaccia imperativa di basso livello, poiché i modelli di ottimizzazione diventano più complessi, sono necessari strumenti migliori per gestire la complessità. HorusLP è una libreria che fornisce strumenti di livello superiore per gestire queste complessità. HorusLP fornisce anche potenti strumenti di debugging e reporting che consentono uno sviluppo e un'iterazione più rapidi.

Fondamentalmente, HorusLP è una libreria orientata agli oggetti che fornisce l'architettura tanto necessaria attorno ai modelli di ottimizzazione. Sfruttando la sintassi orientata agli oggetti di Python, la libreria HorusLP fornisce una struttura attorno alla quale è possibile ottimizzare i modelli di ottimizzazione. Il risultato è una base di codice disaccoppiata, modulare e di facile lettura.

Se desideri un'introduzione più dettagliata alla libreria principale di HorusLP con esempi di codice, puoi trovare un tutorial qui.

Integrazione HorusLP-Gurobi

Sebbene l'API principale di HorusLP fornisca una comoda API di alto livello per la creazione di modelli di ottimizzazione, è basata su PuLP, che, pur essendo in grado di utilizzare Gurobi come risolutore, non ha accesso ad alcune delle capacità più avanzate di Gurobi.

HorusLP-Gurobi è una versione dell'API HorusLP creata utilizzando l'API Python di Gurobi. Ciò consente all'utente l'accesso diretto alle funzionalità avanzate di Gurobi, mantenendo coerente l'API HorusLP.

Una delle filosofie chiave che ha guidato lo sviluppo di HorusLP-Gurobi è stata la coerenza con l'API core di HorusLP. Mantenendo coerente la struttura minimalista di HorusLP, un utente di un risolutore open source può facilmente passare all'utilizzo di Gurobi installando l'API Gurobi e cambiando le istruzioni di importazione.

Per i modelli semplici, i modelli basati su HorusLP richiederanno più righe di codice rispetto al semplice utilizzo imperativo dell'API Python. Tuttavia, poiché il processo di sviluppo continua e i modelli diventano più complessi, i progetti orientati agli oggetti e dichiarativi dell'API HorusLP faciliteranno il debug e lo sviluppo. L'orientamento agli oggetti renderà anche il modello più leggibile, poiché la definizione del modello crea centralizza e delinea chiaramente gli obiettivi, i vincoli e le variabili, ecc.

Senza ulteriori indugi, tuffiamoci in alcuni esempi di codice!

Esempi di codice

API di base di HorusLP

Poiché HorusLP-Gurobi mantiene l'API coerente, il codice del tutorial principale di HorusLP può essere trasferito con una semplice modifica nelle importazioni. Per utilizzare HoruLP-Gurobi, tuttavia, dovrai assicurarti di avere installato l'ottimizzatore Gurobi e l'interfaccia Python di Gurobi. Puoi ottenere Gurobi mettendoti in contatto con loro qui.

Una volta installato Gurobi, possiamo iniziare con la codifica con HorusLP-Gurobi! Iniziamo installando il pacchetto richiesto:

 Pip install horuslp horuslp-gurobi

Una volta completata l'installazione, possiamo iniziare a utilizzare HorusLP-Gurobi! Richiama il problema dello zaino di esempio di prima. Possiamo usare HorusLP-Gurobi per modellare il problema come segue:

Innanzitutto, importa le librerie pertinenti.

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

Definisci alcune variabili.

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

Ora possiamo definire i vincoli usando la classe vincoli.

 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

Possiamo quindi implementare l'obiettivo in modo simile.

 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

E infine, possiamo definire il 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

E istanziamo il problema e chiamiamo la funzione di risoluzione. Qui è dove avviene la 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

Esegui il codice e dovresti vedere il seguente output:

 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}

La prima parte è il risolutore Gurobi e la seconda parte è l'output di HorusLP. Come puoi vedere, l'algoritmo consiglia di prendere la statuetta e il corno, ottenendo 14 libbre di oggetti con un valore di $ 17.

Uno dei vantaggi dell'utilizzo di HorusLP con Gurobi è che ottieni molte informazioni "gratuitamente". Molte delle informazioni che normalmente si vorrebbe esaminare durante lo sviluppo, come il valore di ciascuna variabile, il valore dell'obiettivo finale e i valori dei vincoli, vengono calcolati automaticamente ed emessi in un formato di facile lettura.

Se hai letto l'articolo precedente sul core di HorusLP, noterai che si tratta quasi della stessa identica API. Per mantenere l'API semplice, le interfacce di HorusLP core e HorsLP-Gurobi sono identiche, con differenze tra i solutori astratte nell'implementazione della superclasse.

Quindi, lasceremo l'introduzione di HorusLP a questo semplice esempio; esempi più complessi che dimostrano le funzionalità avanzate di HorusLP possono essere trovati nell'articolo precedente.

Caratteristiche di Gurobi

Gurobi fornisce molte funzionalità avanzate per la risoluzione di problemi complessi. La maggior parte delle funzionalità sono accessibili tramite l'oggetto Modello. Per consentire la piena compatibilità con l'API Gurobi, l'oggetto modello è facilmente accessibile dalla classe problematica come model .

Ad esempio, se vuoi scrivere il file MPS del modello dello zaino, in Gurobi puoi scrivere qualcosa come m.write('knapsack.mps') . Durante l'utilizzo di HorusLP-Gurobi, puoi semplicemente:

 # 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!

E dovresti vedere il file MPS nella tua directory di lavoro.

Puoi utilizzare questa interfaccia per accedere a funzionalità avanzate di Gurobi come il calcolo di IIS, la creazione di callback o l'indicazione di variabili.

Funzionalità avanzate di Gurobi al tuo servizio

Oggi abbiamo esaminato una versione della libreria HorusLP basata sull'API Python di Gurobi. Oltre alle funzionalità di reporting e debug del core HorusLP, ora hai accesso a tutte le funzionalità avanzate di Gurobi accessibili senza problemi grazie all'integrazione con l'API Python di Gurobi.

Se sei un utente attuale di Gurobi o qualcuno interessato a utilizzare l'ottimizzazione di Gurobi, spero che tu provi HorusLP! Puoi trovare codice di esempio, dare suggerimenti o contribuire a HorusLP-Gurobi su GitHub.