Vai al contenuto| Home page|

   Ti trovi in: HOME »Programmi, progetti e risultati »I progetti »PRIN - Programmi di ricerca di Rilevante Interesse Nazionale»Programma di ricerca
INIZIO_TESTO_DA_INDICIZZARE

PROGRAMMA DI RICERCA 2006

italiano - english
Unità di Ricerca
Programmi di ricerca simili:
Classificazione scientifico-disciplinare
Classificazione brevettuale
Classificazione geografica
Bibliografia
[AABP05] A. Altin, E. Amaldi, Belotti, M.C. Pinar "Provisioning Virtual Private Networks under Traffic Uncertainty" Proc. INOC2005, 2005

[AOPS03] R.K. Ahuja, J.B. Orlin, S. Pallottino, M.G. Scutellà "Dynamic Shortest Paths Minimizing Travel Times and Costs" Networks 41, 197-205, 2003

[AOPSS04] R.K. Ahuja, J.B. Orlin, S. Pallottino, M.P. Scaparra, M.G. Scutellà "A multi-exchange heuristic for the single source capacitated facility location problem" Man. Sci. 50, 749-760, 2004

[BT00] L.L. Bailey, R.C. Thompson ÒThe Effects of Performance Feedback on Air Traffic Control Team Coordination: A Simulation StudyÓ, U.S. Dept. of Federal Aviation Admin, 2000.

[BK02] W. Ben-Ameur, H. Kerivin "Routing of Uncertain Demands" Optimization and Engineering 3, 283-313, 2005

[BM00] D. Bienstock, G. Muratore "Strong inequalities for capacitated survivable network design problems" Math. Prog. 89, 127-147, 2000

[BBN06] A. Ben-Tal, S. Boyd, A. Nemirovski "Extending Scope of Robust Optimization: Comprehensive Robust Counterparts of Uncertain Problems" Math. Prog. 107, 63-89, 2006

[BTN99] A. Ben-Tal, A. Nemirovski "Robust solutions of uncertain linear programs" Op. Res. Letters 25, 1-13, 1999

[BTN02] A. Ben-Tal, A. Nemirovsk "Robust optimization-methodology and applications" Math. Prog. 92, 453-480, 2002

[BTGGN04] A. Ben-Tal, A. Goryashko, E. Guslitzer, A. Nemirovski "Adjustable robust solutions of uncertain linear programs" Math. Prog. 99, 351-376, 2004

[BPS04] D. Bertsimas, D. Pachamanova, M. Sim "Robust linear optimization under general norms" Op. Res. Letters 32, 510-516, 2004

[BS03] D. Bertsimas, M. Sim "Robust discrete optimization and network flows" Math. Prog. 98, 49-71, 2003

[BS04] D. Bertsimas, M. Sim "The Price of Robustness" Op. Res. 52, 35-53, 2004

[BS00] D. Bertsimas, S. Stock Patterson "The Traffic Flow Management Rerouting Problem in Air Traffic Control: A Dynamic Network Flow Approach" Trans. Sci. 34, 239-255, 2000

[BOS03] G. Brightwell, G. Oriolo, F.B. Shepherd "Reserving Resilient Capacity in a Network" Networks 41, 87-96, 2003

[CFT02] A. Caprara, M. Fischetti, P. Toth "Modelling and Solving the Train Timetabling Problem" Op. Res. 50, 851-861, 2002

[CF00] J. Castro, A. Frangioni "A Parallel Implementation of an Interior-Point Algorithm for Multicommodity Network Flows" LNCS "Vector and Parallel Processing, VECPAR 2000", Springer-Verlag, 2000

[CF03] Cappanera, A. Frangioni "Symmetric and Asymmetric Parallelization of a Cost-Decomposition Algorithm for Multi-Commodity Flow Problems" INFORMS JOC 15, 369-384, 2003

[CS05] P. Cappanera, M.G. Scutellà "Balanced paths in acyclic networks: tractable cases and related approaches" Networks 45, 104-111, 2005

[COSS06] C. Chekuri, G.Oriolo, M.G. Scutellà, F.B. Shepherd "Hardness of Robust Network Design" Networks, to appear, 2006

[CF05] G. Codato, M. Fischetti "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming" Op. Res., to appear, 2006

[CFO03] G. Conte, F. Ferlito, G. Oriolo, F. Razza, R. Sabella, M. Settembre "A Multilayer Solution for Path Provisioning in New-Generation Optical/MPLS Networks", J. of Lightwave Technology 21, 1141-55, 2003

[CFG01] T.G. Crainic, A. Frangioni and B. Gendron "Bundle-based Relaxation Methods for Multicommodity Capacitated Fixed Charge Network Design Problems" Disc. Appl. Math., 112, 73-99, 2001

[CGD93] T.G. Crainic, M. Gendreau, P. Dejax "Dynamic and stochastic models for the allocation of empty containers" Op. Res. 41, 102-126, 1993

