Teoria ed applicazioni reali dell'Ottimizzazione Combinatoria

Cluster di dipartimento

  • Ricerca operativa

Descrizione

I problemi di ottimizzazione combinatoria si presentano in una quantità impressionante di contesti diversi, sia di natura pratica che teorica. Nelle applicazioni reali, l'ottimizzazione combinatoria è necessaria alla soluzione di problemi di logistica, pianificazione, routing, schedulazione, turnazione di personale, disegno di reti, trasporto di merci e loro stoccaggio, ecc. Nel campo della matematica discreta, numerosi problemi combinatorici rivestono un notevole interesse teorico. In particolar modo, molti di tali problemi sono definiti nell'ambito della teoria dei grafi.

Quasi invariabilmente, I problemi di ottimizzazione combinatoria di cui ci occupiamo risultano molto complessi da un punto di vista computazionale (in termini tecnici, sono NP-hard). La soluzione di questi problemi richiede algoritmi sofisticati, solitamente basati sulla modellazione del problema con tecniche di programmazione matematica. Il nostro gruppo si occupa dello studio di problemi di questa natura principalmente in relazione alla schedulazione di macchine e personale in ambito produttivo/industriale e ad applicazioni nel campo della biologia molecolare  quali predizione e confronto di strutture proteiche tridimensionali, calcolo di distanze evolutive,  estrazione di pattern comuni, ecc.. Per risolvere tali problemi utilizziamo tipicamente un approccio di Programmazione Lineare Intera, con tecniche sofisticate di branch-and-bound tramite piani di taglio per pervenire alla soluzione esatta di istanze di interesse reale in tempi ragionevoli. Per problemi particolarmente difficili utilizziamo inoltre tecniche euristiche, quali Tabu Search o Algoritmi Genetici,  che pur non garantendo la soluzione ottima sono mediamente in grado di produrre soluzioni  di alta qualità.  Un ulteriore filone di ricerca di cui ci occupiamo è lo studio e l'avanzamento della teoria di base della programmazione matematica, come ad esempio l'utilizzo di diseguaglianze di uso generale da noi introdotte (local search inequalities) nell'ambito di vari problemi, o la riformulazione polinomiale (compatta) di modelli con un numero esponenziale di vincoli e/o variabili. Siamo inoltre interessati all'area degli algoritmi di approssimazione e all'utilizzo della Programmazione Intera per affrontare problemi aperti/congetture su strutture combinatoriche opportune.

Linee di ricerca

  • Problemi di scheduling, vehicle routing e turnazione.
  • Problemi di computational biology, su sequenze genomiche e strutture proteiche.
  • Riformulazione compatta di modelli esponenziali.
  • Diseguaglianze valide e piani di taglio nel rafforzamento dei modelli.

Settori ERC

  • PE1_15 Generic statistical methodology and modelling
  • PE1_21 Application of mathematics in sciences

Etichette libere

  • Combinatorial Optimization Mathematical Programming Computational Biology
  • Scheduling Approximation Algorithms

Componenti

Giuseppe LANCIA
Franca RINALDI
Paolo SERAFINI
 

In base alla circolare d'Amministrazione n. 33/1998 si responsabilizzano le persone in indirizzo a verificare la correttezza dei dati inseriti e ad effettuare le dovute comunicazioni di variazione alla Direzione Risorse Umane e Affari generali (DARU) per assicurare il costante aggiornamento dei dati nel tempo, trasmettendo (esclusivamente per posta elettronica) l'esito delle verifiche effettuate agli indirizzi di seguito riportati: