Interessi di ricerca di Antonio Frangioni

Also available in English.

I miei principali interessi di ricerca riguardano l'analisi, ideazione, implementazione e testing di metodi risolutivi per problemi di ottimizzazione strutturati di grandi dimensioni, con particolare enfasi sulle tecniche di (ri)formulazione che permettono di rivelare e sfruttare rilevanti proprietà di problemi nell'interfaccia tra l'ottimizzazione continua e quella combinatoria, e la loro applicazione a problemi reali in diversi contesti applicativi (energia, trasporti, telecomunicazioni, ...). Sono anche interessato alle problematiche di analisi numerica, informatica, intelligenza artificiale e machine learning che emergono all'interno di questi approcci e, viceversa, all'uso di tecniche di programmazione matematica in queste discipline.

La mia ricerca tenta di coniugare strettamente tre diversi aspetti: metodologico, applicativo ed implementativo. Ciò appare necessario in quanto lo sviluppo di opportune metodologie generali permette il miglioramento delle prestazioni nella soluzione di problemi anche molto diversi tra loro; ad esempio, i risultati teorici descritti in [A7, A14, A25, A37] hanno applicazioni in ambiti molto diversi quali l'ottimizzazione su rete [A5, A9, A22], la schedulazione di centrali elettriche [C1, C2, C4, A10, A21] o di veicoli ed equipaggi [N1, A23, A64] ed i problemi di Max-Cut [A13]. D'altro canto, lo studio di problemi specifici porta alla definizione di nuovi approcci metodologici che possono poi trovare applicazioni in ambiti diversi; questo è stato ad esempio il caso dei risultati in [A17] che, motivati da problemi relativi alla schedulazione di centrali elettriche, si sono poi mostrati utili per problemi del tutto diversi [A45, A43, A42, A30, A18, A74]. Infine, la significatività di un contributo, teorico o applicativo che sia, può essere maggiore se viene messo a disposizione degli utenti interessati (nell'accademia o nell'industria) software efficiente e facile da utilizzare che implementa le idee sviluppate. Ciò è particolarmente vero per contributi legati allo sviluppo di algoritmi sofisticati, per i quali la parte implementativa è non banale. Per questo durante la mia ricerca ho particolarmente curato gli aspetti di sviluppo del software e di rilascio del medesimo sotto licenze open source [A39]; si veda l'apposita sezione del mio CV che documenta i molti pacchetti software, organizzati in diversi progetti, che rappresentano un significativo contributo al software di ottimizzazione open source prodotto in Italia,anche grazie ad una linea di ricerca specifica (della quale sono stato coordinatore) di un progetto MIUR. Per motivi analoghi ho anche curato la realizzazione o la raccolta e distribuzione di istanze di problemi di ottimizzazione; dal sito https://commalab.di.unipi.it/datasets sono scaricabili molte diverse collezioni di istanze di problemi di ottimizzazione, ed ho collaborato alla realizzazione di librerie di istanze [A61].
Sono particolarmente attratto dalla ricerca che attraversa i confini tra discipline diverse quali l'analisi numerica, diverse forme di programmazione matematica e l'informatica, come ad esempio applicare tecniche nonlineari a problemi discreti [A1, A5, A10, A13, A15, A18, A23, A30] e viceversa [A16, A17, B4], investigare gli aspetti di analisi numerica in algoritmi di ottimizzazione [A6, A12] e viceversa [A19, A44, A47], applicare tecniche di programmazione parallela a problemi di ottimizzazione [A9, B2], applicare tecniche di ottimizzazione a problemi inerenti lo sviluppo di algoritmi [A40, A65], oppure esplorare le connessioni tra la programmazione matematica, l'intelligenza artificiale ed le tecniche di machine learning [B5 B6, B14, B15, C18, A73, E1]. Questo perché credo fermamente nella necessità di adattare gli strumenti della ricerca alle caratteristiche del problema del sotto esame, se necessario superando i limiti e gli steccati che dividono—spesso surrettiziamente—le diverse discipline.

Dal punto di vista metodologico, le tecniche algoritmiche da me più studiate sono state:

Dal punto di vista applicativo, i problemi che ho principalmente studiato sono:

Comunque, ho anche affrontato altri problemi, ed utilizzato metodologie diverse ove ciò risultasse utile.

Ottimizzazione NonDifferenziabile

