OTTIMIZZAZIONE

Ottimizzazione

Nel senso comune, ottimizzare significa determinare e attuare soluzioni che contemperino al meglio esigenze discordanti, per es. coniugare robustezza e leggerezza in un manufatto, alte prestazioni e bassi consumi in un veicolo, flessibilità di risposta al mutamento della domanda ed economia di scala in un sistema produttivo di beni o servizi: in generale, bassi costi e adeguati benefici. Associato all’interesse di un singolo individuo, il concetto di ottimizzazione non è disgiunto da quello di decisione, nel senso di espressione per una preferenza che, dove consapevole, è spesso (ma non sempre) suscettibile di una classificazione e di una misura razionale, in molti casi numerica. Quando ciò avviene, si parla di modello di ottimizzazione, cioè di un modello astratto in grado di porre in relazione logico-matematica le decisioni che è possibile prendere e i vincoli e requisiti che devono soddisfare.

Il ruolo che l’ottimizzazione riveste in natura o nelle attività umane è degno di un’analisi non superficiale. Soprattutto, ottimizzare appare vantaggioso per quelle attività che si esplicano in condizioni critiche. Ed è significativo che la disciplina-contenitore per eccellenza dei metodi di ottimizzazione – la ricerca operativa – sia nata in ambienti militari durante un periodo critico come il secondo conflitto mondiale e abbia conosciuto un fortissimo sviluppo, in gran parte nei medesimi ambienti, al tempo della Guerra fredda tra le superpotenze.

Ciò non significa che in assenza di evidenti criticità non si dia, in sostanza, ottimizzazione. Molti comportamenti degli individui che compongono una società organizzata appaiono implicitamente informati a una certa ottimizzazione dell’uso di risorse: per recarsi sul posto di lavoro si cerca la strada meno trafficata; alla posta o al supermercato si sceglie la fila più breve; dovendosi recare in più posti si organizza mentalmente il tragitto in modo da ridurre tempi e costi, e così via. In sostanza, quando si vuole raggiungere un certo scopo limitando i costi al minimo, o conseguire il massimo profitto o risparmio nell’impiego di risorse limitate, consciamente o no si adopera qualche metodo di ottimizzazione. L’ottimizzazione assume dunque un ruolo importante in situazioni del tutto generali e non necessariamente critiche: simili semmai a quelle che si verificano in un ecosistema oppure in un libero mercato. Entrambi i casi vedono, infatti, individui con obiettivi più o meno determinati competere, collaborare e/o sfruttarsi reciprocamente (in altre parole si potrebbe dire: essere l’uno risorsa per l’altro). E una modellazione in termini di ottimizzazione può aiutare a descrivere i rapporti tra questi individui, a coglierne l’evoluzione in forme più o meno organizzate, a tracciare scenari e prevedere sviluppi.

Questo genere di modellazione è interessante in chiave tanto scientifica quanto tecnica: cioè sia al fine di studiare il fenomeno sia in quanto strumento tra quelli che i protagonisti dello stesso fenomeno possono adottare per dirigere le proprie scelte. Si pensi, per es., alla sopravvivenza economica, in uno scenario di globalizzazione dei mercati: in un contesto nuovo e proprio perciò portatore di inquietudine, come questo, è facile, infatti, guardare all’ottimizzazione come a una possibilità per fornire i soggetti principali, siano essi di carattere pubblico, come i governi, o di tipo privato, come le industrie multinazionali, di strumenti di decisione per rispondere a temi cruciali per la stessa sopravvivenza della specie umana. Si pensi a temi come l’utilizzo dell’energia, dell’acqua, della terra coltivabile: oggi, più di sempre, si è consapevoli che le risorse del pianeta sono limitate e preziose e che il loro uso, in presenza di tecnologie potenzialmente voraci e appetiti robusti, non dovrebbe essere lasciato al caso o alla libera evoluzione e alla legge del più forte.

Certo, non è ragionevole né opportuno adottare al riguardo una visione acriticamente ottimista e positivista: un modello di ottimizzazione riflette soltanto i punti di vista dei decisori che vi sono rappresentati, e con questi anche i loro limiti; inoltre, i punti di vista non rappresentati nel modello non figureranno affatto nell’evoluzione del sistema, almeno fino a un punto nel quale non divengano essi stessi elementi critici. Un esempio può essere l’inquinamento del pianeta conseguente alle attività dell’uomo: l’aria, considerata per secoli dagli operatori economici un bene dalla disponibilità illimitata e, per ciò stesso, gratuito, non è mai stata presa in considerazione come elemento di alcun modello decisionale. Ma ciò che è privo di prezzo non è necessariamente privo di valore, e l’essere arrivati a un punto in cui la disponibilità di un bene essenziale inizia a venire regolata da un sistema di prezzi – come accade oggi, in un certo senso, in virtù degli accordi di Kyoto sulle emissioni di gas serra – offre senz’altro più di un motivo di riflessione.

Diverso è però il discorso se ne si limita l’orizzonte al contributo dell’ottimizzazione allo sviluppo tecnologico. Dalle telecomunicazioni alla componentistica, dalla logistica alla gestione dell’informazione, la possibilità di costruire un modello di ottimizzazione e risolvere i problemi matematici che esso comporta marca, infatti, in moltissimi casi la differenza tra potere e poter fare.

Modelli di ottimizzazione

