Architettura di algoritmi di ottimizzazione con HorusLP

La ricerca operativa e l'ottimizzazione convessa sono un campo della matematica applicata che ha trovato negli anni applicazioni commerciali ad ampio raggio. Quando la potenza di calcolo è diventata più accessibile e ampiamente disponibile, i ricercatori hanno iniziato a costruire algoritmi di ottimizzazione sempre più sofisticati per aiutarli a prendere decisioni migliori. Oggi, le applicazioni basate sulla ricerca operativa alimentano qualsiasi cosa, dall'instradamento nella logistica globale al livellamento della produzione di elettricità nel settore energetico.

Con la crescente complessità della tecnologia sottostante, è stato creato un nuovo set di strumenti per aiutare ricercatori e sviluppatori a lavorare in modo più produttivo. Questi strumenti, come AMPL, CVXPY e PuLP, consentono agli sviluppatori di definire, creare ed eseguire rapidamente algoritmi di ottimizzazione e interfacciarsi con un'ampia varietà di risolutori.

Tuttavia, mentre le tecnologie di ottimizzazione e le esigenze aziendali continuano a crescere in maniera sofisticata, la maggior parte di questi strumenti è rimasta più o meno la stessa e non si è evoluta abbastanza rapidamente per soddisfare le esigenze del settore. Di conseguenza, lo sviluppo, la gestione, il debug e l'ottimizzazione di questi algoritmi spesso richiedono una grande quantità di sovraccarico cognitivo, soprattutto in un ambiente aziendale in rapida evoluzione.

Oggi vorrei presentare HorusLP, una libreria di ottimizzazione Python che aiuta con l'architettura dei flussi di lavoro di sviluppo di algoritmi. Parleremo dei problemi che lo strumento è progettato per risolvere, quindi forniremo una rapida panoramica della libreria Python e costruiremo alcuni algoritmi di ottimizzazione di esempio.

Problemi che devono affrontare gli sviluppatori di algoritmi di ottimizzazione

Uno dei problemi perenni che la maggior parte degli sviluppatori deve affrontare è l'equilibrio tra la creazione di un software gestibile, efficiente e idiomatico e la consegna di un prodotto entro i limiti di tempo del progetto. Che tu stia lavorando su un'applicazione basata su browser, un'API Web o un microservizio di autenticazione utente, spesso c'è un compromesso tra il modo "giusto" e il modo "veloce" di raggiungere i tuoi obiettivi. Questo compromesso intrinseco diventa più saliente con l'aumentare della complessità del prodotto.

Nella maggior parte delle discipline, uno sviluppatore può alleviare questo problema scegliendo un framework o una libreria che aiuti con l'architettura. Nel front-end rivolto al Web, molti sviluppatori scelgono React o Angular; nel mondo dello sviluppo di API, gli ingegneri del software possono scegliere tra Django, ASP.NET MVC o Play, tra molti altri. Tuttavia, quando si tratta dell'umile sviluppatore di algoritmi di ottimizzazione, ci sono pochissimi strumenti di architettura per aiutare a gestire la complessità dell'architettura. Lo sviluppatore è lasciato a gestire autonomamente variabili, vincoli e vari obiettivi. Inoltre, gli algoritmi di ricerca operativa sono generalmente difficili da esaminare, aggravando il problema.

Lo scopo principale di HorusLP è fornire un framework architetturale per lo sviluppo di algoritmi di ottimizzazione. Fornendo coerenza strutturale, il framework semplifica l'organizzazione e consente agli sviluppatori di concentrarsi su ciò che sanno fare meglio: costruire algoritmi.

Sfide tipiche del flusso di lavoro di ottimizzazione

Esistono diverse principali fonti di complessità durante lo sviluppo di algoritmi OR:

Complessità da variabili

• Le variabili spesso devono essere aggiunte per soddisfare requisiti aziendali aggiuntivi e non esiste un modo semplice per tenerne traccia per l'uso nelle definizioni dei modelli e nella creazione di report in un secondo momento.
• Le variabili correlate devono essere raggruppate e tracciate e non esiste un modo ovvio per gestirle.

Complessità da vincoli

• I vincoli devono essere aggiunti e rimossi per supportare vari scenari ed eseguire il debug, ma non esiste un luogo ovvio per aggiungere o rimuovere vincoli.
• I vincoli sono spesso correlati/dipendenti l'uno dall'altro e non esiste un modo naturale per esprimere le loro relazioni.