L'ottimizzazione di funzioni che non hanno derivate prime continue è significativamente più complessa rispetto al caso delle funzioni differenziabili. Esistono però molte applicazioni importanti con questa caratteristica, tra le quali i metodi di decomposizione mediante rilassamento Lagrangiano [A14] e la decomposizione di Benders [A49], alcune tra le tecniche di elezione per l'approccio a problemi di ottimizzazione strutturati di grandi dimensioni e/o di ottimizzazione combinatoria.
I Metodi del Subgradiente (SM) sono molto popolari per la soluzione di problemi nondifferenziabili grazie alla loro semplicità di implementazione ed il basso costo computazionale. Sono state proposte varianti innovative di SM che combinano proiezione a deflessione [A25], permettendo nel contempo di calcolare la funzione obiettivo solo approssimativamente, ma senza perdere il controllo sulla qualità della soluzione finale ottenuto. Inoltre è stato effettuato un accurato studio computazionale di molte diverse varianti di SM, comprese quelle di [A25], al fine di sviluppare linee guida in grado di aiutare nella scelta della variante più adatta ad ogni specifica applicazione [A52]. Un problema particolare si palesa quando i SM vengono usati per il training delle reti neurali, poiché in questo caso vengono utilizzati formati floating-point a bassa accuratezza; per questo ho studiato le proprietà di convergenza dei SM con errori che rappresentano questo caso di uso per funzioni quasi-convesse [C18], che sono ritenute essere una buona approssimazione (migliore, comunque, di quelle convesse) della funzione di loss delle reti neurali (almeno vicino ad un minimo locale).
All'altro estremo dello spettro sono stati studiati algoritmi Metodi di tipo "Bundle" (BM) [B10], che richiedono la soluzione di un problema di ottimizzazione ad ogni passo per determinare l'iterata successiva, e che quindi sono più complessi da implementare e potenzialmente più costosi; per contro, la loro velocità di convergenza in pratica può essere significativamente più alta. Per questi metodi sono stati ideati algoritmi e realizzati componenti software specifici [A3] al fine di velocizzare la soluzione dei sottoproblemi "master". Dal punto di vista più strettamente metodologico, sono state proposte diverse estensioni alla classe dei BM per adattarli alla strutture specifica delle funzioni che emergono dalle applicazioni. In particolare è stato ampliato l'insieme dei possibili "termini di stabilizzazione" utilizzabili nel problema "master" di questi algoritmi [A7], in modo da poter, ad esempio, usare tecniche di Programmazione Lineare invece che di Programmazione Quadratica per risolverli; ciò porta ad implementazioni più efficienti per importanti applicazioni [A23, A37, A38]. Sono inoltre stati studiati diversi casi in cui parte della struttura del problema viene sfruttata per specializzare il problema "master" [A37, A38], ottenendo significativi miglioramenti delle prestazioni rispetto all'approccio classico. È anche stata esplorata la possibilità di utilizzare problemi "master" con vincoli conici del secondo ordine [A33], in modo da incorporare nel modello informazione parziale "del secondo ordine". Infine, è stata sviluppata un'analisi innovativa della convergenza dei BM che consente una maggiore flessibilità in alcune delle decisioni algoritmiche cruciali, in particolare permettendo di non richiedere la monotonia della funzione obiettivo nei "centri di stabilizzazione" scelti [A41]. Un'accurata analisi dell'impatto sull'algoritmo di computazioni inesatte della funzione è contenuta in [A55], dove viene proposta una variante dell'algoritmo che utilizza modelli superiori per evitare di calcolare alcune componenti nel caso di funzioni somma, non solamente nei "Null Steps" ma anche nei "Serious Step". Inoltre, sono state proposte due nuove forme di "Noise Reduction Steps" che risultano utili sotto specifiche assunzioni del modo in cui l'oracolo tratta il fatto di non essere in grado di calcolare la funzione con accuratezza arbitraria.
L'applicazione di BM alla soluzione di Duali Lagrangiani di problemi di ottimizzazione strutturata corrisponde a versioni "stabilizzate" del metodo di decomposizione di Dantzig-Wolfe, mediante l'aggiunta di variabili di slack e termini di penalizzazione quadratici [A2] o più generali [A7]. Questa tecnica si adatta ad estensioni del metodo di Dantzig-Wolfe come gli algoritmi di generazione di colonne [A23], i metodi di Dantzig-Wolfe parziale [A38] ed i metodi di Dantzig-Wolfe strutturato [A37], permettendo l'implementazione di codici efficienti per la soluzione di molti problemi di ottimizzazione, sia in sequenziale [A4, A5, A10, A13, A14, A15, A21, A22, A32, A56, A64, A66>/A>, A68 B1, B12, C1, C2, C4] che in parallelo [A9]. Lo studio ha riguardato anche le problematiche relative all'uso di tecniche di decomposizione come alternativa alle classiche tecniche di Programmazione Lineare all'interno di approcci enumerativi [T2].
Anche se queste tecniche sono state per la maggior parte applicate a metodi di decomposizione basati sul rilassamento Lagrangiano, in effetti esse sono applicabili anche all'altro approccio (duale) della decomposizione di Benders, che in ultima analisi è ancora un metodo del tipo "piano di taglio". In questo caso per´ il "master problem" è un problema combinatorio ed alcune proprietà non si estendono in modo ovvio, richiedendo un'analisi specifica. Questo aspetto è studiato in [A49] per algoritmi basati su oracoli informativi, on-demand ed inesatti che permettono di diminuire il costo computazionale dell'approccio risolvendo i sottoproblemi in modo inesatto per la maggior parte delle iterazioni. Una specifica applicazione al Cell Suppression Problem relativo alla confidenzialità di dati statistici ha dimostrato che l'approccio in effetti porta a significtivi miglioramenti delle prestazioni rispetto ad implementazioni "standard" del metodo [A63].
La ricerca prosegue sia dal punto applicativo, con l'applicazione delle metodologie ad altri contesti ed il miglioramento dei risultati già ottenuti, sia dal punto di vista teorico che dal punto di vista algoritmico con il perfezionamento e l'estensione del software e delle tecnologie disponibili.