Come detto, i modelli di ottimizzazione variano in dipendenza del punto di vista: anzitutto, un modello può tenere conto del punto di vista di un singolo decisore oppure di molti; allo stesso modo, il criterio di ottimizzazione del decisore può a sua volta essere unico, oppure multiplo. Per es., progettare un circuito integrato che, impegnando un’area minima, realizzi una funzione input/output prestabilita richiede la definizione di un modello a decisore singolo (il progettista) e criterio singolo (la minimizzazione dell’area impegnata). Un altro semplice esempio è il problema dello zaino (knapsack problem), nel quale si prende in esame il caso di Alì Babà: costui, penetrato nella caverna, vuole prelevare oggetti senza eccedere la portata del sacco che ha sulle spalle; il suo criterio è massimizzare il valore complessivo della refurtiva. Invece, in altro ambito, minimizzare la frequenza di sostituzione di un reagente e massimizzarne l’efficacia rappresentano due distinti (e contrastanti) criteri che si possono adottare nella gestione di un impianto chimico, e il decisore può non sapere a priori quale privilegiare in una gestione ottimale. Infine, un sistema con più operatori che competono per un insieme di risorse limitate cercando di massimizzare il profitto individuale può descriversi per mezzo di un modello a decisore multiplo (gli operatori) e criterio multiplo omogeneo (la massimizzazione del profitto di ciascuno).

La tariffazione di una rete fornisce un semplice esempio di problema multidecisore multicriterio che evidenzia interessanti relazioni gerarchiche tra i decisori. Si immagini che la comunicazione tra due nodi s e t della rete venga stabilita lungo un (s,t)-cammino, vale a dire lungo una sequenza di link che inizia in s e termina in t. Si immagini, inoltre, che per l’utente della rete (un primo decisore, chiamato follower) usare un (s,t)-cammino comporti un costo pari alla somma dei costi di percorrenza dei link che lo costituiscono. Si supponga, infine, che un operatore (un secondo decisore, chiamato leader) possa attivare nuovi link con il criterio di massimizzare gli introiti che derivano dall’eventuale utilizzo di questi link da parte del follower. Se il follower segue il criterio dell’(s,t)-cammino meno costoso, per il leader si pone il problema di scegliere le tariffe dei link introdotti determinando un equilibrio il più favorevole possibile: con tariffe troppo elevate, infatti, il follower eviterà di usare i link aggiuntivi, con tariffe troppo basse il leader incasserà una cifra inferiore alle aspettative.

In un modello nel quale ogni decisore esprime un solo criterio è sensato definire ottima una soluzione che soddisfi il criterio in modo migliore, o almeno non peggiore, delle altre (per es., una soluzione di costo minimo). Ciò non accade in generale se il decisore esprime più di un criterio, come nell’esempio della gestione dell’impianto chimico dove una soluzione ottima rispetto a un criterio può rivelarsi non ottima rispetto all’altro. È una situazione comune nelle scelte delle persone, per es. nell’acquisto di beni durevoli come l’automobile, caratterizzati da prezzi e prestazioni differenti. In casi di questo tipo si parla di dominanza tra soluzioni, intendendo che una soluzione domina un’altra se appare preferibile a quella rispetto a tutti i criteri considerati. Una soluzione che non risulti dominata da alcun’altra si dice Pareto-ottima e l’insieme delle soluzioni Pareto-ottime è detto regione di efficienza.

Va osservato che ogni problema di ottimizzazione, anche quando rappresenti un singolo decisore e un singolo criterio, ammette implicitamente l’esistenza di un secondo, notevole punto di vista: quello dell’antagonista. Un giocatore di scacchi ha un antagonista che oppone contromosse (decisioni) alle sue mosse; un operatore che offre un servizio a una certa tariffa ha un antagonista nel concorrente che desidera valutare la convenienza a entrare in quel mercato praticando tariffe diverse per quel tipo di servizio; l’antagonista di un soggetto che cerca di massimizzare un profitto fabbricando beni a partire da risorse limitate è rappresentato dal complesso degli operatori del mercato che lo riforniscono delle risorse necessarie alla produzione. Questo punto di vista è analizzato da un apparato teorico molto fecondo che va sotto il nome di teoria della dualità e al quale si accennerà nel seguito.

Un’altra distinzione può essere fatta tra modelli descrittivi e modelli prescrittivi. Nel primo caso il modello si limita a descrivere gli elementi di interesse esplicitandone tutte le reciproche relazioni ed è utilizzato per simulare il comportamento del sistema reale (comportamento descritto attraverso opportuni indicatori di output) al variare di condizioni esterne, sollecitazioni di input e parametri di controllo. Le variazioni, tese a condurre gli indicatori ai valori desiderati, sono praticate in modo sistematico con metodi statistici secondo uno schema di natura sperimentale. Non potendo di solito coprire con tali variazioni l’intero spettro delle possibilità non si pretende in genere di individuare una soluzione ottima in senso stretto. Diversamente, un modello prescrittivo codifica parte delle sollecitazioni e dei parametri di controllo (e specificamente quelli accessibili al controllore) sotto forma di variabili di decisione e per esse definisce (matematicamente) un insieme di vincoli che, descrivendo relazioni reciproche, ne contiene le possibili variazioni all’interno di una certa regione; mentre un insieme di indicatori di output, rappresentati anch’essi come funzioni matematiche di queste variabili, definisce gli obiettivi del decisore (o dei decisori). Più ambizioso di uno descrittivo, un modello prescrittivo richiede dunque il calcolo di quei valori delle variabili di decisione che consentono agli obiettivi di raggiungere i valori desiderati. Perciò, un modello prescrittivo può essere utilizzato a patto che la complessità del sistema da ottimizzare sia sufficientemente contenuta e ha senso nella misura in cui il problema matematico soggiacente ammette un algoritmo di soluzione efficiente.

Nel seguito si cercherà di chiarire i concetti espressi attraverso pochi esempi intesi a descrivere il ruolo della modellazione matematica in applicazioni potenzialmente di rilievo nel prossimo futuro nell’ambito delle scienze statistiche, economiche, biologiche e dell’ingegneria. Infine si accennerà, in modo necessariamente sommario, ad alcuni dei metodi matematici al momento considerati tra i più efficaci e promettenti.

Scienze statistiche