Complessità dagli obiettivi

• Le espressioni oggettive possono diventare ingombranti se hanno più componenti. Ciò può essere aggravato se i vari componenti vengono ponderati e i pesi devono essere adeguati in base ai requisiti aziendali.

Complessità dal debug

• Non esiste un modo semplice per vedere i risultati del modello durante lo sviluppo. Uno sviluppatore deve stampare in modo esplicito nuove variabili e valori di vincolo per vedere i risultati. Ciò porta a codice duplicato e sviluppo più lento.
• Quando l'aggiunta di un vincolo rende il modello non ammissibile, potrebbe non essere ovvio il motivo per cui il vincolo ha reso il modello non ammissibile. Di solito, gli sviluppatori devono eliminare vari vincoli e cercare l'incompatibilità attraverso tentativi ed errori

HorusLP spera di rendere queste sfide più gestibili fornendo struttura, strumenti, migliori pratiche per migliorare la produttività degli sviluppatori e la manutenibilità del prodotto.

Tutorial HorusLP: algoritmo di ottimizzazione e panoramica dell'API

Senza ulteriori indugi, tuffiamoci e vediamo cosa può fare per te la libreria HorusLP!

Poiché HorusLP è basato su Python e PuLP, vorremo installarli usando pip. Esegui quanto segue nella tua riga di comando:

 Pip install horuslp pulp

Una volta completata l'installazione, andiamo avanti e apriamo un file Python. Implementeremo il problema dello zaino del mio precedente articolo sulla ricerca operativa.

La libreria HorusLP ha un'API dichiarativa molto semplice e molto poco standard. Iniziamo importando le classi e le variabili necessarie:

 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

Dopo aver importato tutte le variabili, definiamo le variabili di cui abbiamo bisogno per questo problema. Lo facciamo creando una sottoclasse di gestione delle variabili e popolandola con le variabili binarie:

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

Ora che le variabili sono definite, definiamo i vincoli. Creiamo vincoli sottoclassi della classe di vincolo principale e implementando la sua funzione di "definizione".

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

Nella funzione define, puoi richiedere le variabili richieste per nome. Il framework individuerà la variabile nel gestore delle variabili e la passerà alla funzione define.

Dopo che il vincolo è stato implementato, possiamo implementare l'obiettivo. Poiché si tratta di un obiettivo semplice, utilizzeremo ObjectiveComponent :

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

La funzione define ha un'impostazione molto simile alla funzione define della classe di vincoli. Invece di restituire un'espressione di vincolo, tuttavia, restituiamo un'espressione affine.

Ora che le variabili, i vincoli e gli obiettivi sono definiti, definiamo il modello:

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

Per costruire il modello, creiamo una classe che è una sottoclasse della classe Problema e specifichiamo le variabili, gli obiettivi, i vincoli e il senso. Con il problema specificato, possiamo risolvere il problema:

 prob = KnapsackProblem() prob.solve()

Dopo la risoluzione, possiamo stampare i risultati usando la funzione print_results della classe del problema. Possiamo anche accedere al valore di variabili specifiche osservando la classe result_variables .

 prob.print_results() print(prob.result_variables)

Esegui lo script e dovresti vedere il seguente output:

 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}

Dovresti vedere lo stato del problema, il valore finale delle variabili, il valore obiettivo e il valore dell'espressione del vincolo. Vediamo anche i valori risultanti delle variabili come un dizionario.

E il gioco è fatto, il nostro primo problema HorusLP in circa 35 righe!

Nei prossimi esempi, esploreremo alcune funzionalità più sofisticate della libreria HorusLP.

Utilizzo di gruppi di variabili

A volte, le variabili sono correlate e appartengono a un gruppo logico. Nel caso del problema dello zaino, tutte le variabili possono essere inserite in un gruppo di oggetti. Possiamo refactoring del codice per utilizzare il gruppo di variabili. Assicurati di salvare il codice della sezione precedente poiché vi faremo riferimento nei tutorial successivi!

Modifica le istruzioni di importazione in questo modo:

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

Ora dobbiamo anche modificare le dichiarazioni delle variabili dello zaino in questo modo:

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

Il primo argomento è il nome del gruppo di variabili, la seconda variabile è un elenco di nomi per le variabili all'interno di quel gruppo.

Ora dobbiamo cambiare il vincolo e le definizioni degli obiettivi. Invece di chiedere i singoli nomi, faremo come per il gruppo di variabili, che verrà passato come un dizionario dove le chiavi sono i nomi ei valori sono le variabili. Modificare il vincolo e le definizioni degli obiettivi in ​​questo modo:

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