Metodi Interior Point

La ricerca in questo campo si è focalizzata nel tentativo di costruire versioni specializzate ed efficienti di metodi Interior Point (IP) per problemi di Programmazione Lineare con particolare struttura. Per questo è stato realizzato un modulo Interior Point generico, contenente tutti gli elementi algoritmici indipendenti dalla struttura del problema, che è stato poi specializzato su alcune specifiche classi di problemi. In particolare, sono stati studiati metodi IP per problemi di Flusso di Costo Minimo; dopo uno studio delle proprietà teoriche rilevanti dei sistemi lineari caratteristici di questi problemi [A6], sono state proposte alcune nuove famiglie di precondizionatori per la soluzione efficiente di tali sistemi [A12, A19], anche all'interno di approcci "extended crossover" [A20] in cui si utilizzano congiuntamente sia algoritmi IP che approcci di tipo combinatorio. I precondizionatori sono successivamente stati utilizzati con successo all'interno di metodi multi-iterativi [A44, A47], sviluppando apposite famiglie di proiettori ed interpolatori che mantengono la struttura di grafo della matrice ai livelli inferiori.
Indipendentemente, è stato implementato e testato un algoritmo IP parallelo per problemi di Flusso Multicommodity [B2], anch'esso basato su metodi iterativi per la soluzione dei corrispondenti sistemi lineari. La ricerca prosegue con l'affinamento dei risultati ottenuti e l'estensione ad altre classi di problemi; un'interessante prospettiva sembra inoltre essere offerta dallo sviluppo di tecniche ibride che utilizzino i metodi IP in congiunzione con tecniche Lagrangiane.

Algoritmi per problemi misti-interi nonlineari