Determinare il miglior fitting di un insieme di dati riportati in un diagramma cartesiano, vale a dire individuare fra quelle di una certa classe-modello Ƴ la curva – detta di regressione – che ne interpreta la tendenza, è un classico problema di statistica che, allo stesso tempo, si configura notoriamente come problema di ottimizzazione. In generale, dati p record numerici omogenei che descrivono n caratteristiche di un certo campione e che si rappresentano quindi come una nuvola di punti di ℝⁿ, la curva di regressione a questi associata è una (iper)curva di Ƴ che si trova a distanza minima (secondo una metrica prescritta) dalla nuvola data. In questo contesto, sono di fatto metodi di ottimizzazione i cosiddetti metodi dei minimi quadrati e della massima verosimiglianza, largamente impiegati nella statistica induttiva per il fitting di modelli a dati. Analogamente ai metodi d’interpolazione tipici del calcolo numerico i quali, similmente, richiedono la risoluzione di problemi di ottimizzazione, l’esempio riportato trova applicazione generale tanto nelle scienze economiche e sociali quanto nella verifica sperimentale propria di qualunque metodo scientifico.

La tradizione che vede lo studio di problemi di ottimizzazione come uno strumento essenziale per le scienze statistiche è tuttora molto viva. A titolo di esempio si cita l’interessante campo applicativo del data mining recentemente apertosi a seguito degli enormi sviluppi delle tecnologie dell’informazione le quali, riducendo i costi di dispositivi e software, hanno moltiplicato le possibilità di raccolta e trattamento dei dati da parte delle più svariate organizzazioni.

In sostanza, il data mining riguarda l’analisi di cospicue e complicate messi di dati alla ricerca delle informazioni effettivamente interessanti che, in un certo senso, vi sono sepolte e conta applicazioni che vanno dalla statistica medica al marketing alle scienze sociali. Un centro di ricerca medico in possesso di record clinici relativi a un gran numero di pazienti può porsi il problema interpretativo di correlare le componenti dei record (che possono essere estremamente ricchi d’informazione, includendo, per es., i risultati di complessi esami clinici così come l’attuazione di protocolli di somministrazione di farmaci) all’insorgenza ovvero al recedere di una determinata patologia. Similmente, tecniche di data mining sono largamente impiegate nell’analisi di dati microeconomici. Un esempio è il supporto al marketing attraverso la segmentazione della clientela; oppure alle organizzazioni bancarie per identificare transazioni fraudolente o profili di clienti a elevato potenziale economico o di rischio. Più recentemente, si riscontrano applicazioni alla gestione di siti Internet o di posta elettronica per l’individuazione automatica della pirateria informatica e dello spamming. Infine, un campo applicativo d’impatto rilevante per le tecniche di data mining è rappresentato dall’analisi di dati genetici, dove le tecniche note si confrontano con il problema di trattare dati descritti da insiemi di variabili estremamente numerosi (nell’ordine delle centinaia di migliaia).

Nella maggioranza dei casi il trattamento di informazioni così estese ed eterogenee viene affidato a un sistema di calcolo progettato, con scopi predittivi, per separare i casi positivi da quelli negativi (per es., pazienti sani da pazienti malati, transazioni sicure da transazioni fraudolente). Il sistema è inizialmente addestrato su un campione opportunamente predisposto e, prima di essere rilasciato per l’uso operativo, è messo alla prova su una popolazione più ampia misurando in varie forme gli errori commessi. Metodi matematici di ottimizzazione, come quelli tesi al calcolo di una misura di sovrapposizione di due classi di record ovvero alla determinazione della migliore (iper)superficie di separazione tra due classi, contribuiscono grandemente al miglioramento dell’affidabilità e precisione dei sistemi descritti, e di fatto i migliori schemi di apprendimento automatico (reti neurali; alberi di decisione; SVM, Support Vector Machines) fanno largo uso di tecniche evolute di ottimizzazione per garantire a un tempo accuratezza ed efficienza computazionale.

Scienze economiche

Nell’ambito della teoria economica, metodologie direttamente o indirettamente legate all’ottimizzazione hanno occupato nel secolo scorso un posto di rilievo assoluto, testimoniato dai premi Nobel per l’economia John R. Hicks e Kenneth J. Arrow (teoria dell’equilibrio economico generale, 1972), Wassilij Leontiev (modelli input-output, 1973), Leonid V. Kantorovič e Tjalling C. Koopmans (teoria della distribuzione ottimale delle risorse, 1975), Gerard Debreu (teoria dell’equilibrio economico generale, 1983), John C. Harsanyi, John F. Nash Jr e Reinhard Selten (teoria dei giochi non cooperativi, 1994). Questi contributi, e altri ancora, condividono quello che potremmo definire un punto di vista quantitativo: vale a dire descrivono i fenomeni economici non sulla base di osservazioni generali sulle propensioni degli attori o di generiche relazioni tra settori della produzione, bensì attraverso l’uso di equazioni e di modelli logico-matematici che, alimentati con dati rilevati sul terreno, forniscono utili elementi di previsione e analisi. A differenza dei primi modelli di tipo macroeconomico, in grado di trattare soltanto flussi o quantità di carattere globale (come il prodotto lordo, il valore aggiunto settoriale ecc.), la tendenza recente pone l’accento su modelli microeconomici, nei quali un ruolo essenziale è assegnato ai decisori, rappresentati come agenti che perseguono in modo più o meno autonomo il proprio interesse.

Nella teoria economica sviluppata nel 20° sec. sono in prima istanza rappresentati due approcci. In uno, il comportamento dell’agente è motivato da preferenze espresse tramite una relazione d’ordine (per semplificare, qualcosa come la graduatoria – con eventuali ex aequo – che ci aspetteremmo fornita da un amico al quale chiedessimo di elencare quelli che, a suo giudizio, sarebbero i dieci film da salvare in caso di catastrofe). Nell’altro, il comportamento è informato da regole di scelta che vengono codificate da una famiglia ℑ di insiemi finiti, detti budget set, che corrispondono a una lista esaustiva delle combinazioni di scelta ammissibili; e da una regola R: ℑ→ℑ tale che R(S)⊂S per ogni S∈ℑ, la quale rappresenta la selezione operata dall’agente sul budget sets S.