[DIO04] P. D'Aprile, P. Iovanna, G. Oriolo, R. Sabella "Strategy for Dynamic Routing and Grooming of Data Flows into Lightpaths in New Generation Optical Network Based on the GMPLS Paradigm" Photonic Network Communications 7, 131-144, 2004

[EGOS05] F. Eisenbrand, F. Grandoni, G. Oriolo, M. Skutella "New Approaches for Virtual Private Network Design" Proc. 32nd ICALP, 2005

[FL03] M. Fischetti, A. Lodi "Local Branching" Math. Prog. 98, 23-47, 2003

[FL05] M. Fischetti, A. Lodi "Optimizing over the first Chvàtal closure" in IPCO2005 (M. Juenger and V. Kaibel eds.), LNCS 3509, Springer-Verlag, 12-22, 2005

[FPS04] M. Fischetti, C. Polo, M. Scantamburlo "A Local Branching Heuristic for Mixed-Integer Programs with 2-Level Variables" Networks 44, 61-72, 2004

[FS05] M. Fischetti, C. Saturni "Mixed-Integer Cuts from Cyclic Groups" Math. Prog., to appear, 2006

[Fr02] A. Frangioni "Generalized Bundle Methods" SIAM J. Opt. 13, 117-156, 2002

[Fr05] A. Frangioni "About Lagrangian Methods in Integer Optimization" Annals of Op. Res. 139, 163-193, 2005

[FG99] A. Frangioni, G. Gallo "A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min Cost Flow Problems" INFORMS JOC 11, 370-393, 1999

[FG04] A. Frangioni, C. Gentile "New Preconditioners for KKT Systems of Network Flow Problems" SIAM J. Opt. 14, 894-913, 2004

[FG06a] A. Frangioni, C. Gentile "Perspective Cuts for a class of convex 0-1 Mixed Integer Programs" Math. Prog. 106, 225-236, 2006

[FG06b] A. Frangioni, C. Gentile "Solving nonlinear single-unit commitment problems with ramping constraints" Op. Res., to appear, 2006

[FLR05] A. Frangioni, A. Lodi, G. Rinaldi "New approaches for optimizing over the semimetric polytope" Math. Prog. 104, 375-388, 2005

[FM06] A. Frangioni, A. Manca "A Computational Study of Cost Reoptimization for Min Cost Flow Problems" INFORMS JOC 18, 61-70, 2006

[FSN04] A. Frangioni, M.G. Scutellà, E. Necciari "A Multi-exchange Neighborhood for Minimum Makespan Machine Scheduling Problems" J. of Combinatorial Opt. 8, 195-220, 2004

[GSZ06] S. Giulini, M. Sanguineti, R. Zoppoli "Approximation schemes for functional optimization problems" JOTA, 2006

[ILO06] G. Italiano, S. Leonardi, G. Oriolo "Design of Trees in the Hose Model: the balanced case", Op. Res. Letters, to appear, 2006

[KW94] P. Kall, S.W. Wallace "Stochastic Programming" John Wiley and Sons, 1994

[Keta05] A. Koster, A. Zymolka, M. Jager, R. Hulsermann "Demand-wise shared protection for meshed optical networks" J. of Network and Syst. Management, 13, 35-55, 2005

[KS05] V. Kurkova, M. Sanguineti "Error estimates for approximate optimization by the extended ritz method" SIAM J. Optimiz. 15, 461-487, 2005

[LSV98] A. Lisser, R. Sarkissian, J.-Ph. Vial "Mid-range Planning of Survivable Telecommunications Networks: Joint Optimal Synthesis of Base and Spare Network Capacities" HEC/Logilab Technical Report 98.14, 1998

[OZDM05] A. Olivo, P. Zuddas, M. Di Francesco, A. Manca "An operational model for empty container management" Marit. Econ. & Log. 7, 199-222, 2005

[PS97] S. Pallottino, M.G. Scutellà "Dual algorithms for the shortest path tree problem" Networks 29, 125-133, 1997

[PS03] S. Pallottino, M.G. Scutellà "A new algorithm for reoptimizing shortest paths when the arc costs change" Op. Res. Letters 31, 149-160, 2003

[PSZ05] S. Pallottino, G.M. Sechi, P. Zuddas "A DSS for water resources management under uncertainty by scenario analysis" Envir. Modelling & Soft. 20, 1031-1042, 2005

[RW91] R.T. Rockafellar, R.J-B. Wets "Scenarios and Policy Aggregation in Optimization under Uncertainty" Math. of Op. Res. 16, 119-147, 1991

[RJN03] J.M. Rosenberger, E.L. Johnson, G.L. Nemhauser "Rerouting Aircraft for Airline Recovery" Trans. Sci. 37, 408-421, 2003

[S03] M.G. Scutellà "An approximation algorithm for computing longest paths" EJOR 148, 584-590, 2003

[S05] M.G. Scutellà "The maximum cut congestion problem" Proc. INOC2005, 2005