Una linea di ricerca si è focalizzata sullo studio di tecniche di riformulatione per problemi di Programmazione NonLineare Mista-Intera (MINLP) con particolari strutture. Ad esempio, per problemi con variabili semi-continue e funzione obiettivo separabile, convessa e nonlineare la Riformulazione Prospettica permette di ottenere, attraverso il rilassamento continuo, valutazioni inferiori di qualità significativamente migliore. Poiché la Riformulazione Prospettica ha una funzione obiettivo fortemente nonlineare, è stata studiata una classe di diseguaglianze valide, dette Tagli Prospettici [A17], che permette di modellarla sotto forma di un problema di programmazione semi-infinita, ma con funzione obiettivo molto più semplice. Generando un numero finito di tali tagli si ottengono metodi approssimati che si sono dimostrati efficaci in alcuni contesti [A24]. Le diseguaglianze sono state confrontate con una riformulazione alternativa, basata su vincoli conici, risultando in generale molto competitive [A26].
Benché queste tecniche richiedano la separabilità della funzione obiettivo, è stato proposto un metodo efficace per estrarre, nel caso di funzioni quadratiche, una parte separabile della funzione obiettivo alla quale applicare l'approccio, con buoni risultati [A18]. Calcolare Riformulazioni Prospettiche "esatte" di problemi non separabili è in generale complesso, ma ciò puù essere fatto per matrici kxk con un "piccolo" k; la funzione obiettivo originale può poi essere decomposta (se necessario approssimativamente) nella somma di matrici kxk, il che permette di rafforzare ulteriormente le formulazioni [A60].
Per migliorare l'efficienza dell'approccio sono state studiate versioni proiettate [A30] che permettono di salvaguardare una parte maggiore della struttura del problema originale, il che può risultare utile ad esempio nel caso di problemi su reti [C5] o per problemi relativi alla confidenzialità dei dati statistici [A42]. L'estensione di approcci di questo a problemi con struttura meno rigida è stata studiata in [A48]. Poiché l'approccio Approximated Projected Perspective Reformulation proposto può portare ad un deterioramento della valutazione ottenuta dal rilassamento, è stata proposta una tecnica per recuperare la piena potenza della valutazione fornita dal Rilassamento Prospettico utilizzando informazione duale [A54].
Le tecniche basate sulla Riformulazione Prospettica si sono dimostrate utili in un numero sorprendentemente alto di contesti diversi, tra cui problemi relativi all'energia, problemi relativi a reti di telecomunicazione la Sequential Convex MINLP Technique per la soluzione di problemi MINLP in cui gli elementi non convessi appaiono solamente come funzioni univariate [A62, A75], ed il "pruning" di reti neurali [A74].
Una linea di lavoro diversa ha riguardato invece lo sviluppo di algoritmi di programmazione dinamica a due stadi per la soluzione di problemi MINLP con particolare struttura "time-indexed", corrispondenti a problemi di schedulazione in cui la disponibilità di una risorsa in un istante di tempo influenza quella degli istanti immediatamente precedente e successivo [A16]. Ma, come a volte succede, due linee di ricerca apparentemente distanti possono essere unite fornendo un risultato superiore alla somma delle parti: combinando la formulazione sottostante all'algoritmo di programmazione dinamica con le tecniche di riformulazione prospettica si ottiene la prima formulazione "perfetta" per problemi di single-Unit Commitment con tutti i principali vincoli operativi e funzione costo nonlineare [A72], dimostrando anche un risultato generale di analisi di inviluppi convessi di problemi con particolare strutura che ha un suo interesse intrinseco. È interessante notare come una versione errata del risultato fosse stata pubblicata in precedenza [T6].
La ricerca prosegue in diverse direzioni, relative allo sfruttamento di ulteriori sorgenti di struttura nei problemi studiati, allo sviluppo di diverse classi di diseguaglianze valide [A29], all'applicazione dei risultati a diverse classi di problemi, alla ulteriore generalizzazione dei risultati, nonché allo sviluppo di metodi interamente diversi, quali euristiche "feasibility pump" [B4, A36, A70] o di altro tipo. Tutte queste linee di ricerca sono state, tra l'altro, finanziate da tre progetti PRIN (2009, 2012 e 2015), degli ultimi due dei quali sono stato coordinatore nazionale.

Problemi di Flusso single e Multicommodity

Una delle applicazioni delle tecniche algoritmiche sviluppate è stata a problemi di flusso Multicommodity [V1]; tali problemi, oltre all'interesse intrinseco, costituiscono una parte rilevante di molti modelli in ambito di problemi di trasporto o progetto di rete [A22, B1, A34, C7]. Gli approcci sviluppati hanno dimostrato di avere interessanti potenzialità, sia in sequenziale [A4] che in parallelo [A9, B2]. Allo scopo di realizzare tali approcci è stata proposta ed implementata un'interfaccia astratta per solutori di problemi di Flusso di Costo Minimo single-commodity, sono stati sviluppati o portati sotto tale interfaccia diversi codici efficienti [A12, A19, A20] e sono state studiate le caratteristiche di tali codici nel caso di riottimizzazione per cambio dei costi [A15].
Ulteriori sviluppi sono attesi sia dall'affinamento delle singole tecniche utilizzate che dalla combinazione di tecniche diverse.

Problemi di Network Design