Tradizionalmente, una relazione di preferenza si dice razionale se è al tempo stesso completa, vale a dire se è definita per ogni coppia di possibili alternative, e transitiva, nel senso che se a è preferito a b e b è preferito a c, allora a è preferito a c. Sull’effettiva razionalità delle relazioni di preferenza si tornerà tra breve. Si osservi per ora che specifiche ipotesi, altrettanto naturali, si fanno quando si vuol descrivere il comportamento dell’agente attraverso regole di scelta. Una di queste è la consistenza, secondo la quale, in sostanza, se di fronte al budget set S={a, b} l’agente sceglie R(S)={a}, ci si aspetta che di fronte al budget set T={a, b, c} la scelta operata R(T) non possa contenere b senza contenere anche a. Questa assunzione è nota come assioma debole della preferenza rivelata (proposto da Paul Samuelson nel 1938) e conduce alla definizione di una particolare relazione di preferenza, che porta lo stesso nome, secondo la quale a è preferito a b se e solo se esiste un budget set che contiene sia a sia b, e la regola di scelta a esso applicata fornisce un sottoinsieme che contiene a. Si osservi che questa relazione non è necessariamente razionale nel senso sopra descritto e, in effetti, mentre ogni relazione di preferenza razionale può rappresentarsi con regole di scelta consistenti, il viceversa non è detto che si verifichi.

L’apparato assiomatico e modellistico descritto può essere messo alla prova, per es., nell’analisi del risultato globale dei comportamenti dei consumatori in un’economia di mercato – dove il termine mercato indica una situazione nella quale beni e servizi vengono acquistati a prezzi o tassi di scambio noti agli agenti che vi operano. In particolare, è possibile leggere l’assioma debole della preferenza rivelata come un modo equivalente di definire la legge compensativa della domanda, secondo la quale prezzi e quantità richieste si muovono in direzioni opposte con mutazioni del prezzo che lasciano inalterato il livello di ricchezza reale. Nella teoria classica della domanda la decisione di un consumatore razionale – cioè operante in base a una relazione di preferenza razionale – può essere diretta dalla massimizzazione di una funzione utilità soggetta a vincoli che esprimono la dipendenza delle quantità scelte da prezzi e ricchezza disponibile. Un’analoga teoria, fondata in modo rilevante come la prima sull’uso dell’ottimizzazione, è disponibile sul lato della produzione dei beni e servizi, dove i modelli di ottimizzazione riguardano prevalentemente la minimizzazione dei costi e la massimizzazione dei profitti a fronte di specifiche di produzione e di risorse limitate. A un livello di complessità lievemente superiore si trovano poi teorie che rappresentano a un tempo il punto di vista dei consumatori e quello dei produttori: in questo caso, classicamente, una soluzione di equilibrio competitivo è costituita da vettori di consumo x^k associati ai singoli consumatori k∈C, vettori di produzione yⁱ associati ai singoli produttori i∈P, e un vettore di prezzi p=(p1,…, p_n) degli n beni considerati, che massimizzino i profitti pyⁱ e le utilità u_k(x^k) dei soggetti coinvolti rispettando vincoli di conservazione (i beni consumati non possono eccedere la somma di quelli posseduti e quelli prodotti), di ricchezza disponibile (il prezzo dei beni complessivamente acquistati da ogni consumatore non può eccedere il valore di mercato dei beni posseduti e l’eventuale share dei profitti dei produttori) e di equilibrio tra domanda e offerta. Questo tipo di modello rappresenta, come si vede, l’equilibrio del mercato come una soluzione Pareto-ottima di un problema di ottimizzazione a singolo decisore. Situazioni economiche caratterizzate dalla presenza simultanea di più giocatori che competono e contrattano sono spesso efficacemente simulate, invece, da modelli di teoria dei giochi che rappresentano evoluzioni della teoria dell’equilibrio di Nash. Definire una strategia può essere, infatti, notevolmente problematico per il singolo decisore, il quale si trova nella necessità di valutare in anticipo le mosse dei competitori per incassare la massima posta in gioco minimizzando il rischio di perdite.

In tutti i casi esposti, la citata teoria della dualità fornisce strumenti interpretativi di notevole rilievo. Per es., al problema di massimizzare il profitto di un produttore di n beni a fronte di risorse limitate corrisponde un problema (duale) di minimizzazione, la cui soluzione ottima fornisce i prezzi delle singole risorse quali si determinerebbero in condizioni di concorrenza perfetta; a un problema di gioco a somma zero (ossia in cui vincite e perdite si bilanciano), nel quale si vuole massimizzare il peggior risultato economico atteso di un giocatore a fronte delle possibili scelte del concorrente, corrisponde un problema (duale), la cui soluzione ottima fornisce le decisioni che il concorrente dovrebbe prendere per ridurre al minimo il miglior share dell’avversario.

Si conclude ritornando alla definizione di relazione di preferenza razionale per osservare come quella che sembra un’ipotesi ovvia possa sollevare problemi derivanti, in ultima analisi, dal voler attribuire comportamenti razionali a esseri in parte (o nel profondo) irrazionali – e comunque dal fatto che il giudizio delle persone non sempre, o quasi mai, si forma attraverso calcoli logico-matematici. Ciò accade, per es., quando le distinzioni sono espresse in una scala troppo fine, per cui chi esprime la preferenza non è in grado di distinguere elementi adiacenti, ma opera distinzioni nette tra elementi distanti (come quando si sceglie il colore da dare a una parete); o quando la scelta viene posta in termini irrilevanti razionalmente ma non psicologicamente (supponendo che in un negozio a venti minuti di distanza da un altro si possono risparmiare complessivamente 5 euro sull’acquisto di due oggetti di valore molto diverso, molte più persone andranno in quel negozio se i 5 euro si risparmiano nominalmente sull’oggetto meno caro). Ciò accade anche in alcuni casi in cui la decisione è presa attraverso un metodo – come una votazione democratica – che coinvolge agenti con preferenze individuali transitive, ma dà luogo, una volta applicato, a scelte collettive non transitive che non possono quindi essere rappresentate mediante funzioni matematiche di utilità (paradosso di Condorcet). Concetti come bounded rationality introducono, inoltre, limiti al tempo e alle informazioni disponibili per prendere decisioni. Tutto ciò conduce a teorie comportamentali che sottopongono il ruolo delle funzioni utilità e quello stesso di ottimizzazione a critica sostanziale. In questa direzione si attende perciò un’evoluzione della teoria dell’ottimizzazione che sia feconda di nuovi contributi alla comprensione dei problemi.

