09. Prescriptive Analytics
Indice
Obiettivo del Modulo
Definizione
La Prescriptive Analytics usa modelli e algoritmi per suggerire quale decisione prendere, dato un obiettivo, un insieme di vincoli e dati disponibili.
In pratica: dopo aver descritto cosa e successo e previsto cosa potrebbe accadere, si passa alla domanda operativa piu importante: che cosa conviene fare? Per esempio: quale giro deve fare un camion, quale cliente assegnare a quale magazzino, quante risorse allocare a ogni attivita.
Nel corso, questo modulo chiude il percorso iniziato con Operational Analytics: i modelli predittivi di Predictive Analytics producono informazioni, mentre l’ottimizzazione le trasforma in decisioni.
Note
La prescrizione non richiede sempre la soluzione perfetta. Nei problemi reali spesso serve una soluzione abbastanza buona, trovata in tempo accettabile e rispettando i vincoli operativi.
Ottimizzazione Matematica
Problema di ottimizzazione
Definizione
L’ottimizzazione matematica e la selezione del miglior elemento possibile da un insieme di alternative ammissibili.
Formalmente, dato un insieme A e una funzione obiettivo f: A -> R, vogliamo trovare un elemento x0 tale che:
minimizzazione: f(x0) <= f(x) per ogni x in A
massimizzazione: f(x0) >= f(x) per ogni x in AIn pratica: A rappresenta tutte le decisioni possibili, f misura quanto e buona una decisione, e i vincoli eliminano le decisioni non realizzabili.
Esempio operativo
In logistica,
Apuo essere l’insieme di tutti i percorsi possibili per consegnare ordini. La funzione obiettivo puo essere il costo totale, il tempo di percorrenza o la distanza. I vincoli possono imporre capacita dei veicoli, orari di consegna e durata massima dei turni.
Principali famiglie di problemi
Le slide distinguono diverse aree dell’ottimizzazione:
- Linear Programming (LP): funzione obiettivo e vincoli lineari.
- Nonlinear Programming: funzione obiettivo o vincoli non lineari.
- Quadratic Programming: obiettivo con termini quadratici e vincoli lineari.
- Integer Programming (IP/ILP): alcune o tutte le variabili devono essere intere.
- Mixed Integer Linear Programming (MILP): alcune variabili sono intere, altre continue.
- Combinatorial Optimization: le soluzioni sono discrete, come insiemi, percorsi, assegnamenti o permutazioni.
- Stochastic Programming: alcuni parametri dipendono da variabili casuali.
- Robust Programming: cerca soluzioni valide sotto molte possibili realizzazioni dell’incertezza.
- Constraint Programming: modella il problema tramite relazioni e vincoli tra variabili.
Tip
La scelta del modello dipende dalla natura della decisione. Se devo scegliere quantita continue, spesso basta un LP. Se devo scegliere si/no, sequenze o assegnamenti discreti, entrano in gioco IP, MILP e ottimizzazione combinatoria.
Difficolta Computazionale
P, NP e scala reale
Definizione
La difficolta computazionale misura quanto cresce il tempo necessario per risolvere un problema quando cresce la dimensione dell’istanza.
Molti problemi operativi diventano rapidamente ingestibili se si cerca la soluzione ottima con enumerazione completa. Il caso tipico e il Travelling Salesman Problem: con n nodi, il numero di tour possibili cresce circa come (n-1)!.
In pratica: un problema piccolo puo sembrare facile, ma aggiungere pochi clienti, veicoli o vincoli puo far esplodere lo spazio delle soluzioni.
Soluzioni subottime ma utili
Punto chiave
Nelle applicazioni reali, la dimensione delle istanze spesso esclude la possibilita di risolvere tutto all’ottimo in tempi accettabili.
La conseguenza pratica e che si cercano soluzioni:
- fattibili, cioe rispettano i vincoli;
- di qualita accettabile, anche se non dimostrate ottime;
- calcolabili rapidamente, per supportare decisioni operative;
- robuste, se i dati sono incerti o cambiano spesso.
Questo spiega perche euristiche e metaeuristiche sono centrali nella Prescriptive Analytics.
Ottimizzazione Combinatoria
Componenti, soluzioni e fattibilita
Definizione
Un problema di ottimizzazione combinatoria e definito su un insieme di componenti di base
C = {c1, ..., cn}; una soluzione e un sottoinsiemeSdiC, e solo alcune soluzioni appartengono all’insieme fattibileF.
La funzione costo z(S) assegna un valore a ogni soluzione. L’obiettivo e trovare una soluzione fattibile S° con costo minimo. Se non si riesce a provare l’ottimalita, l’algoritmo restituisce la migliore soluzione fattibile trovata S*.
In pratica: i componenti possono essere archi di un grafo, assegnamenti cliente-magazzino, turni, attivita pianificate o scelte binarie. Il lavoro dell’algoritmo e combinare componenti senza violare i vincoli.
Travelling Salesman Problem
Definizione
Il Travelling Salesman Problem (TSP) chiede il tour piu corto che parte da un deposito, visita ogni cliente una sola volta e ritorna al punto di partenza.
Il TSP puo essere simmetrico o asimmetrico. Nel caso simmetrico, andare da i a j costa come andare da j a i; nel caso asimmetrico, i due costi possono differire.
Come problema combinatorio:
Ce l’insieme degli archi del grafo;Fe l’insieme dei cicli hamiltoniani;z(S)e la somma dei pesi degli archi scelti.
Lettura pratica
Un corriere deve visitare 20 clienti. Anche se le distanze sono note, provare tutti i tour e impossibile in pratica. Servono modelli matematici, euristiche o metaeuristiche.
Vehicle Routing Problem
Definizione
Il Vehicle Routing Problem (VRP) estende il TSP: invece di un singolo tour, bisogna costruire rotte ottime per una flotta di veicoli che serve piu clienti.
Input tipici:
V = {0, 1, ..., n}: nodi, con0come deposito;E: archi disponibili;cij: costo o distanza dal nodoial nodoj;di: domanda del clientei;Q: capacita del veicolo;K: numero di veicoli.
I vincoli possono includere finestre temporali, tempi di servizio, durata massima delle rotte, consegne frazionabili, pickup and delivery e limiti dei conducenti.
Note
Il VRP e piu vicino ai problemi logistici reali del TSP, perche include capacita, piu mezzi e vincoli operativi. Per questo e spesso piu difficile da modellare e risolvere.
Generalized Assignment Problem
Definizione
Il Generalized Assignment Problem (GAP) assegna clienti o task a risorse capacitate minimizzando un costo complessivo.
Nel modello presentato, un grafo bipartito collega:
I: strutture o risorse potenziali, per esempio magazzini;J: clienti o punti di domanda;xij: variabile decisionale che indica se il clienteje servito dalla facilityi;cij: costo di servirejdai;qij: domanda o consumo di capacita;Qi: capacita della facilityi.
Il modello minimizza il costo totale, assicura che ogni cliente sia servito e impone che ogni facility non superi la propria capacita.
Esempio operativo
Una catena retail deve assegnare negozi a magazzini. Ogni negozio deve essere servito da un magazzino, ma ogni magazzino ha capacita limitata. Il GAP decide gli assegnamenti minimizzando costo di trasporto o tempo di consegna.
Euristiche Costruttive
Logica greedy
Definizione
Un’euristica costruttiva costruisce una soluzione passo dopo passo, aggiungendo componenti che sembrano promettenti e mantenendo la fattibilita parziale.
Schema generale:
1. Ordina i componenti per costo crescente.
2. Parti da una soluzione vuota.
3. Aggiungi un componente se mantiene la soluzione parzialmente fattibile.
4. Continua finche la soluzione e completa e fattibile.In pratica: e un approccio rapido e intuitivo. Puo funzionare molto bene per alcuni problemi, ma in altri puo produrre soluzioni scarse o non riuscire a completare una soluzione fattibile.
Limite delle scelte miopi
Una scelta conveniente adesso puo rendere costose le scelte successive. Le euristiche greedy sono veloci, ma non guardano abbastanza lontano.
Nearest Neighbor
Definizione
La Nearest Neighbor Heuristic per il TSP parte da una citta e visita ogni volta la citta non ancora visitata piu vicina all’ultima citta visitata.
Passi principali:
- scegli un nodo di partenza;
- trova il vicino non visitato piu vicino;
- ripeti finche tutti i nodi sono visitati;
- collega l’ultimo nodo al punto di partenza.
In pratica: e semplice e veloce, ma il punto di partenza influenza molto il risultato. Le ultime connessioni tendono a essere lunghe, perche l’algoritmo rimanda i nodi meno comodi alla fine.
Tip
Una buona strategia pratica e usare Nearest Neighbor per costruire una soluzione iniziale, poi migliorarla con ricerca locale.
Ricerca Locale
Neighborhood e mosse
Definizione
La ricerca locale parte da una soluzione fattibile e cerca soluzioni migliori nel suo intorno, chiamato neighborhood.
Una funzione di neighborhood N(S) definisce quali soluzioni sono considerate vicine a S. Passare da S a una soluzione S' si chiama mossa.
Schema tipico:
1. Genera una soluzione iniziale fattibile S.
2. Trova la migliore soluzione S' in N(S).
3. Se S' migliora S, sostituisci S con S' e ripeti.
4. Se non ci sono miglioramenti, restituisci S.In pratica: la ricerca locale migliora una soluzione gia esistente. Il risultato dipende fortemente da come definiamo il neighborhood.
2-opt e 3-opt
Definizione
2-opt e 3-opt sono neighborhood classici per il TSP: modificano rispettivamente coppie o terne di archi o nodi per cercare un tour piu corto.
Nel 2-opt sugli archi, l’algoritmo prova a rimuovere due archi e riconnettere il tour invertendo una sottosequenza. Se il costo migliora, accetta la modifica e ricomincia.
Nel 3-opt si considerano modifiche piu ampie, con tre archi o tre nodi. Questo puo trovare miglioramenti migliori, ma costa di piu computazionalmente.
Note
Un ottimo locale rispetto a 2-opt non e necessariamente un ottimo globale. Significa solo che nessuna mossa 2-opt immediata migliora la soluzione.
Metaeuristiche
Intensificazione e diversificazione
Definizione
Una metaeuristica e una strategia generale che guida euristiche piu semplici per ottenere soluzioni di alta qualita, evitando di fermarsi troppo presto in ottimi locali.
Le metaeuristiche gestiscono il trade-off tra:
- intensificazione: cercare meglio in una regione promettente dello spazio delle soluzioni;
- diversificazione: spostarsi verso regioni diverse quando la ricerca e bloccata o poco produttiva.
Esempi nelle slide: Iterated Local Search, Simulated Annealing, Tabu Search, GRASP, Variable Neighborhood Search, ALNS, algoritmi genetici, Ant Colony Optimization, Scatter Search e Particle Swarm Optimization.
Iterated Local Search
Definizione
L’Iterated Local Search (ILS) ripete ricerche locali partendo da soluzioni iniziali diverse o da perturbazioni di soluzioni gia trovate.
Idea pratica:
- genera una soluzione iniziale;
- applica ricerca locale fino a un ottimo locale;
- perturba la soluzione;
- riapplica ricerca locale;
- accetta o rifiuta la nuova soluzione secondo un criterio.
ILS funziona bene quando la perturbazione non e completamente casuale, ma sfrutta la storia della ricerca o la struttura del problema.
Simulated Annealing
Definizione
Il Simulated Annealing (SA) e una metaeuristica che accetta sempre mosse migliorative e, con una certa probabilita, anche mosse peggiorative.
La probabilita di accettare peggioramenti dipende dalla temperatura T: all’inizio e piu alta, poi diminuisce gradualmente. Questo aiuta a uscire da ottimi locali nelle fasi iniziali e a stabilizzarsi nelle fasi finali.
Intuizione
Se un tour TSP e bloccato in una configurazione discreta, accettare temporaneamente un peggioramento puo permettere di raggiungere una regione che poi contiene tour migliori.
Tabu Search
Definizione
La Tabu Search (TS) esplora il miglior vicino disponibile anche se e peggiore della soluzione corrente, ma usa una tabu list per evitare di tornare subito su soluzioni gia visitate.
La memoria e l’elemento distintivo: la tabu list proibisce mosse o soluzioni recenti, riducendo cicli e ripetizioni.
In pratica: TS accetta di peggiorare nel breve periodo per migliorare nel lungo periodo, ma lo fa con controllo, non in modo casuale.
GRASP
Definizione
GRASP sta per Greedy Randomized Adaptive Search Procedure: costruisce soluzioni iniziali con una procedura greedy randomizzata e poi le migliora con ricerca locale.
Il metodo e multistart: quando raggiunge un ottimo locale, riparte da un’altra regione promettente dello spazio di ricerca.
Punti chiave:
- la costruzione non e completamente greedy, perche introduce randomizzazione;
- la randomizzazione evita di generare sempre la stessa soluzione;
- la ricerca locale trasforma una buona soluzione iniziale in una soluzione piu raffinata.
Variable Neighborhood Search
Definizione
La Variable Neighborhood Search (VNS) esplora una sequenza di neighborhood diversi, perche un ottimo locale rispetto a un neighborhood puo non esserlo rispetto a un altro.
La versione Variable Neighborhood Descent (VND) applica neighborhood in ordine fisso. Quando trova un miglioramento, riparte dal primo neighborhood.
VNS aggiunge:
- una perturbazione, per riposizionare la ricerca;
- un criterio di accettazione, per decidere se continuare dalla nuova soluzione.
Note
Solo un ottimo globale e ottimo locale rispetto a tutti i possibili neighborhood. Cambiare neighborhood e un modo pragmatico per non fidarsi troppo del primo ottimo locale trovato.
Adaptive Large Neighborhood Search
Definizione
L’Adaptive Large Neighborhood Search (ALNS) usa operatori di distruzione e riparazione della soluzione, aggiornando dinamicamente il peso degli operatori in base alle loro prestazioni.
Funzionamento intuitivo:
- scegli un metodo di destroy per rimuovere una parte della soluzione;
- scegli un metodo di repair per ricostruirla;
- accetta o rifiuta la nuova soluzione;
- aggiorna i pesi degli operatori piu efficaci;
- restituisci la migliore soluzione incontrata.
In pratica: ALNS e utile per problemi complessi come routing e scheduling, dove piccole mosse locali non bastano e serve modificare blocchi piu grandi della soluzione.
Workflow Operativo
Un workflow pratico di Prescriptive Analytics puo essere:
- Definire la decisione: che cosa si deve scegliere concretamente?
- Definire obiettivo e vincoli: minimizzare costo, tempo, distanza, ritardi o massimizzare profitto e servizio.
- Scegliere il modello: LP, MILP, problema combinatorio, routing, assignment o altro.
- Costruire una soluzione iniziale: euristica costruttiva, greedy o metodo specifico.
- Migliorare la soluzione: ricerca locale o metaeuristica.
- Valutare qualita e tempo: non solo costo finale, ma anche stabilita, fattibilita e tempo di calcolo.
- Integrare con i dati predittivi: usare output di forecasting e modelli ML come input decisionali.
Da ricordare
La soluzione migliore matematicamente non e sempre la migliore operativamente. Deve essere spiegabile, applicabile, compatibile con i vincoli reali e calcolabile quando serve.
Chiusura del Corso
Questo modulo completa il ciclo dell’Operational Analytics:
- statistica descrittiva e statistica inferenziale aiutano a capire e validare i dati;
- predictive analytics e modelli predittivi stimano cosa potrebbe accadere;
- prescriptive analytics decide come agire usando obiettivi, vincoli e algoritmi.
La logica finale e: dati → previsione → decisione → azione. L’ottimizzazione rende operativo questo passaggio, soprattutto quando risorse, tempi e capacita sono limitati.