Ora possiamo usare la stessa definizione del problema ed eseguire i comandi:

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

Dovresti vedere questo nel tuo output:

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

Gestione di più vincoli

I modelli con un unico vincolo sono relativamente rari. Quando si lavora con più vincoli, è bene avere tutti i vincoli in un'unica posizione in modo che possano essere monitorati e gestiti facilmente. HorusLP lo rende naturale.

Supponiamo, ad esempio, di voler vedere come cambierebbero i risultati se costringessimo il modello ad aggiungere una fotocamera al nostro zaino. Implementeremmo un vincolo aggiuntivo e lo aggiungeremmo alla nostra definizione del problema.

Torna al modello che abbiamo implementato nel primo tutorial. Aggiungi il seguente vincolo:

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

Per aggiungere il vincolo al modello, dobbiamo semplicemente aggiungerlo alla definizione del problema in questo modo:

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

Esegui il problema e dovresti vedere il seguente output:

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

Dovresti vedere il nuovo vincolo stampato nello stdout e i valori delle variabili ottimali modificati.

Gestione dei vincoli e dei gruppi di vincoli dipendenti

I vincoli sono spesso correlati tra loro o perché dipendono l'uno dall'altro o perché logicamente appartengono allo stesso gruppo.

Ad esempio, se si desidera impostare un vincolo per limitare la somma del valore assoluto di un insieme di variabili, è necessario prima specificare i vincoli per esprimere le relazioni di valore assoluto tra le variabili previste, quindi specificare i limiti di valore assoluto. A volte, è necessario applicare vincoli simili a un gruppo di variabili per esprimere una relazione specifica tra variabili.

Per esprimere questi raggruppamenti, possiamo utilizzare la caratteristica dei vincoli dipendenti delle nostre definizioni di vincoli. Per vedere come utilizzare la funzione di vincolo dipendente, rifattorizzare SizeConstraint del problema precedente in questo modo:

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

E ora per verificare che i vincoli dipendenti vengano implementati automaticamente, prendiamo il MustHaveItemConstraint dalla definizione del problema:

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

Ed esegui di nuovo il codice e dovresti vedere quanto segue in stdout:

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

Sembra che il MustHaveItemConstraint sia implementato! Per un esempio più complesso di come è possibile utilizzare il vincolo dipendente, fare riferimento all'esempio di assegnazione del personale alla fine dell'esercitazione.

Gestione di più obiettivi ponderati

Spesso, durante lo sviluppo dei nostri algoritmi di ottimizzazione, incontreremo un'espressione oggettiva composta da più parti. Come parte della nostra sperimentazione, possiamo modificare la pesatura di vari componenti obiettivi per orientare l'algoritmo verso il risultato desiderato. L' CombinedObjective fornisce un modo pulito e semplice per esprimere questo.

Supponiamo di voler influenzare l'algoritmo per scegliere la statuina e il sidro. Eseguiamo il refactoring del codice della sezione precedente per utilizzare CombinedObjective .

Innanzitutto, importa la classe CombinedObjective in questo modo:

 from horuslp.core import CombinedObjective

Possiamo implementare una componente obiettivo indipendente in questo modo:

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

Ora possiamo combinare l'obiettivo del valore e l'obiettivo del sidro/figurine implementando un obiettivo CombinedObjective :

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

Ora cambiamo la definizione del problema in questo modo:

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

Esegui il problema e dovresti vedere il seguente output:

 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

L'output delineerà il valore dell'obiettivo combinato, il valore di ciascuna delle componenti dell'obiettivo, il peso e, naturalmente, il valore di tutti i vincoli.

Trovare vincoli incompatibili

Quando sviluppiamo algoritmi, spesso ci imbattiamo in modelli irrealizzabili. Se il modello è complesso, può essere difficile determinare perché il modello è improvvisamente irrealizzabile. HorusLP ha uno strumento utile per aiutarti in questi casi.

Supponiamo di aggiungere vincoli e di ottenere il seguente insieme di vincoli:

 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

Abbiamo un paio di vincoli sulla dimensione totale degli oggetti nello zaino, un vincolo che richiede che il sidro debba essere nello zaino e un insieme incompatibile di vincoli che richiedono che la fotocamera sia dentro e non nello zaino. (Naturalmente, in un algoritmo del mondo reale, i vincoli di solito non sono così ovvi e coinvolgono relazioni e vincoli variabili complesse.)

