Programmazione a numeri interi misti: una guida al processo decisionale computazionale

La ricerca operativa, la scienza dell'uso dei computer per prendere decisioni ottimali, è stata utilizzata e applicata in molte aree del software. Per fare alcuni esempi, le aziende di logistica lo usano per determinare il percorso ottimale per andare dal punto A al punto B, le compagnie elettriche lo usano per determinare i programmi di produzione di energia e le aziende manifatturiere lo usano per trovare modelli di personale ottimali per le loro fabbriche.

Oggi esploreremo il potere della ricerca operativa esaminando un ipotetico problema. In particolare, utilizzeremo la programmazione a interi misti (MIP) per determinare il modello di personale ottimale per un'ipotetica fabbrica.

Algoritmi di ricerca operativa

Prima di approfondire il nostro problema di esempio, è utile esaminare alcuni concetti di base nella ricerca operativa e comprendere un po' degli strumenti che utilizzeremo oggi.

Algoritmi di programmazione lineare

La programmazione lineare è una tecnica di ricerca operativa utilizzata per determinare il miglior risultato in un modello matematico in cui l'obiettivo ei vincoli sono espressi come un sistema di equazioni lineari. Un esempio di modello di programmazione lineare potrebbe essere simile a questo:

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

Nel nostro esempio molto semplice, possiamo vedere che il risultato ottimale è 5, con a = 2 e b = 3. Anche se questo è un esempio piuttosto banale, puoi probabilmente immaginare un modello di programmazione lineare che utilizza migliaia di variabili e centinaia di vincoli .

Un buon esempio potrebbe essere un problema di portafoglio di investimenti, in cui potresti ritrovarti con qualcosa di simile al seguente, in pseudo-codice:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

Il che sarebbe piuttosto complesso e difficile da risolvere a mano o per tentativi. Il software di ricerca operativa utilizzerà diversi algoritmi per risolvere rapidamente questi problemi. Se sei interessato agli algoritmi sottostanti, ti consiglio di conoscere il metodo simplex qui e il metodo del punto interno qui.

Algoritmi di programmazione intera

La programmazione intera è come la programmazione lineare con un'indennità aggiuntiva per alcune o tutte le variabili come valori interi. Anche se questo potrebbe non sembrare un grande miglioramento all'inizio, ci consente di risolvere molti problemi che avrebbero potuto rimanere irrisolti utilizzando la sola programmazione lineare.

Uno di questi problemi è il problema dello zaino, in cui ci viene fornita una serie di articoli con valori e pesi assegnati e ci viene chiesto di trovare la combinazione di articoli di valore più alto che possiamo inserire nel nostro zaino. Un modello di programmazione lineare non sarà in grado di risolvere questo problema perché non c'è modo di esprimere l'idea che puoi mettere o meno un oggetto nello zaino, ma non puoi mettere parte di un oggetto nello zaino: ogni variabile è un continuo variabile!

Un esempio di problema con lo zaino potrebbe avere i seguenti parametri:

E il modello MIP sarà simile a questo:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

La soluzione ottima, in questo caso, è a=0, b=1, c=0, d=1, con il valore dell'elemento totale pari a 17.

Il problema che risolveremo oggi richiederà anche una programmazione intera, poiché un dipendente in una fabbrica può essere programmato per un turno o meno: per semplicità, non è possibile programmare un dipendente per 2/3 di un turno in questa fabbrica.

Per rendere possibile la programmazione di interi, vengono utilizzati diversi algoritmi matematici. Se sei interessato agli algoritmi sottostanti, ti consiglio di studiare l'algoritmo dei piani di taglio e l'algoritmo branch-and-bound qui.

Esempio di problema: programmazione

Descrizione del problema

Oggi esploreremo il problema del personale di una fabbrica. In qualità di dirigente della fabbrica, vorremo ridurre al minimo i costi di manodopera, ma vogliamo garantire una copertura sufficiente per ogni turno per soddisfare la domanda di produzione.

Supponiamo di avere cinque turni con le seguenti richieste di personale:

E supponiamo di avere i seguenti lavoratori:

Per mantenere il problema semplice, assumiamo per il momento che la disponibilità e il costo siano le uniche preoccupazioni.

I nostri strumenti

Per il problema di oggi, useremo un pezzo di software branch-and-cut open source chiamato CBC. Ci interfacceremo con questo software usando PuLP, che è una popolare libreria di modelli per la ricerca operativa per Python. Puoi trovare informazioni a riguardo qui.

