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

RESEARCH PROGRAM

italiano - inglese
Research Units
Similar research programs:
Scientific and education field classification
International Patent Classification
Geographical classification
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.
Keywords
ROBUST OPTIMIZATION, STOCHASTIC PROGRAMMING, DISCRETE SIMULATION, INTEGER LINEAR PROGRAMMING, HEURISTIC ALGORITHMS, COMPUTATIONAL ANALYSIS, TELECOMMUNICATION NETWORKS, NETWORK ALGORITHMS, TRANSPORTATION NETWORK SOFTWARE

Models and algorithms for robust network optimization

Università degli Studi di Padova
Abstract
The project is aimed at advancing the state of the art in the research and application of robust network optimization problems. Besides developing individual approaches to specific problems, and testing them in real-world applications, the project will focus on:

- finding algebraic and structural commonalities among different applications;

- finding algorithmic ways to exploit a common structure that can be re-used on several different applications;

- developing ways for combining different forms of robustness;

- developing innovative algorithmic approaches for large-scale optimization which can be also used in contexts not necessarily related to robust network optimization;

- implementing a common and well-engineered software layer which facilitates the above processes.

We intend to tackle several different but interconnected facets of managing uncertainty in networks, each requiring specific skills and algorithmic tools. In particular, we intend to pursue all the following aspects:

- *robust* models and algorithms, i.e., approaches aimed at obtaining solutions which are designed to stand a set of unforeseen events without becoming infeasible or too costly;

- *scenario* (also known as *adjustable robust*) models and algorithms, i.e., approaches where the solution covers not only the decisions relative to the normal functioning of the network (nominal >>>

Principal Investigator
Matteo Fischetti Università degli Studi di PADOVA
Research Objectives
The objective of this project is to exploit and to coordinate the skills of the participating Research Units, in order to advance the theoretical understanding and the development of algorithmic approaches for optimization problems related to planning, management and operations of networks under uncertainty, as well as their application in actual operating environments.

Many real-world systems are extremely complex, and they require appropriate quantitative techniques to be designed, maintained and operated safely, effectively and efficiently. Networks are a main example of such a situation: hydro networks, land/sea/air transportation networks (which are generally interconnected), and communication networks all require specialized decision support systems, mostly based on mathematical models solved by computer programs, to aid decision makers in all stages of the system life, from planning (either of the network itself or of its technological components) to routine operations.

These decision support systems often require the solution of extremely challenging optimization problems. The complexity of these problems is mainly due to two factors:

- some decisions have to be taken in the face of a high level of uncertainty regarding the value of some crucial input data; such an uncertainty may concern either the current status of the system, which is unknown (maybe estimated by a simulation or a discretization process), or future >>>

Timescale
24 months
National and international background
Networks are pervasive in everyday life. The electrical network, the hydro network, the transportation networks---in their several modes: air transportation, land transportation (cars/buses/trucks/trains), sea transportation, and their inter-modal connections---and the communication networks are the backbone of modern societies. Their effective and efficient operation is a fundamental prerequisite for the normal functioning of almost every aspect of modern life.

Several aspects of the routine functioning of networks require the solution of optimization problems, which are often "bolted in" the very fabric of the network. For instance, the routing of the Internet traffic is typically based on the solution of suitable shortest path problems, which have to take into account several factors as different types of traffic (multimedia, high revenue, ...), Quality of Service requirements, and network faults. For some networks, the availability of proper mathematical models is crucial for safe operations; examples are the Optimal Power Flow models that need to be solved to assess stability of an electrical network under specific load conditions at nodes, and the sectorization models that help in the assignment of time slots in air traffic control to maximize safety of airborne operations. In several other cases, computer-aided quantitative decision support systems, based on mathematical models solved by computer programs, have gradually assumed a central role >>>