Si supponga inoltre che i vincoli siano raggruppati nel modo seguente, rendendo forse più difficile il rilevamento:

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

Ecco la definizione del problema:

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

Esegui il problema e dovresti vedere il seguente risultato:

 KnapsackProblem: Infeasible

Oh no! Cosa facciamo? Se stiamo utilizzando la maggior parte degli strumenti, dobbiamo intraprendere una difficile sessione di debug in cui restringiamo uno per uno i vincoli potenzialmente in conflitto. Fortunatamente, HorusLP ha una funzione di ricerca di incompatibilità per aiutarti a restringere più rapidamente i vincoli incompatibili. Il modo più semplice per utilizzare la funzione di ricerca di incompatibilità è modificare la chiamata print_results in questo modo:

 prob.print_results(find_infeasible=True)

Semplice come quella! Esegui il codice e ora dovresti vedere quanto segue come output:

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

Grande! Ora abbiamo stabilito che MustHaveItemConstraint non è la causa dell'impossibilità e che il problema è dovuto a CombinedConstraints1 e CombinedConstraints2 .

Questo ci fornisce alcune informazioni, ma tra i vincoli combinati ci sono quattro vincoli dipendenti. Possiamo identificare quale dei quattro vincoli è incompatibile? Beh si. Modifica la tua chiamata print_results questo modo:

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

In questo modo la ricerca dell'infattibilità espanderà i vincoli dipendenti in modo da ottenere un'immagine molto più dettagliata di ciò che sta causando l'infattibilità. Esegui questo e dovresti vedere il seguente output:

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

Sebbene sia allettante eseguire ogni volta una ricerca approfondita sull'infattibilità, per problemi realistici con un numero elevato di vincoli totali, la ricerca approfondita sull'infattibilità può richiedere molto tempo e risorse. Pertanto, è meglio eseguire la ricerca di non fattibilità di base per restringere la possibilità ed eseguire la ricerca di non fattibilità approfondita su un sottoinsieme più piccolo dopo aver eseguito alcune indagini manuali.

Costruire algoritmi da file di dati

Quando costruiamo modelli, raramente abbiamo il lusso di codificare ogni vincolo e variabile. Spesso, il nostro programma deve essere sufficientemente flessibile da modificare il modello in base ai dati di input. Supponiamo che invece dell'input hardcoded vogliamo costruire il nostro problema dello zaino dal seguente 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 }

Possiamo farlo affidandoci al supporto dei kwargs della funzione di "definizione" che implementiamo per i vincoli e gli obiettivi.

Modifichiamo il codice dal semplice problema dello zaino (il problema che abbiamo implementato nella sezione 1 del tutorial). Innanzitutto, inseriamo la stringa JSON nel file. Naturalmente, normalmente lo leggeremmo da una fonte esterna, ma per semplicità conserviamo tutto in un unico file. Aggiungi quanto segue al tuo codice:

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

Assicuriamoci anche che il nostro programma sia in grado di analizzarlo. Aggiungi quanto segue alle tue dichiarazioni di importazione:

 Import json

Ora modifichiamo il nostro codice di configurazione delle variabili in questo modo:

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

Questo definirà una variabile per ciascuno degli elementi nel JSON e la denominerà in modo appropriato.

Cambiamo il vincolo e le definizioni degli obiettivi in ​​questo modo:

 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)

**kwargs invece di variabili specifiche, la funzione define ottiene un dizionario contenente tutte le variabili per nome. La funzione di definizione del vincolo può quindi accedere alle variabili dal dizionario.

Nota: per i gruppi di variabili, sarà un dizionario nidificato in cui il primo livello è il nome del gruppo e il secondo livello è il nome della variabile.

Il resto è abbastanza semplice:

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

Esegui questo programma e dovresti vedere il seguente output:

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

Definizione di metriche personalizzate in HorusLP

A volte, sia per scopi di debugging che di reporting, creeremo metriche personalizzate che non sono espresse direttamente nell'obiettivo o come vincolo. HorusLP ha una funzione per semplificare la specifica di metriche personalizzate.

Supponiamo di voler tenere traccia di quanti frutti il ​​modello della nostra sezione precedente stava mettendo nello zaino. Per tenerne traccia possiamo definire una metrica personalizzata. Iniziamo importando la classe base Metrics:

 From horuslp.core import Metric