Biomatematica e bioinformatica

Fin dagli anni Trenta analisi genetiche di organismi viventi mostrarono che specie distinte ma affini in senso evolutivo presentavano sequenze di DNA (DeoxyriboNucleic Acid) che differivano per il fatto di avere all’interno blocchi di geni in ordine inverso. Da allora, molte scoperte in campo biologico hanno accertato che fra le modalità più comuni di evoluzione molecolare figura il cosiddetto riarrangiamento del genoma: ossia, le sequenze geniche di due specie affini hanno spesso lo stesso insieme di geni, disposti però in un ordine differente nella sequenza cromosomica. Di norma, il riarrangiamento si ottiene attraverso quattro meccanismi elementari: reversal di una porzione di sequenza (inversione), riallocazione di sottosequenze (trasposizione), scambio di prefissi/suffissi di due cromosomi (traslocazione), copia di una porzione di cromosoma (duplicazione).

Una questione importante in biologia riguardava quanti eventi fossero necessari per trasformare un genoma in un altro. Il minimo numero di questi eventi è chiamato distanza ed è correntemente ritenuto un valido modo per misurare l’effettiva distanza, in termini evolutivi, fra due specie diverse. Purtroppo, come si può facilmente verificare, pochi eventi successivi sono sufficienti a rendere inintelligibile la relativa vicinanza tra due sequenze di geni: in altre parole, calcolare a occhio (o con carta e matita) la distanza tra due sequenze di DNA non è, in generale, un compito semplice. Si considerino per semplicità le inversioni di blocchi di geni che, tra l’altro, fra i quattro tipi di operazione sono le più frequenti, specialmente negli organismi dotati di un solo cromosoma.

Il problema di calcolare la reversal distance in termini di permutazioni è stato studiato per la prima volta da John Kececioglu e David Sankoff (1995), i quali diedero un algoritmo 2-approssimato (che consente, cioè, di non eccedere la stima della distanza reale di oltre il 100%) e congetturarono che il problema fosse di elevata complessità (ipotesi in effetti confermata da Alberto Caprara nel 1997). In termini matematici, il problema si formula nel seguente modo. Un cromosoma definisce una sequenza σ di elementi di un dato insieme, e tale sequenza viene manipolata attraverso reversals sostituendo una qualsiasi sottosequenza σ′di σ con la rilettura di σ′ in ordine inverso: attraverso reversals successivi si può dunque trasformare la sequenza iniziale σ in un’altra sequenza π che costituisce il target. Poiché questa trasformazione può avvenire attraverso più di un set di reversals, la domanda è: qual è il minimo numero di reversals necessari? Come ben si vede, si tratta di un problema di ottimizzazione (combinatoria): un problema che fino a qualche anno fa sembrava estremamente arduo, ma al quale i contributi teorici e algoritmici recentemente sviluppati hanno dato una risposta efficace, tanto che oggi la distanza (in termini di reversals) tra due sequenze geniche si può calcolare in pochi secondi sul web.

Scienze dell’ingegneria

Le scienze dell’ingegneria costituiscono da sempre un campo di applicazione privilegiato per la teoria dell’ottimizzazione. Senza dubbio ciò è dovuto al ruolo di rilievo rivestito nell’ingegneria dagli aspetti economici e dalla necessità di coniugarli a precisi vincoli tecnologici; ma, a ben vedere, la differenza con le scienze naturali ed economiche non risiede tanto in tale rilevanza, quanto piuttosto nel fatto che i principi di economia occorrenti nelle scienze naturali (per es., nella teoria dell’evoluzione delle specie) fanno normalmente – anche se non sempre – riferimento a modelli multicriterio multidecisore, mentre nell’ingegneria si osserva una prevalenza di modelli a singolo decisore. Gli esempi di applicazione di modelli e metodi di ottimizzazione, innumerevoli e riscontrabili nel proliferare di una vasta letteratura di qualità, vanno dalle telecomunicazioni alla produzione industriale, al progetto di circuiti elettronici, alle tecnologie aerospaziali. Non potendo qui dar conto di tutti, ci si limita a citare due casi di scuola tuttora oggetto di viva attenzione da parte degli esperti del settore.

Il primo esempio riguarda il campo dell’ingegneria gestionale e, in particolare, la gestione di risorse energetiche. Per fissare le idee, si consideri la produzione nazionale di energia elettrica. Dal 1970 a oggi il fabbisogno annuale italiano è più che triplicato, e stime recenti ipotizzano che dagli oltre 300 terawatt/ora attuali esso possa superare 560 nel prossimo decennio. Cifre come queste, elaborate per di più da portatori di interessi del settore, non sono certo da assumere in maniera acritica. Nondimeno l’Italia si trova a dover prendere nel medio periodo decisioni impegnative in merito alle politiche di produzione, non fosse altro che per ridurre la propria dipendenza dagli idrocarburi in un possibile scenario di prezzi crescenti, nonché per ottemperare a obblighi internazionali sottoscritti in merito alla riduzione di emissioni. D’altra parte, il tema della diversificazione delle fonti di approvvigionamento pone questioni decisamente ardue: per es., il nucleare presenta oggettivi problemi in termini di sicurezza intrinseca, di costi iniziali e conseguente rigidità dei prezzi di vendita, scarsa flessibilità produttiva, di smaltimento delle scorie e, non ultimo, di ridotte economie di scala e pesanti vincoli strategici per le nazioni prive di nucleare militare. Le fonti rinnovabili, dal canto loro, non sembrano al momento in grado di coprire il fabbisogno di società industrializzate e, comunque, necessitano del cuscinetto di una rete in grado di assorbire inevitabili picchi o avvallamenti di produzione. In un quadro così complesso e problematico, l’aspetto sul quale tutti sembrano peraltro concordare è l’impellenza di conseguire i massimi risparmi e la massima efficienza nei processi di trasformazione.