PuLP ci consente di costruire modelli MIP in modo molto Pythonico e si integra perfettamente con il codice Python esistente. Ciò è molto utile poiché alcuni degli strumenti di analisi e manipolazione dei dati più diffusi sono scritti in Python e la maggior parte dei sistemi di ricerca operativa commerciale richiedono un'elaborazione dei dati estesa prima e dopo l'ottimizzazione.

Per dimostrare la semplicità e l'eleganza di PuLP, ecco il problema dello zaino di prima e risolto in PuLP:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

Esegui questo e dovresti ottenere l'output:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Ora sul nostro problema di pianificazione!

Codificare la nostra soluzione

La codifica della nostra soluzione è abbastanza semplice. Innanzitutto, vorremo definire i nostri dati:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] 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 } }

Successivamente, vorremo definire il modello:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

E ora gli chiediamo solo di risolvere e stampare i risultati!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

Una volta eseguito il codice, dovresti vedere i seguenti output:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Aumenta un po' la difficoltà: vincoli aggiuntivi

Anche se il modello precedente era interessante e utile, non dimostra completamente la potenza della programmazione a numeri interi misti. Potremmo anche scrivere facilmente un ciclo for per trovare i lavoratori x più economici per ogni turno, dove x è il numero di lavoratori necessari per un turno. Per dimostrare come MIP può essere utilizzato per risolvere un problema che sarebbe difficile da risolvere in modo imperativo, esaminiamo cosa accadrebbe se aggiungiamo alcuni vincoli extra.

Vincoli aggiuntivi

Supponiamo che, a causa delle nuove normative del lavoro, nessun lavoratore possa essere assegnato a più di 2 turni. Per tenere conto dell'aumento del lavoro, abbiamo reclutato l'aiuto del Dothraki Staffing Group, che fornirà fino a 10 lavoratori Dothraki per ogni turno a una tariffa di $ 40 per turno.

Supponiamo inoltre che, a causa di alcuni conflitti interpersonali in corso al di fuori della nostra fabbrica, Cersei e Jaime non siano in grado di lavorare a turni insieme a Daenerys o Jon. Inoltre, Jaime e Cersei non sono in grado di lavorare su turni insieme. Infine, Arya, che ha relazioni interpersonali particolarmente complesse, non è in grado di lavorare nello stesso turno con Jaime, Cersei o Melisandre.

L'aggiunta di questi due nuovi vincoli e risorse non rende affatto il problema irrisolvibile con mezzi imperativi, ma rende la soluzione molto più difficile, poiché si dovrà tenere conto dei costi opportunità di programmare un lavoratore per un determinato turno.

Soluzione

Con la programmazione a numeri interi misti, tuttavia, è molto più semplice. Dobbiamo semplicemente modificare il nostro codice in questo modo:

Definisci la lista dei ban e alcuni vincoli:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Popola le variabili per l'implementazione del divieto e dei vincoli di spostamento massimo:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Aggiungi le variabili Dothraki:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Avremo anche bisogno di un ciclo leggermente modificato per calcolare i requisiti di spostamento e divieto:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

E infine, per stampare i risultati:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

E dovremmo essere a posto. Esegui il codice e dovresti vedere l'output come di seguito:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

Ed ecco qua, un risultato che rispetta l'elenco dei lavoratori banditi, segue le normative sul lavoro e utilizza i lavoratori Dothraki con giudizio.

Conclusione

Oggi abbiamo esplorato l'utilizzo della programmazione a numeri interi misti per prendere decisioni migliori. Abbiamo discusso gli algoritmi e le tecniche sottostanti utilizzati nella ricerca operativa e abbiamo esaminato un problema di esempio che è rappresentativo di come viene utilizzata la programmazione mista intera nel mondo reale.

Spero che questo articolo ti abbia ispirato a saperne di più sulla ricerca operativa e ti abbia fatto pensare a come questa tecnologia può essere applicata ai tuoi progetti. Abbiamo visto solo la punta dell'iceberg quando si tratta dell'entusiasmante mondo degli algoritmi di ottimizzazione e della ricerca operativa.

Puoi trovare tutto il codice relativo a questo articolo su GitHub. Se vuoi discutere di più, condividi i tuoi commenti qui sotto!