Definiamo ora la metrica personalizzata:

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

Come puoi vedere, l'interfaccia definita è molto simile a quelle della classe dei componenti del vincolo e dell'obiettivo. Se hai seguito il tutorial finora, questo dovrebbe esserti abbastanza familiare.

Ora dobbiamo aggiungere la metrica alla definizione del problema. L'interfaccia qui di nuovo è molto simile alla definizione del vincolo:

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

Esegui questo e dovresti vedere il seguente output:

 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

Puoi vedere il numero di frutti stampato in basso.

Affrontare un problema più complesso: due zaini

Esaminiamo un esempio leggermente più complesso. Supponiamo che invece di un solo zaino, abbiamo una borsa e una valigia. Abbiamo anche due classi di oggetti, durevoli e fragili. La valigia, essendo più protettiva, può contenere sia merci fragili che durevoli. La borsa, invece, può contenere solo beni durevoli. Supponiamo inoltre che i dati per gli articoli siano forniti nel seguente 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 }

Vediamo come questo cambia il modello. Iniziamo con una tabula rasa poiché il modello sarà molto diverso. Inizia con l'impostazione del problema:

 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)

Ora impostiamo le variabili. Imposteremo una variabile binaria per ogni possibile combinazione articolo/contenitore.

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

Ora vogliamo implementare vincoli di peso sia per la valigia che per la borsa.

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

Ora dobbiamo implementare un vincolo leggermente più complesso, il vincolo che assicura che un articolo non entri sia nella valigia che nella borsa, ovvero se la variabile "in the suitcase" è 1, allora "in the bag" la variabile deve essere zero e viceversa. Ovviamente, vogliamo assicurarci di consentire anche i casi in cui l'articolo finisce in nessuno dei due contenitori.

Per aggiungere questo vincolo, dobbiamo eseguire un'iterazione su tutti gli articoli durevoli, trovare la variabile "nella valigia" e la variabile "nella borsa" e affermare che la somma di queste variabili è inferiore a 1.

Possiamo definire dinamicamente i vincoli dipendenti abbastanza facilmente in 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

Ora che i vincoli sono definiti, costruiamo l'obiettivo. L'obiettivo è semplice la somma di tutti i valori che otteniamo da tutti gli oggetti che sono nei contenitori. Così:

 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

Definiamo anche alcune metriche personalizzate in modo da poter vedere a colpo d'occhio quanto peso è stato inserito nella borsa e nella valigia, nonché quanto peso della valigia proveniva da beni durevoli e beni fragili:

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

Ora che abbiamo finito tutti i pezzi, istanziamo il problema ed eseguiamo il modello:

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

Esegui questo e dovresti vedere il seguente output nel tuo stdout:

 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

Quindi la macchina fotografica, gli occhiali, la mela e la banana entrano nella valigia per un totale di 15 unità di peso, la statuetta, il corno e l'uomo di pelle vanno tutti nella borsa per un totale di 17 pesi. Il valore totale della merce è di 32 unità di valore. È interessante notare che nessuno dei beni durevoli è finito nella valigia, molto probabilmente perché la borsa aveva una capacità sufficiente per contenere tutti i beni durevoli.

Uno scenario più ampio e realistico: il problema del personale

Se sei arrivato così lontano nel nostro tutorial HorusLP, congratulazioni! Ora hai una buona idea di come usare HorusLP.

Tuttavia, tutti gli esempi su cui abbiamo lavorato finora sono stati permutazioni del problema dello zaino e alcuni requisiti e parametri sono un po' irrealistici. Esaminiamo insieme un altro problema per vedere come HorusLP può risolvere un problema più realistico. Lavoreremo attraverso il problema del personale delineato nella seconda metà del mio precedente articolo di Toptal.

Nell'interesse del tempo, andremo direttamente alla versione finale del modello (con conflitti personali, normative sul lavoro e indennità per i lavoratori temporanei) ma l'implementazione del modello iniziale più semplice è disponibile anche su GitHub.

Quindi iniziamo impostando il 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

Definiamo ora le variabili, che in questo caso sarebbero variabili binarie che determinano se un lavoratore deve svolgere il proprio turno e variabili intere che determinano quanti dothraki assumiamo per ogni turno:

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

Adesso implementiamo il vincolo che ci impone di personale a sufficienza per ogni turno:

 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

Ora, dobbiamo implementare i vincoli che impediscono a persone specifiche di lavorare tra loro:

 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.

Avvolgendo

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!