Molti sistemi reali sono estremamente complessi, e richiedono appropriate tecniche quantitative per essere progettati e gestiti in modo sicuro ed efficiente. Le reti
costituiscono un importante esempio di tale tipo di sistemi: le reti di trasporto e le reti di telecomunicazione richiedono sistemi di supporto alle decisioni specializzati,
solitamente basati su opportuni modelli matematici risolti da programmi informatici, per aiutare a prendere decisioni in tutte le fasi del ciclo di vita del sistema, dalla pianificazione alle operazioni quotidiane. Questi sistemi di supporto alle decisioni spesso richiedono la risoluzione di problemi di ottimizzazione estremamente difficili. La complessità di questi problemi deriva principalmente da due fattori:
• alcune decisioni devono essere prese in presenza di incertezza relativa ad alcuni parametri del sistema; tale incertezza può riguardare sia lo stato corrente del sistema, che può non essere conosciuto (magari stimato da una simulazione o mediante un
processo di discretizzazione), sia gli stati futuri, relativi all’evoluzione del sistema nel tempo; l’incertezza può inoltre essere dovuta ad eventi imprevisti, che possono alterare lo stato corrente del sistema oggetto di studio;
• anche nel caso di perfetta conoscenza dei parametri del sistema ed in assenza di eventi imprevisti, alcuni problemi possono essere molto difficili da risolvere a causa della loro inerente complessità computazionale, e/o per via della loro elevata dimensione.
Tali problematiche sono particolarmente evidenti in problemi di ottimizzazione su rete. Le reti sono presenti in molti aspetti della vita quotidiana. La rete elettrica, la rete idrica, le reti di trasporto e le reti di telecomunicazione costituiscono la spina dorsale della società moderna. Il funzionamento efficiente di queste reti è un fondamentale prerequisito per il normale svolgimento di quasi tutti gli aspetti della vita moderna. Molti aspetti del normale funzionamento delle reti richiedono la risoluzione di problemi di ottimizzazione. Ad esempio, l’instradamento del traffico su internet è solitamente basato sulla risoluzione di opportuni problemi di cammino minimo che devono tener conto di fattori quali differenti tipi di traffico (multimedia, high revenue, ecc.), requisiti di Qualità di Servizio (QoS), e guasti della rete. In alcuni casi, la disponibilità di un modello matematico appropriato è cruciale per l’affidabilità delle operazioni; un esempio è costituito dai modelli di settorizzazione che, nel
controllo del traffico aereo, aiutano ad assegnare finestre temporali in modo da massimizzare la sicurezza delle operazioni in volo. In molti altri casi, i sistemi di
supporto alle decisioni basati su modelli matematici hanno gradualmente conquistato un ruolo centrale per l’efficienza delle reti; un esempio è dato dalla schedulazione del personale e/o dei veicoli che operano sulle reti di trasporto (ad esempio ferroviario e aereo). I modelli matematici hanno un ruolo fondamentale anche nelle decisioni di gestione e di progetto delle reti e delle loro componenti tecnologiche. Esempi sono la pianificazione e la gestione delle reti logistiche, il progetto e l’aggiornamento di reti di telecomunicazione (ai diversi livelli, quali fisico e di trasporto), ed il progetto e la gestione nel lungo periodo di reti idriche. L’ampio spazio che è stato dedicato alla
ricerca di algoritmi efficienti per problemi di ottimizzazione con struttura di rete è infatti motivato prevalentemente dall’importanza pratica delle potenziali applicazioni. I progressi della ricerca algoritmica, supportati dalla sempre crescente disponibilità di potenza di calcolo a basso costo, hanno permesso di sviluppare sistemi di supporto alle decisioni capaci di risolvere parecchi problemi di ottimizzazione legati alla pianificazione, alla gestione e alle operazioni di rete.
Come precedentemente accennato, molti aspetti dei problemi reali sono tuttavia soggetti ad incertezza. Ciò è particolarmente evidente se si considerano problemi di ottimizzazione su rete. Le reti elettriche sono soggette a continue variazioni della produzione e della domanda di potenza, nonché ad eventi catastrofici come la rottura degli strumenti di trasmissione o degli impianti di generazione. Le reti di trasporto sono soggette a innumerevoli cause di ritardo (condizioni atmosferiche, congestioni, scioperi, rottura degli equipaggiamenti o delle linee di trasporto, errori umani). Le reti di telecomunicazione sono soggette ad improvvisi ed imprevedibili cambiamenti della domanda di comunicazione, nonché a guasti. Infine, le reti idriche sono soggette alla variazione degli schemi di afflusso e deflusso, variazione che può essere molto difficile predire accuratamente.
Ad alto livello, tale incertezza può essere ricondotta a due diverse tipologie: può essere relativa ad alcuni parametri del sistema (ad esempio, costi/pesi associati ai nodi e agli archi di una rete), o essere legata alla struttura del sistema (quale esistenza di alcuni nodi ed archi in una rete). Spesso la prima forma di incertezza è collegata a mancanza di conoscenza circa alcuni parametri del sistema (ad esempio, quali saranno le domande di comunicazione future in una rete di telecomunicazione), mentre la seconda forma è solitamente collegata ad eventi inaspettati (quali rottura delle attrezzature, condizioni meteorologiche avverse o scioperi in una rete di
trasporto). Nella pratica, e soprattutto nel caso di eventi imprevisti, l’incertezza viene usualmente affrontata con azioni di recupero, ossia mediante cambiamenti della soluzione precedentemente pianificata, che garantiscano che tale soluzione resti ammissibile o non diventi troppo costosa in seguito all’evento imprevisto. In alcuni
contesti (quali reti elettriche e di telecomunicazione) queste azioni devono essere eseguite in pochissimo tempo, e quindi sono delegate ad equipaggiamenti automatici. In altri contesti, quali i trasporti, le azioni di recupero sono delegate alle decisioni umane, molto spesso senza l’assistenza di alcun sistema quantitativo di supporto alle decisioni. Sempre nel contesto delle reti, le azioni di recupero possono essere
estremamente costose e rallentare drasticamente il normale funzionamento della rete.
A causa dell’inerente complessità computazionale di molti problemi di ottimizzazione, l’incertezza è stata a lungo trascurata, o affrontata solo mediante azioni di recupero. In alternativa, in contesti in cui le informazioni riguardanti il comportamento del sistema nel passato possono essere utilizzate per calcolare informazioni statistiche ragionevolmente attendibili, è possibile definire il cosiddetto problema del valore atteso, in cui si assume che i parametri incerti del sistema si realizzino mediante il relativo valore atteso, nella speranza che la corrispondente soluzione deterministica suggerisca decisioni che nel caso medio funzionino ragionevolmente bene. Tuttavia, spesso tale assunzione non è ragionevole, specialmente per quei problemi di natura combinatoria in cui piccole variazioni dei dati possono rendere non ammissibile la soluzione ottima così determinata. In taluni casi si può far ricorso all’analisi di sensitività per valutare come piccole perturbazioni dei dati incerti influenzino la soluzione ottima ottenuta. Tuttavia, tale ricorso è possibile solo per certi tipi di problemi, quali i problemi di Programmazione Lineare (PL), e per un ristretto insieme di possibili variazioni dei dati (ad esempio termini noti o costi), ed è di poco aiuto nella ricerca di soluzioni “robuste”, dal momento che tale analisi può essere eseguita solamente a posteriori, vale a dire al termine del processo di ottimizzazione.
Nonostante ciò, per molto tempo risolvere il problema del valore atteso nel caso di incertezza dovuta ad alcuni parametri del sistema, o intraprendere azioni di recupero, solitamente in tempo reale, in caso di eventi imprevisti, sono state le uniche opzioni possibili per gestire l’incertezza, soprattutto a causa delle limitate capacità risolutive di molti sistemi di supporto alle decisioni.
Da quando la capacità di progettare approcci algoritmici sofisticati è incrementata, e di pari passo il costo della potenza di calcolo è diminuito, ci si è invece resi conto dell’importanza di includere esplicitamente l’incertezza nei modelli matematici, e di affrontarla per via algoritmica. Nel corso degli ultimi anni, e soprattutto nell’arco dell’ultima decade, sono state proposte infatti alcune metodologie per trattare in modo esplicito l’incertezza. Principio guida di tali metodologie è il raggiungimento di un adeguato “compromesso” tra la gamma di condizioni di incertezza cui la soluzione individuata deve essere in grado di far fronte (il cosiddetto livello di robustezza della soluzione determinata), e lo sforzo computazionale necessario per la determinazione di una tale soluzione. Il livello di compromesso raggiunto definisce il cosiddetto livello di conservativismo della metodologia considerata: una metodologia è molto
conservativa quando la soluzione da essa determinata protegge il sistema nei
confronti di un’ampia gamma di condizioni di incertezza, solitamente al prezzo di un notevole sforzo computazionale, ed è invece detta poco conservativa se assicura meno protezione al sistema, privilegiando il ricorso ad uno sforzo computazionale contenuto.
In In principio, si possono distinguere due famiglie principali di metodologie per la gestione esplicita dell’incertezza:
• metodologie di programmazione stocastica, ossia estensioni di metodologie
deterministiche (siano esse lineari o non lineari), in cui ad ogni evento imprevisto e/o ad ogni parametro incerto viene associata un’opportuna distribuzione di probabilità, in modo esplicito oppure implicito;
• metodologie per l’ottimizzazione robusta, ossia metodologie il cui obiettivo è determinare una soluzione che sia in grado di far fronte ad un insieme
opportunamente specificato di eventi imprevisti e/o ad una data variabilità di taluni parametri senza diventare inammissibile e troppo costosa, non facendo alcuna ipotesi di natura probabilistica circa gli elementi del sistema soggetti ad incertezza.
differenti. In primo luogo, le metodologie di programmazione stocastica fanno riferimento ad un ambiente di analisi di decisioni in condizioni di rischio, in cui, cioè, entrano in gioco elementi di tipo probabilistico, contrariamente a ciò che accade nell’ambito delle metodologie per l’ottimizzazione robusta. Inoltre, qualora
l’incertezza possa essere descritta attraverso un opportuno insieme di scenari, dove uno scenario è inteso come la descrizione di un evento imprevisto o la realizzazione di un parametro incerto, spesso le metodologie di programmazione stocastica si
prefiggono l’obiettivo di determinare simultaneamente sia le decisioni relative al normale funzionamento del sistema (detto stato nominale o scenario base), sia le azioni da intraprendere per modificare tale stato nominale in seguito al verificarsi di uno qualsiasi degli eventi e/o realizzazione dei parametri descritti in termini di scenario, a cui viene associata la relativa probabilità di realizzazione. Al contrario, le metodologie per l’ottimizzazione robusta si prefiggono solitamente l’obiettivo di individuare un’unica soluzione che sia in grado di far fronte all’insieme specificato di eventi imprevisti e/o alla specificata variabilità dei parametri del sistema senza perdere la propria ammissibilità, garantendo al tempo stesso una certa qualità in termini di costo della soluzione individuata (per completezza va comunque segnalato che, recentemente, sono state proposte metodologie per l’ottimizzazione robusta, dette adjustable o modificabili, che determinano una soluzione come sopra
specificato, e congiuntamente specificano come modificarla per far fronte al verificarsi di un dato insieme di eventi imprevisti; le metodologieadjustable non verranno considerate nella trattazione che segue).
L’inconveniente principale delle metodologie di programmazione stocastica consiste nell’impossibilità, in talune applicazioni, di associare una funzione di probabilità ad eventi e parametri di un sistema, in quanto tale funzione di probabilità può essere spesso assai difficile da stimare. Inoltre, le metodologie di programmazione stocastica possono permettere, con una certa probabilità, la violazione di alcuni dei vincoli che definiscono il sistema. In taluni contesti applicativi, soprattutto in ambito finanziario, ciò può rendere inadeguato il ricorso a tale tipo di metodologie.
Nel seguito della trattazione analizzeremo alcuni aspetti delle metodologie per l’ottimizzazione robusta. Come precedentemente introdotto, obiettivo di tali metodologie è prendere decisioni, vale a dire determinare soluzioni, che siano “ragionevoli” a prescindere da quelli che saranno i valori effettivamente assunti dai parametri incerti, oppure gli eventi imprevisti che si realizzeranno, purché tale
variabilità risponda ad un’opportuna definizione di incertezza, e la “ragionevolezza” di una soluzione sia dettata da un criterio di robustezza anch’esso opportunamente definito. Specificatamente, nel seguito introdurremo innanzitutto alcune modalità standard per definire l’incertezza. A partire da tali definizioni, presenteremo quindi alcuni criteri base per definire il concetto di soluzione robusta, unitamente a tecniche di modellazione e/o tecniche algoritmiche per la loro determinazione.