[Setal98] P. Soriano, C. Wynants, R. Seguin, M. Labbe, M. Gendreau, B. Fortz "Design and dimensioning of survivable SDH/SONET networks" in Telecommunications Network Planning (B. Sanso and P. Soriano eds.), Kluwer, 147-168, 1998

[Wa00] S.W. Wallace "Decision making under uncertainty: is sensitivity analysis of any use?" Op. Res. 48, 20-25, 2000

[ZPS01] R. Zoppoli, T. Parisini, M. Sanguineti "Approximating networks and extended Ritz method for the solution of functional optimization problems" JOTA 112, 403-440, 2001.
Parole Chiave
OTTIMIZZAZIONE ROBUSTA, PROGRAMMAZIONE STOCASTICA, SIMULAZIONE DISCRETA, PROGAMMAZIONE LINEARE INTERA, ALGORITMI EURISTICI, ANALISI COMPUTAZIONALE, RETI DI TELECOMUNIZIONE, ALGORITMI SU RETI, SOFTWARE PER RETI DI TRAPOSTO

Modelli ed algoritmi per l'ottimizzazione robusta delle reti

Università degli Studi di Padova
Abstract
Lo scopo del progetto è quello di far progredire lo stato dell'arte della ricerca e delle applicazioni dei problemi di ottimizzazione robusta di rete. Oltre a sviluppare approcci individuali per problemi specifici e testarli nelle applicazioni reali, il progetto si concentrerà su:

- scoprire elementi algebrici e strutturali comuni a differenti applicazioni;

- trovare approcci algoritmici in grado di sfruttare le strutture comuni che possano essere riutilizzate in molte differenti applicazioni;

- sviluppare modi di combinare le differenti forme di robustezza;

- sviluppare approcci algoritmici innovativi per l'ottimizzazione di grande dimensione che possano essere utilizzati in contesti non necessariamente collegati all'ottimizzazione robusta;

- implementare un'interfaccia comune e ben ingegnerizzata che faciliti i processi sopra indicati.

Intendiamo affrontare molti aspetti, diversi ma interconessi, della gestione dell'incertezza nelle reti, ognuno dei quali richiede specifiche capacità e strumenti algoritmici. Intendiamo studiare, in particolare, tutti i seguenti aspetti:

- modelli e algoritmi *robusti*, ossia approcci il cui obiettivo è ottenere soluzioni che siano costruite per sopportare un insieme di eventi imprevisti senza diventare inammissibili o troppo costose;

- modelli e algoritmi *a scenari* (o *modificabili*), ossia >>>

Coordinatore Scientifico del Programma di Ricerca
Matteo Fischetti Università degli Studi di PADOVA
Obiettivo del Programma di Ricerca
L'obiettivo di questo progetto è sfruttare e coordinare le competenze dei partecipanti alle Unità di Ricerca, in modo da migliorare la comprensione teorica e lo sviluppo di approcci algoritmici per problemi di ottimizzazione riguardanti la pianificazione, la gestione e l'operatività di reti soggette ad incertezza, nonché la loro applicazione negli attuali ambienti operativi.

Molti sistemi reali sono estremamente complessi, e richiedono appropriate tecniche quantitative per essere progettati, gestiti e fatti funzionare in modo sicuro, efficiente ed efficace. Le reti sono un importante esempio di questa situazione: le reti idriche, le reti di trasporto terrestre, marino ed aereo (che sono generalmente interconnesse), e le reti di comunicazione, richiedono tutte sistemi di supporto alle decisioni specializzati, per la maggior parte basati su modelli matematici risolti da programmi informatici, per aiutare a prendere decisioni in tutte le fasi del ciclo vita del sistema: dalla pianificazione (sia della rete stessa che dei suoi componenti) alle operazioni quotidiane.

Questi sistemi di supporto alle decisioni spesso richiedono di risolvere problemi di ottimizzazione estremamente difficili. La complessità di questi problemi deriva principalmente da due fattori:

- alcune decisioni devono essere prese in presenza di un'elevata incertezza sui valori dei dati di input fondamentali; tale incertezza può riguardare sia lo stato >>>

Durata
24 mesi
Base di partenza scientifica nazionale o internazionale
Le reti sono presenti in molti aspetti della vita quotidiana. La rete elettrica, la rete idrica, le reti di trasporto---dei diversi tipi: aereo, terrestre (auto, bus, camion, treni) e marittimo, con le loro connessioni intermodali---e le reti di telecomunicazione formano sono la spina dorsale della società moderna. Il funzionamento efficace ed 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, che sono spesso parte integrante della struttura fondamentale delle reti stesse. Ad esempio, l'instradamento del traffico su internet è tipicamente basato sulla soluzione di opportuni problemi di cammino minimo che devono tener conto di diversi 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; esempi sono modelli di Optimal Power Flow che devono essere risolti per controllare la stabilità di una rete elettrica date specifiche condizioni di carico ai nodi, e 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 quantitativi di supporto >>>