A tal proposito le centrali termoelettriche (sia quelle tradizionali sia, a maggior titolo, quelle a ciclo combinato) presentano tuttora un indiscutibile vantaggio in termini di flessibilità, potendo il loro regime essere regolato in tempi relativamente brevi in modo da seguire adeguatamente la domanda. Il problema di massimizzare l’efficienza può allora essere formulato rappresentando, secondo parametri tipici delle singole centrali, i consumi in funzione di variabili decisionali, come la temperatura della centrale al momento dell’accensione (dipendente dalla durata dell’intervallo di fermo) e la potenza erogata istante per istante. Una soluzione del problema definisce, per ciascun istante di pianificazione, lo stato operativo di ciascuna centrale (ossia, banalizzando, se è ‘accesa’ oppure ‘spenta’) e la potenza da questa erogata. La soluzione associata a una singola centrale, detta dispatching, è vincolata al rispetto di svariate condizioni operative, come i tempi di salita e discesa della temperatura e i tempi di mantenimento; oltre a questo, nel loro in­sieme, i dispatchings del parco centrali devono garantire lungo l’arco di pianificazione, ora per ora, il soddisfacimento di un determinato fabbisogno, normalmente corredato di un’opportuna riserva e stabilito dall’ente acquirente sulla base di dati storici come premessa all’aggiudicazione della fornitura. Il problema consiste dunque nel calcolare un dispatching delle centrali che rispetti tutti i requisiti sopra citati consumando (cioè costando) meno possibile.

La complessità del problema è dovuta soprattutto alle non linearità (di origine termodinamica) di erogazione e consumi. Le tecniche di linearizzazione più note – basate su generazione di colonne – comportano un numero di variabili estremamente elevato, dal momento che ogni variabile corrisponde, semplificando, a un (s,t)-cammino su un opportuno grafo; tuttavia, opportuni algoritmi di scomposizione permettono di restituire in tempi accettabili soluzioni che garantiscono notevoli risparmi.

Modelli di ottimizzazione ancora più complessi possono integrare tipologie diverse di generazione di elettricità, come quella idroelettrica, che consente in certi casi l’immagazzinamento di parte dell’energia prodotta in momenti di bassa domanda; tra l’altro, la trattazione di questo aspetto fornisce un notevole esempio di problema multicriterio multidecisore, vista la presenza di altri portatori di interesse, come le autorità di bacino e gli operatori dell’agricoltura. Tali modelli possono altresì occuparsi di problemi di distribuzione (vale a dire, scegliere quali centrali riforniscono quali utenze mantenendo l’equilibrio della rete e minimizzando le perdite di carico) o localizzazione (vale a dire, determinare in modo ottimale i siti di produzione in rapporto a criteri di economia di realizzazione ed esercizio).

Un secondo esempio di successo dell’ottimizzazione nelle scienze dell’ingegneria riguarda i modelli di taglio o packing ottimo. Problemi riducibili a questo formato ricorrono frequentemente in contesti manifatturieri e logistici: nel primo caso, basta pensare a tutte le produzioni industriali (vetro, carta, gomma, tessile, acciaio ecc.) nelle quali componenti di forma e dimensioni prefissate sono ottenuti per taglio da pezze, rulli o lastre standard; nel secondo, al riempimento di container con colli da spedire. Uno degli obiettivi principali in entrambe le situazioni consiste nell’utilizzare al meglio la risorsa disponibile (materiale da tagliare o spazio da occupare) limitando per quanto possibile gli sprechi.

La rilevanza di questo genere di problemi ha richiamato l’interesse dei ricercatori fin dagli anni Cinquanta del Novecento. Il problema classico, noto come cutting stock, consiste nel produrre n formati diversi, ciascuno richiesto in uno specifico quantitativo, a partire da elementi di un unico formato standard di grandi dimensioni minimizzando lo sfrido di lavorazione (ovvero, in modo equivalente, il numero di formati standard complessivamente utilizzati). Formulato matematicamente già nel 1960 a opera di Leonid V. Kantorovich, questo problema è stato uno dei migliori esempi dell’efficacia della tecnica di scomposizione proposta da George Dantzig e Phil Wolfe (1959) e applicata per la prima volta a questo caso da Paul Gilmore e Ralph E. Gomory (1963) con una formulazione nella quale ciascuna variabile decisionale stabilisce quante volte applicare un certo schema di taglio. Le variabili così definite possono raggiungere in linea di principio il numero di 2ⁿ (per intenderci, 100 formati distinti corrispondono a un problema con 1,27×1030 variabili), ma come nell’esempio precedente la tecnica di scomposizione ne consente l’introduzione differita – vale a dire, una nuova variabile viene introdotta solo se in grado di migliorare il valore della soluzione corrente – attraverso la risoluzione di un particolare problema di ottimizzazione (definito di pricing) che, nel caso di taglio unidimensionale, si riduce a un knapsack intero.

Dagli anni Sessanta ai giorni nostri lo studio di problemi di questo tipo ha dato luogo a contributi notevoli per quantità e qualità, sia generalizzando i modelli allo scopo di seguire esigenze applicative sempre più sofisticate (problemi a 2-3 dimensioni, formati non convessi, riutilizzo del materiale tagliato, varietà dei formati standard, riduzione dei set-up dovuti alla rimpostazione dei tagli, lot sizing ecc.), sia sviluppando nuove e più efficienti metodologie di soluzione (tra le più rilevanti va ricordato il metodo di branch-and-price messo a punto da Martin W.P Savelsbergh e altri nel 1998).

Brevi cenni sulla matematica dell’ottimizzazione

Da quanto detto finora un problema di ottimizzazione può considerarsi come il modello di un problema concreto del quale si ricerca una soluzione con caratteristiche tali da renderla preferibile a tutte le altre. In senso matematico e nella generalità dei casi, un modello singolo-criterio è costituito da un funzionale reale f avente come dominio un insieme D di uno spazio vettoriale. Il valore assunto da f in un generico punto rappresenta una misura della qualità della soluzione corrispondente a quel punto: il problema consiste, dunque, nel determinare un punto estremo (per es., un massimo) di f in D, qualora esistente; in altre parole, si tratta di fornire x*∈D tale che f(x*)≥f(x) per ogni x∈D. Un tale punto x* si dice soluzione ottima del problema.

Nella maggioranza dei casi d’interesse D⊆ℝⁿ ed è implicitamente definito tramite una funzione g: ℝⁿ→ℝ^m come l’insieme di tutti i punti x di ℝⁿ che soddisfano il sistema di disequazioni g(x)≤0. Il problema di ottimizzazione assume dunque la forma (detta di programmazione matematica)

max{f(x): g(x)≤0, x∈ℝⁿ} [1]

Una x∈ℝⁿ si dice soluzione ammissibile (inammissibile) di [1] se (se non) verifica g(x)≤0. Particolare importanza assume il rilassamento lagrangiano di [1], definito come

L(λ)=max{f(x)−λg(x): x∈ℝⁿ} λ∈ℝ ^m₊ [2]

il quale dà una limitazione superiore al valore della soluzione ottima di [1]. La limitazione più stringente si ottiene determinando un vettore λ≥0 che minimizzi L(λ): questo secondo problema di ottimizzazione è noto come duale lagrangiano di [1], e lo studio delle sue proprietà è argomento della teoria della dualità.

Nel caso particolare in cui f e g sono entrambe funzioni lineari il problema si dice di programmazione lineare e assume la forma

max{cx: Ax≤b, x∈ℝⁿ} [3]

con A∈ℝ^m×n, b∈ℝ^m, c∈ℝⁿ. Un fatto non privo di conseguenze interessanti dal punto di vista algoritmico è che il duale di un problema di programmazione lineare continua a essere un problema di programmazione lineare.

Un’importante classificazione dei problemi di ottimizzazione viene fatta in base alla disponibilità di un algoritmo efficiente per la loro risoluzione, intendendosi con ciò un algoritmo in grado di calcolare – secondo un modello di calcolo specifico come quello formulato da Alan Turing nel 1936 – una soluzione ottima del problema, ovvero certificarne l’inesistenza, in un numero di passi limitato superiormente da un polinomio nella taglia del problema. Un tale algoritmo si dice polinomiale: laddove disponibile, il problema è classificato come appartenente alla classe P. Per es., la programmazione lineare è un problema della classe P per A, b a coefficienti razionali.

Ottimizzazione combinatoria

Un problema di ottimizzazione discreta si pone quando si cerca una soluzione ottima all’interno di un insieme finito. Un caso particolare di ottimizzazione discreta è l’ottimizzazione combinatoria, che comunemente si formalizza con un universo finito U={u1,…, u_n}, una funzione (detta peso) c: U→ℝ e una famiglia ℑ⊆2^U di sottoinsiemi di U: una volta definito il peso c(X) di X∈U come la somma dei pesi c(u_i)=c_i di tutti gli elementi u_i di X, il problema consiste nel trovare X^*∈ℑ tale che c(X^*)≥c(X) per ogni X∈ℑ, ovvero concludere che ℑ è vuota. Anche in questo caso ℑ viene in genere fornita in modo implicito come la famiglia dei sottoinsiemi di U che soddisfano una certa proprietà ℘ (d’altra parte una definizione esplicita di ℑ, anche se disponibile, è sostanzialmente impraticabile già per valori di n relativamente maneggevoli, dal momento che ℑ può contenere fino a 2ⁿ elementi). La tabella riporta alcuni problemi di ottimizzazione combinatoria notevoli.

La grande maggioranza dei problemi di ottimizzazione combinatoria studiati (inclusi tutti quelli della tabella) appartiene a una superclasse NP di P, contenente tutti quei problemi che ammettono un algoritmo polinomiale in grado di verificare se un dato x è o non è soluzione (ottima) del problema. Per molti di questi problemi si è stabilita l’appartenenza alla classe P; per molti altri si è viceversa dimostrato (Stephen Cook nel 1971) che, se tale algoritmo esistesse, allora ne esisterebbe uno per ogni problema di NP (e quindi si avrebbe P=NP): tali problemi appartengono a una sottoclasse di NP chiamata NP-completa. Se si tratti di P=NP o P≠NP è una questione che risale al 1976, ed è tuttora aperta. Tra i problemi di ottimizzazione combinatoria appartenenti a P rivestono particolare importanza albero ricoprente, matching, taglio e (s,t)-cammino minimo (con funzione peso reale positiva); tra i problemi NP-completi si possono ricordare invece clique, insieme stabile (e quindi set packing, del quale entrambi i problemi rappresentano un caso particolare), insieme dominante, edge covering, node covering (e quindi set covering), knapsack, circuito hamiltoniano, taglio e (s,t)-cammino minimo (con funzione peso reale negativa).

Un problema di ottimizzazione combinatoria ammette in generale una formulazione in termini di programmazione lineare. Questa si ottiene associando biunivocamente a ogni X⊆U un x∈ℝⁿ, detto vettore caratteristico di X, dove x_i=1 se u_i∈X e x_i=0 se u_i∉X. In questo modo si ha evidentemente c(X)=cx e, detto S l’insieme di tutti i vettori caratteristici degli insiemi di ℑ, il problema può porsi nei termini

max{c(x): x∈conv(S)} [4]