Molti problemi di Network Design [B1 , B16] hanno una struttura simile a quella dei problemi di Flusso Multicommodity, o comunque adatta per l'applicazione delle tecniche di ottimizzazione a grandi dimansioni sviluppate. Per alcuni di questi problemi sono state ricavate efficienti valutazioni inferiori basate su tecniche Lagrangiane e problemi di flusso [A5, T1], eventualmente in congiunzione con varianti specializzate di algoritmi "Bundle" [A38]. In alternativa sono state utilizzate tecniche basate su riformulazioni 0/1 combinate con innovative tecniche di generazione simultanea di righe e colonne [A22]; opportunamente stabilizzate, queste tecniche danno origine a metodi di tipo Stabilized Structured Dantzig-Wolfe Decomposition [A37]. La flessibilità delle tecniche Lagrangiane ha consentito di proporre nuovi schemi di rilassamento "node-based" che permettono di scegliere tra un vasto panorama di approcci con diversi rapporti tra costo computazionale e qualità della valutazione fornita. In molti casi, i problemi di Network Design hanno una struttura che porta a Quasi-Separable Dantzig-Wolfe Reformulations, che possono essere sfruttate dal punto di vista computazionale [B13, B20].
Approcci basati sulla Riformulazione Prospettica si sono rivelati efficienti per problemi di Network Design con funzione obiettivo nonlineare [A48, A30, C5].
Una diversa linea di ricerca ha riguardato invece le tecniche per l'ottimizzazione sul politopo semimetrico [B3, A13], che hanno ricadute per le tecniche poliedrali per la soluzione di problemi di Network Loading.
Sono anche stati studiati problemi di Network Design con vincoli probabilistici, utilizzando tecniche di ottimizzazione robusta per produrre diverse approssimazioni convesse di tali vincoli e confrontandole tra loro dal punto di vista computazionale [C6].
La ricerca prosegue con lo sviluppo di euristiche e/o metodi enumerativi che sfruttino le tecniche proposte, e con l'affinamento delle tecniche stesse.

Problemi relativi all'energia

La progettazione e gestione dei sistemi energetici sono una fonte quasi inesauribile di modelli di ottimizzazione altamente sfidanti. Tra questi, i problemi di Unit Commitment di centrali elettriche rivestono un ruolo fondamentale nella gestione del sistema elettrico. Sono sempre stati problemi di grande scala, non convessi ed estremamente difficili da risolvere, specialmente per via del fatto che i vincoli operativi richiedono che ciò sia fatto in un tempo "irragionevolmente breve". In più, il recente aumento della produzione da energie rinnovabili ha significativamente incrementato il livello di incertezza nel sistema, rendendo il modello di Unit Commitment ideale un problema di grande scala, non convesso, ed incerto (stocastico, robusto, o con vincoli probabilistici), come discusso nel survey [A46] (ed in ancor maggiore dettaglio nella versione aggiornata [A59]).
Per tali problemi sono state sviluppate tecniche euristiche basate su Rilassamento Lagrangiano, sia per il caso del produttore monopolistico [A10, A21, C4] che per il caso del libero mercato [C2], che hanno dato buoni risultati, anche quando confrontate con metaeuristiche [C1]. Un nuovo algoritmo di programmazione dinamica a due stadi è stato proposto per la soluzione dei relativi sottoproblemi Lagrangiani nel caso in cui siano presenti "vincoli di rampa" [A16]; tale algoritmo si è dimostrato in grado di "guidare" efficacemente le euristiche Lagrangiane, permettendo di estendere tale tecnica anche ai problemi con vincoli di rampa [A21, C4]. Lo studio dei problemi di Unit Commitment ha anche suggerito una nuova classe di diseguaglianze valide per problemi di MINLP [A17] con particolare struttura, che si sono rivelate utili anche per modelli provenienti da applicazioni molto diverse quali l'ottimizzazione del portafoglio finanziario [A18]; di particolare interesse è l'uso di tali disuguaglianze per costruire modelli approssimati in grado di fornire buone soluzioni al problema in tempi rapidi con tecnologie MILP standard [A24], soprattutto se usate in combinazione con tecniche Lagrangiane [A32]. L'algoritmo di programmazione dinamica proposto in [A16] ha inoltre suggerito formulazioni "grandi ma molto accurate" del problema, che si sono dimostrate promettenti computazionalmente [B11, A72], portando anche alla dimostrazione di un risultato generale di analisi di inviluppi convessi che ha un suo interesse intrinseco (e del quale era stata pubblicata una versione errata [T6]). La combinazione di tecniche diverse è cruciale per risolvere versioni stocastiche del problema in grado di tener conto dell'incertezza inerente dei sistemi elettrici, quale ad esempio quella relativa alla produzione da fonti rinnovabili [A56]. Le sfide poste da questa specifica classe di problemi hanno portato allo sviluppo di una nuova procedura euristica di "primal recovery" per approcci basati sul rilassamento Lagrangiano [A66] che ci si può aspettare avere altre applicazioni in futuro.
Una diversa linea di ricerca ha riguardato lo sviluppo di modelli per problemi di ottimizzazione relativi alle Comunità Energetiche (EC), in particolare tenendo conto di aspetti quali l'"agency problem" e la corretta ripartizione dei ricavi tra i partecipanti alla comunità, utilizzando diversi approcci quali la teoria dei giochi cooperativi [A69] o l'ottimizzazione bilevel [C16]. Questa linea di ricerca ha portato ad interessanti sviluppi metodologici, tra cui la definizione dell'approccio generale Fair Least Core che, attraverso un innovativo schema di generazione di vincoli, permette di calcolare imputazioni "fair" ed efficienti per EC di dimensioni realistiche, migliorando in modo drastico le prestazioni degli approcci precedentemente noti che non erano in grado di scalare alle dimensioni richieste [A78].
Una linea di ricerca completamente diversa ha riguardato lo sviluppo di una variante innovativa del meccanismo standard Pay-as-Clear (PaC) per la risoluzione di mercati, ampiamente utilizzato nel settore energetico, con lo scopo di ottenere un certo grado di "disaccoppiamento" tra produttori (e, volendo, consumatori) di diverse tipologie [T8, A76]: il nuovo approccio Segmented Pay-as-Clear (SPaC) ha mostrato un buon potenziale per ottenere una significativa riduzione del costo totale di sistema senza compromettere i fondamentali segnali di prezzo a breve e lungo termine caratteristici dell'approccio PaC.
Un'ulteriore linea di ricerca ha riguardato lo sviluppo di metodi per l'ottimizzazione del piazzamento di turbine sottomarine [C19, A79].
La ricerca su questi problemi è stata anche finanziata da uno specifico Progetto Coordinato Agenzia2000 CNR, da un progetto PRIN 2005, da un progetto dell'Università di Pisa (AUTENS), da tre progetti del Gaspard-Monge Program for Optimization and Operations Research (2013—2021), dal progetto H2020 plan4res e dalla COST Action TD1207 "Mathematical Optimization in the Decision Support Systems for Efficient and Robust Energy Networks", dei quali sono stato responsabile scientifico. In particolare, nella COST Action ho coordinato lo sviluppo di una Wiki sull'ottimizzazione nell'energia, che in seguito è diventata un libro. Sono stato inoltre l'estensore originale della pagina di Wikipedia "Unit commitment problem in electrical power production". La ricerca prosegue sia dal punto di vista modellistico che algoritmico. Di particolare interesse appare la possibilità di sviluppare modelli innovativi del problema, ed i corrispondenti algoritmi risolutivi, che tengano conto di alcuni vincoli che finora sono state modellati solamente in modo approssimato per via della necessità di rendere i modelli computazionalmente trattabili.

Problemi di Max-Cut

Una formulazione del problema di Max-Cut è quella che utilizza le cycle (triangle) inequalities; l'insieme di queste diseguaglianze definisce il politopo semimetrico. Selezionando opportunamente un sottinsieme di queste diseguaglianze si ottiene il politipo semimetrico radicato, sul quale il problema di ottimzzazione lineare è facilmente risolubile utilizzando tecniche di flusso di costo minimo [B3, T3]. Combinando gli efficienti algorimi per questo problema con tecniche Lagrangiane [A13] si costruiscono algoritmi in grado di ottimizzare sul politopo semimetrico più efficientemente rispetto ai metodi standard di Programmazione Lineare. La ricerca prosegue, sia cercando di migliorare ulteriormente l'efficienza delle tecniche risolutive che utilizzandole all'interno di approcci esatti o approssimati per il problema.

Problemi di schedulazione di veicoli ed equipaggi

Questi problemi vengono usualmente formulati come Set Partitioning di dimensioni estremamente elevate; per questo tipo di formulazione sono state sviluppate euristiche basate sulla generazione di colonne [N1], in particolare sfruttando tecniche Lagrangiane [A2, A3] per la soluzione efficiente dei Master Problems. In questo contesto appare di particolare importanza la "stabilizzazione" della generazione di colonne, che può essere ottenuta ad esempio mediante termini di stabilizzazione che rispettino opportune proprietà teoriche [A7]; ciò si dimostra molto utile su molti problemi reali quali la schedulazione di veicoli multi-deposito e la schedulazione di equipaggi [A23]. Casi particolari, importanti per alcune applicazioni, sono quelli in cui le colonne (cammini) hanno forme specifiche che possono essere sfruttate per rendere gli approcci più efficienti [A57], anche di tipo generazione di colonne [C15]; in effetti il problema di "pricing" della generazione di colonne suggerisce una formulazione compatta che ha ottime prestazioni [A67]. Nell'ambito del trasporto pubblico urbano tali problemi sono spesso solo uno dei passi necessari per la pianificazione del servizio; pertanto è utile studiare modelli che combinano più aspetti, quali ad esempio la schedulazione dei veicoli e la costruzione (simultanea) di tabelle orarie [A64]. La ricerca prosegue, siaccon lo studio delle proprietà teoriche di altre tecniche di stabilizzazione, sia con lo studio del comportamento computazionale in pratica, finalizzato ad incrementare le prestazioni degli algoritmi, sia, infine, con lo studio di formulazioni alternative in contesti specifici.

Problemi relativi a reti di telecomunicazione

I problemi relativi a reti di telecomunicazione hanno spesso, ma non sempre, una forte struttura di flusso o multiflusso. Ad esempio, alcuni problemi di instradamento in una rete di telecomunicazione possono essere scritti come varianti minime di problemi di flusso multicommodity, e quindi risolti efficientemente anche con semplici tecniche di PL [A34, C7].
Un problema specifico dei problemi di telecomunicazione è che la matrice delle domande di comunicazione spesso non è nota con precisione. Ciò da origine ad un insieme di problemi complessi in cui le decisioni di instradamento dipendono dall'effettiva realizzazione delle domande. Alcuni di questi casi (in cui i problemi risultano in effetti essere facili) sono stati studiati in [A31].
I problemi di instradamento in reti di telecomunicazione packed-based con vincoli sul massimo ritardo danno origine a problemi di flusso con vincoli nonlineari; tali problemi sono NP-hard già anche con un solo flusso instradato su un singolo cammino, e quindi necessitano, per essere risolti efficientemente, di tecniche modellistiche ed algoritmiche appropriate [A45], in particolare quando siano usati modelli molto dettagliati del processo di schedulazione nei routers della rete [A51]. I modelli MINLP sviluppati sono stati testati con dettagliate simulazioni di rete, mostrandosi molto promettenti per migliorare l'utilizzazione delle risorse di rete [A43, A50], anche se alcune analisi suggeriscono che la funzione obiettivo tipicamente usata non rispecchi pienamente l'obiettivo di migliorare le performances di rete [C14]. Un approccio in qualche modo analogo (ma anche piuttosto diverso) può essere usato per calcolare il ritardo al caso pessimo (worst-case delay) per l'accesso ad un banco di memoria DRAM [A71], anche se in questo caso il grafo è quello delle transizioni del controller DRAM e sono necessari complessi vincoli aggiuntivi rispetto alla struttura di flusso.
Non tutti i problemi relativi a reti di telecomunicazione, comunque, hanno una predominante struttura di flusso. Ad esempio, i problemi di schedulazione di risorse in reti cellulari [A58, B7, C12, C10, C17] hanno strutture molto diverse, per le quali tecniche di generazione di patterns possono essere efficienti, considerata la necessità di ottenere buone soluzioni in tempi molto rapidi. Valutare l'utilità in pratica di algoritmi di schedulazione avanzati richiede lo sviluppo di sofisticati ambienti di simulazione [C11].
Inoltre, i problemi relativi all'Internet-of-Things possono richiedere sofisticate combinazioni di comunicazioni broadcast e punto-punto, che danno origine a formulazioni di Programmazione Nonlineare Mista-Intera estremamente complesse che richiedono approcci ad hoc, come quelli Branch-and-Bound basati su rilassamento Lagrangiano [B12].

Altri problemi e metodologie

Infine, sono state studiate diverse altre applicazioni e metodologie:

Aggiornamento: 09/01/2025