dove conv(S) indica l’involucro convesso di S. Poiché conv(S) è un poliedro limitato di ℝⁿ, esso è rappresentabile mediante un sistema di disequazioni lineari, e quindi la [4] ammette la riformulazione [3]. Purtroppo, nonostante, come osservato, la programmazione lineare ∈ P per matrici a elementi razionali, questa riformulazione non consente in generale di pervenire a un algoritmo polinomiale per ogni problema di ottimizzazione combinatoria, in quanto non è noto un algoritmo polinomiale per determinare la forma implicita di conv(S), cioè le matrici A e b, a partire dalla proprietà ℘ che descrive la famiglia ℑ, e le stesse matrici A e b potrebbero avere un numero di elementi esponenziale nella taglia del problema. Tuttavia, questa trasformazione è alla base di un’importante classe di metodi, detti poliedrali, per la soluzione di problemi di ottimizzazione combinatoria. Lo studio di tali metodi appartiene a una branca dell’ottimizzazione detta combinatorica poliedrale.

Di norma, peraltro, la formulazione disponibile non corrisponde all’involucro convesso dei punti soluzione del problema. Quando la formulazione disponibile è un problema di programmazione lineare con variabili soggette ad assumere valori interi è possibile tentare con successo la risoluzione attraverso un metodo di enumerazione implicita detto di branch-and-bound. Nella sua forma più semplice il metodo, disponendo se possibile di una soluzione iniziale ammissibile (ma non necessariamente ottima) ottenuta eventualmente per via euristica e mantenendola come ottimo corrente, costruisce un albero di enumerazione i cui nodi corrispondono a problemi nei quali la funzione obiettivo viene, per es., separatamente minimizzata su sottoinsiemi disgiunti, la cui unione copre la regione ammissibile. Uno dei modi di costituire tale albero consiste nel determinare una prima soluzione x0 del problema di programmazione lineare, ottenuta consentendo alle variabili dichiarate intere di assumere valori non interi. Ovviamente se la soluzione così ottenuta è intera il problema è risolto; in caso contrario, il valore della soluzione fornisce una limitazione inferiore al valore della soluzione ottima, per cercare la quale occorre procedere all’enumerazione. Per far questo si può scegliere una variabile che nella soluzione x0 è stata fissata a un valore non intero q, per es. q=3,5, e separare la regione ammissibile del problema in due sottoinsiemi: uno nel quale la variabile presa in considerazione è vincolata ad assumere valori ≤ q˚=3, l’altro in cui essa è vincolata ad assumere valori ≥ q=4; dopodiché il procedimento si ripete. Quella appena illustrata è la fase di branch, nella quale si produce appunto l’albero di enumerazione per successive ramificazioni corrispondenti alle variabili via via trovate non intere. Questa procedura, che dà comunque luogo a un’esplosione combinatoria degli stati della computazione, può essere accelerata attraverso la fase di bound, che utilizza le limitazioni inferiori generate nel corso del calcolo per tagliare ramificazioni la cui esplorazione non fornirebbe soluzioni migliori dell’ottimo corrente.

Sviluppi futuri

Come gran parte delle discipline scientifiche, anche la teoria dell’ottimizzazione ha subito l’influsso degli sviluppi delle tecnologie dell’informazione, sia indirettamente, attraverso la nascita di nuovi problemi e contesti applicativi indotta da queste tecnologie, sia direttamente, attraverso la crescente disponibilità di potenza di calcolo che, da un lato, ha stimolato la domanda (problemi più complessi, tempi di risposta più rapidi), dall’altro, ha rapidamente reso in parte obsoleti certi tipi di ricerca metodologica, come quella che negli anni a cavallo tra i Settanta e gli Ottanta del secolo scorso sembrava focalizzare l’interesse sulla mera classificazione dei problemi in base alla complessità computazionale. A partire dalla fine degli anni Ottanta si è assistito a una notevole rivalutazione della programmazione lineare come un potente strumento per risolvere in pratica, in modo esatto oppure approssimato (Dorit S. Hochbaum, 1998) problemi teoricamente intrattabili. Il ritorno in auge di metodi poliedrali – tagli di Chvátal-Gomory (Gomory, 1958; Vašek Chvátal, 1971), lift-and-project (Egon Balas, 1993) – non solo ha consentito la risoluzione pratica di importanti problemi di ottimizzazione combinatoria (pionieristici in questo senso i lavori di Manfred Padberg e Giovanni Rinaldi sul traveling salesman problem, e di Francisco Barahona sul max-cut), ma ha dato l’avvio alla costituzione di un corpus teorico che, con i contributi di studiosi quali Chvátal, Lászlό Lovász, Alexander Schrijver, Neil Robertson, Paul Seymour ecc., ha contribuito al raggiungimento di risultati matematici di assoluto rilievo, tra i quali la chiusura delle due celebri congetture di Berge sui grafi perfetti (Lovász, 1972; Maria Chudnovsky, Robertson, Seymour e Robin Thomas, 2002).

Da allora nuovi sentieri sono stati tracciati. Fra le tendenze più significative nell’ambito dei metodi per la soluzione di problemi di programmazione intera si indicano: il perfezionamento di schemi di branching con tecniche volte a tenere sotto controllo la simmetria del problema, l’ottimizzazione di funzioni submodulari, l’applicazione di tecniche di programmazione semidefinita per ottenere limitazioni al valore delle soluzioni correnti generate nello schema di enumerazione, la caratterizzazione della proprietà di total dual integrality.

Bibliografia

A. Mas-Colell, M.D. Whinston, J.R. Green, Microeconomic theory, New York 1995.

D.J. Bertsimas, J.N. Tsitsiklis, Introduction to linear optimization, Belmont (Mass.) 1997.

Approximation algorithms for NP-hard problems, ed. D.S. Hochbaum, Boston (Mass.) 1997.

T. Hastie, R. Tibshirani, J.H. Friedman, The elements of statistical learning. Data mining, inference, and prediction, New York 2001.

A. Schrijver, Combinatorial optimization. Polyhedra and efficiency, Berlin-New York 2003.