TY - GEN A1 - Giovanidis, Anastasios A1 - Brueck, Stefan A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Hartanto Tanzil, Vicky T1 - A 0-1 Program for Minimum Clustering in Downlink Base Station Cooperation N2 - Base station cooperation in the downlink of cellular systems has been recently suggested as a promising concept towards a better exploitation of the communication system physical resources. It may offer a high gain in capacity through interference mitigation. This however, comes at a cost of high information exchange between cooperating entities and a high computational burden. Clustering of base stations into subgroups is an alternative to guarantee such cooperation benefits in a lower scale. The optimal definition of clusters, however, and a systematic way to find a solution to such problem is not yet available. In this work, we highlight the combinatorial nature of the problem, exploit this to describe the system of users and base stations as a graph and formulate a pure 0-1 program. Its solution suggests a cost optimal way to form clusters and assign user subsets to them. T3 - ZIB-Report - 11-19 KW - Wireless Communications KW - Base Station Cooperation KW - 0-1 Program Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12776 ER - TY - GEN A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio T1 - A new theoretical framework for Robust Optimization under multi-band uncertainty N2 - We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks. T3 - ZIB-Report - 13-61 KW - Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42644 UR - http://www.springer.com/business+%26+management/operations+research/book/978-3-319-00794-6 SN - 1438-0064 ER - TY - GEN A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - Scheduling technology migration in WDM Networks N2 - The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/). T3 - ZIB-Report - 13-62 KW - Scheduling, Extended Formulations, Network Migration, WDM Networks Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42654 UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6507677&isnumber=6507670 SN - 1438-0064 ER - TY - GEN A1 - Zakrzewska, Anna A1 - D'Andreagiovanni, Fabio A1 - Ruepp, Sarah A1 - Berger, Michael S. T1 - Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks N2 - We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension. Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR. T3 - ZIB-Report - 13-63 KW - Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42675 UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6576416&isnumber=6576384 SN - 1438-0064 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - Multiband Robust Optimization and its Adoption in Harvest Scheduling N2 - A central assumption in classical optimization is that all the input data of a problem are exact. However, in many real-world problems, the input data are subject to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal solutions that are actually suboptimal or even infeasible. Robust optimization offers a remedy for optimization under uncertainty by considering only the subset of solutions protected against the data deviations. In this paper, we provide an overview of the main theoretical results of multiband robustness, a new robust optimization model that extends and refines the classical theory introduced by Bertsimas and Sim. After introducing some new results for the special case of pure binary programs, we focus on the harvest scheduling problem and show how multiband robustness can be adopted to tackle the uncertainty affecting the volume of produced timber and grant a reduction in the price of robustness. T3 - ZIB-Report - 13-76 KW - Data Uncertainty KW - Robust Optimization KW - Multiband Robustness KW - Harvest Scheduling Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43380 SN - 1438-0064 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Felici, Giovanni A1 - Lacalandra, Fabrizio T1 - Revisiting the use of Robust Optimization for optimal energy offering under price uncertainty N2 - We propose a new Robust Optimization method for the energy offering problem of a price-taker generating company that wants to build offering curves for its generation units, in order to maximize its profit while taking into account the uncertainty of market price. Our investigations have been motivated by a critique to another Robust Optimization method, which entails the solution of a sequence of robust optimization problems imposing full protection and defined over a sequence of nested subintervals of market prices: this method presents a number of issues that may severely limit its application and computational efficiency in practice and that may expose a company to the risk of presenting offering curves resulting into suboptimal or even infeasible accepted offers. To tackle all such issues, our method provides for solving one single robust counterpart, considering an intermediate level of protection between null and full protection, and to make energy offers at zero price, practically eliminating the risk of non-acceptance. Computational results on instances provided by our industrial partners show that our new method is able to grant a great improvement in profit. T3 - ZIB-Report - 15-61 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57128 SN - 1438-0064 N1 - Fabio D'Andreagiovanni is First Author ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Mett, Fabian A1 - Pulaj, Jonad T1 - An (MI)LP-based Primal Heuristic for 3-Architecture Connected Facility Location in Urban Access Network Design N2 - We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks integrating wired and wireless technologies. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage represented through signal-to-interference ratios. Since the problem can prove very challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic that combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver. T3 - ZIB-Report - 15-62 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57139 SN - 1438-0064 ER - TY - GEN A1 - D'Andreagiovanni, Fabio T1 - Revisiting wireless network jamming by SIR-based considerations and Multiband Robust Optimization N2 - We revisit the mathematical models for wireless network jamming introduced by Commander et al. (2007,2008): we first point out the strong connections with classical wireless network design and then we propose a new model based on the explicit use of signal-to-interference quantities. Moreover, to ad- dress the uncertain nature of the jamming problem and tackle the peculiar right-hand-side (RHS) uncertainty of the corresponding model, we propose an original robust cutting-plane algorithm drawing inspiration from Multiband Robust Optimization. Finally, we assess the performance of the proposed cutting plane algorithm by experiments on realistic network instances. T3 - ZIB-Report - 15-12 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57728 SN - 1438-0064 N1 - Published in Optimization Letters 9 (8), 1495-1510, 2015 (First online: 24 December 2014). The final publication is available at Springer http://dx.doi.org/10.1007/s11590-014-0839-2. ER - TY - GEN A1 - Bauschert, Thomas A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Koster, Arie M.C.A. A1 - Kutschka, Manuel A1 - Steglich, Uwe T1 - Network Planning under Demand Uncertainty with Robust Optimization N2 - The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties. T3 - ZIB-Report - 13-59 KW - Network Design, Demand Uncertainty, Robust Optimization, Telecommunications Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42557 SN - 1438-0064 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Mannino, Carlo T1 - An Optimization Model for WiMAX Network Planning and Optimization T2 - WiMAX Network Planning and Optimization Y1 - 2009 SN - 978-1-4200-6662-3 SP - 369 EP - 386 PB - Auerbach Publications ER - TY - JOUR A1 - D'Andreagiovanni, Fabio A1 - Mannino, Carlo A1 - Sassano, Antonio T1 - GUB Covers and Power-Indexed Formulations for Wireless Network Design JF - Management Science Y1 - 2013 U6 - https://doi.org/10.1287/mnsc.1120.1571 VL - 59 IS - 1 SP - 142 EP - 156 ER - TY - JOUR A1 - D'Andreagiovanni, Fabio T1 - Pure 0-1 programming approaches to wireless network design JF - 4OR Y1 - 2012 U6 - https://doi.org/10.1007/s10288-011-0162-z VL - 10 IS - 2 SP - 211 EP - 212 ER - TY - JOUR A1 - Dely, Peter A1 - D'Andreagiovanni, Fabio A1 - Kassler, Andreas T1 - Fair Optimization of Mesh-Connected WLAN Hotspots JF - Wireless Communications and Mobile Computing Y1 - 2013 U6 - https://doi.org/10.1002/wcm.2393 VL - 15 IS - 5 SP - 924 EP - 946 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Mannino, Carlo A1 - Sassano, Antonio T1 - Negative Cycle Separation in Wireless Network Design T2 - Network Optimization - INOC 2011 Y1 - 2011 U6 - https://doi.org/10.1007/978-3-642-21527-8_7 VL - 6701 SP - 51 EP - 56 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio T1 - On Improving the Capacity of Solving Large-scale Wireless Network Design Problems by Genetic Algorithms T2 - Applications of Evolutionary Computation - EvoApplications 2011 Y1 - 2011 U6 - https://doi.org/10.1007/978-3-642-20520-0_2 VL - 6625 SP - 11 EP - 20 ER - TY - JOUR A1 - Bauschert, Thomas A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Koster, Arie M.C.A. A1 - Kutschka, Manuel A1 - Steglich, Uwe T1 - Network planning under demand uncertainty with robust optimization JF - IEEE Communications Magazine Y1 - 2014 U6 - https://doi.org/10.1109/MCOM.2014.6736760 VL - 52 IS - 2 SP - 178 EP - 185 ER - TY - CHAP A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - Robust optimization under multiband uncertainty T2 - CTW 2013 Y1 - 2013 SP - 35 EP - 38 ER - TY - CHAP A1 - Zakrzewska, Anna A1 - D'Andreagiovanni, Fabio A1 - Ruepp, Sarah A1 - Berger, Michael S. T1 - Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks T2 - Proceedings of the 11th International Symposium on Modeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt 2013) - RAWNET/WNC3’13 Y1 - 2013 SP - 652 EP - 658 ER - TY - GEN A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio T1 - Robust Optimization under Multiband Uncertainty T2 - 2013 Mixed Integer Programming Workshop - MIP 2013 Y1 - 2013 ER - TY - CHAP A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - Scheduling technology migration in WDM Networks T2 - Photonic Networks, 14. 2013 ITG Symposium. Proceedings Y1 - 2013 SP - 1 EP - 5 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - Multiband Robust Optimization and its Adoption in Harvest Scheduling T2 - Proc. of FORMATH 2013 Y1 - 2014 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A hybrid primal heuristic for Robust Multiperiod Network Design T2 - EvoApplications 2014 Y1 - 2014 ER - TY - CHAP A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - WDM Fiber Replacement Scheduling T2 - Proceedings of INOC 2013 Y1 - 2013 U6 - https://doi.org/10.1016/j.endm.2013.05.092 VL - 41 SP - 189 EP - 196 ER - TY - CHAP A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio T1 - A New Theoretical Framework for Robust Optimization Under Multi-Band Uncertainty T2 - Operations Research Proceedings 2012 Y1 - 2014 U6 - https://doi.org/10.1007/978-3-319-00795-3_17 SP - 115 EP - 121 ER - TY - CHAP A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - 0-1 Multiband Robust Optimization T2 - Operations Research Proceedings 2013 Y1 - 2013 ER - TY - BOOK A1 - D'Andreagiovanni, Fabio ED - Carlucci Aiello, Luigia T1 - New perspectives on Wireless Network Design - Strong, stable and robust 0-1 models by Power Discretization Y1 - 2012 PB - Sapienza Editrice ER - TY - CHAP A1 - D'Andreagiovanni, Fabio T1 - A Hybrid Exact-ACO Algorithm for the Joint Scheduling, Power and Cluster Assignment in Cooperative Wireless Networks T2 - BIONETICS 2012 Y1 - 2012 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Gleixner, Ambros T1 - Towards an accurate solution of wireless network design problems T2 - Cerulli R., Fujishige S., Mahjoub A. (eds) Combinatorial Optimization. ISCO 2016 N2 - The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-45587-7_12 SP - 135 EP - 147 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Mett, Fabian A1 - Pulaj, Jonad T1 - An (MI)LP-based Primal Heuristic for 3-Architecture Connected Facility Location in Urban Access Network Design T2 - EvoApplications: European Conference on the Applications of Evolutionary Computation. Applications of Evolutionary Computation. 19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 -- April 1, 2016, Proceedings, Part I N2 - We investigate the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks integrating wired and wireless technologies. We propose an original optimization model for the problem that includes additional variables and constraints to take into account wireless signal coverage represented through signal-to-interference ratios. Since the problem can prove very challenging even for modern state-of-the art optimization solvers, we propose to solve it by an original primal heuristic that combines a probabilistic fixing procedure, guided by peculiar Linear Programming relaxations, with an exact MIP heuristic, based on a very large neighborhood search. Computational experiments on a set of realistic instances show that our heuristic can find solutions associated with much lower optimality gaps than a state-of-the-art solver. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-31204-0_19 VL - 9597 SP - 283 EP - 298 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Felici, Giovanni A1 - Lacalandra, Fabrizio T1 - Multiband Robust Optimization for optimal energy offering under price uncertainty T2 - Proc. of ROADEF 2016 N2 - We consider the problem of a price-taker generating company that wants to select energy offering strategies for its generation units, to maximize the profit while considering the uncertainty of market price. First, we review central references available in literature about the use of Robust Optimization (RO) for price-uncertain energy offering, pointing out how they can expose to the risk of suboptimal and even infeasible offering. We then propose a new RO method for energy offering that overcomes all the limits of other RO methods. We show the effectiveness of the new method on realistic instances provided by our industrial partners, getting very high increases in profit. Our method is based on Multiband Robustness (MR - Büsing, D'Andreagiovanni, 2012), an RO model that refines the classical RO model by Bertsimas and Sim, while maintaining its computational tractability and accessibility. MR is essentially based on the use of histogram-like uncertainty sets, which result particularly suitable to represent empirical distributions commonly available in uncertain real-world optimization problems. Y1 - 2016 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A hybrid primal heuristic for Robust Multiperiod Network Design N2 - We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty. Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap. T3 - ZIB-Report - 13-78 KW - Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44081 SN - 1438-0064 ER - TY - GEN A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - 0-1 Multiband Robust Optimization N2 - We provide an overview of new theoretical results that we obtained while further investigating multiband robust optimization, a new model for robust optimization that we recently proposed to tackle uncertainty in mixed-integer linear programming. This new model extends and refines the classical Gamma-robustness model of Bertsimas and Sim and is particularly useful in the common case of arbitrary asymmetric distributions of the uncertainty. Here, we focus on uncertain 0-1 programs and we analyze their robust counterparts when the uncertainty is represented through a multiband set. Our investigations were inspired by the needs of our industrial partners in the research project ROBUKOM. T3 - ZIB-Report - 13-77 KW - Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44093 SN - 1438-0064 ER - TY - GEN A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio T1 - Robust Optimization under Multi-band Uncertainty - Part I: Theory N2 - The classical single-band uncertainty model introduced by Bertsimas and Sim has represented a breakthrough in the development of tractable robust counterparts of Linear Programs. However, adopting a single deviation band may be too limitative in practice: in many real-world problems, observed deviations indeed present asymmetric distributions over asymmetric ranges, so that getting a higher modeling resolution by partitioning the band into multiple sub-bands is advisable. The critical aim of our work is to close the knowledge gap on the adoption of multi-band uncertainty in Robust Optimization: a general definition and intensive theoretical study of a multi-band model are actually still missing. Our new developments have been also strongly inspired and encouraged by our industrial partners, interested in getting a better modeling of arbitrary shaped distributions, built on historical data about the uncertainty affecting the considered real-world problems. T3 - ZIB-Report - 13-10 KW - Robust Optimization, Multiband Uncertainty, Compact Robust Counterpart, Cutting Planes, Probabilistic Bound Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43469 SN - 1438-0064 N1 - Submitted for publication in 2012. Preprint also available in Optimization Online (13-01-3748) and arXiv (1301.2734) ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A Fast Hybrid Primal Heuristic for Multiband Robust Capacitated Network Design with Multiple Time Periods N2 - We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps. T3 - ZIB-Report - 14-40 KW - Capacitated Network Design KW - Multiperiod Design KW - Multiband Robust Optimization KW - Traffic Uncertainty KW - Metaheuristic KW - Ant Colony Optimization KW - Exact Large Neighborhood Search Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52862 SN - 1438-0064 ER - TY - JOUR A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods JF - Applied Soft Computing N2 - We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps. Y1 - 2014 U6 - https://doi.org/10.1016/j.asoc.2014.10.016 VL - 26 SP - 497 EP - 507 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Di Lullo, Michela A1 - Felici, Giovanni A1 - Lacalandra, Fabrizio T1 - A Unified View on Tight Formulations for the Unit Commitment Problem with Optimal Transmission Switching T2 - Gaspard Monge Program for Optimization - Conference on Optimization & Practices in Industry : PGMO-COPI '14 N2 - The classical Unit Commitment Problem (UC) consists in determining the production of a set of thermal and hydro power generation units over a given time horizon, in order to meet a forecast energy demand and minimize a cost function. In the last years, in connection with the UC, increasingly attention has been given to active switching, namely the possibility of changing the topology of the transmission network by tripping some of the lines. Active switching has been indeed recognized as an important way to improve capacity and reliability of the network. Modifying the network topology is also very useful in modern electricity systems, where the penetration of on-programmable renewable energy sources is high and tends to be very concentrated in some zones of the network. As a consequence, the interest for automatic and optimized switching procedures is currently spreading. In this paper, we address the UC when complemented by active switching, thus leading to so-called Unit Commitment with Optimal Transmission Switching (UCOTS). We formulate the UCOTS as a mixed integer linear program, where we unify tight formulations recently proposed in literature for relevant subfamilies of constraints of the problem. Concerning the cost function, in our formulation we approximate the quadratic thermal cost objective function by a piecewise linear function based on perspective cuts and we propose a new simple and effective way to perturb it, with the aim of breaking symmetries induced by optimal transmission switching decision variables. Our original solution approach also exploits specialized branching priorities. Computational experiments on realistic UCOTS instances highlight that our new framework is able to find optimal and near-optimal solutions in reasonable amount of time by direct use of a state-of-the-art commercial MIP solver. Y1 - 2014 ER - TY - JOUR A1 - D'Andreagiovanni, Fabio T1 - Revisiting wireless network jamming by SIR-based considerations and Multiband Robust Optimization JF - Optimization Letters N2 - We revisit the mathematical models for wireless network jamming introduced by Commander et al. (2007,2008): we first point out the strong connections with classical wireless network design and then we propose a new model based on the explicit use of signal-to-interference quantities. Moreover, to address the uncertain nature of the jamming problem and tackle the peculiar right-hand-side uncertainty of the corresponding model, we propose an original robust cutting-plane algorithm drawing inspiration from multiband robust optimization. Finally, we assess the performance of the proposed cutting plane algorithm by experiments on realistic network instances. Y1 - 2014 U6 - https://doi.org/10.1007/s11590-014-0839-2 VL - 9 SP - 1495 EP - 1510 PB - Springer ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Nardin, Antonella T1 - Towards the fast and robust optimal design of Wireless Body Area Networks N2 - Wireless body area networks are wireless sensor networks whose adoption has recently emerged and spread in important healthcare applications, such as the remote monitoring of health conditions of patients. A major issue associated with the deployment of such networks is represented by energy consumption: in general, the batteries of the sensors cannot be easily replaced and recharged, so containing the usage of energy by a rational design of the network and of the routing is crucial. Another issue is represented by traffic uncertainty: body sensors may produce data at a variable rate that is not exactly known in advance, for example because the generation of data is event-driven. Neglecting traffic uncertainty may lead to wrong design and routing decisions, which may compromise the functionality of the network and have very bad effects on the health of the patients. In order to address these issues, in this work we propose the first robust optimization model for jointly optimizing the topology and the routing in body area networks under traffic uncertainty. Since the problem may result challenging even for a state-of-the-art optimization solver, we propose an original optimization algorithm that exploits suitable linear relaxations to guide a randomized fixing of the variables, supported by an exact large variable neighborhood search. Experiments on realistic instances indicate that our algorithm performs better than a state-of-the-art solver, fast producing solutions associated with improved optimality gaps. T3 - ZIB-Report - 15-34 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55475 SN - 1438-0064 ER - TY - JOUR A1 - D'Andreagiovanni, Fabio A1 - Nardin, Antonella T1 - Towards the fast and robust optimal design of Wireless Body Area Networks JF - Applied Soft Computing N2 - Wireless body area networks are wireless sensor networks whose adoption has recently emerged and spread in important healthcare applications, such as the remote monitoring of health conditions of patients. A major issue associated with the deployment of such networks is represented by energy consumption: in general, the batteries of the sensors cannot be easily replaced and recharged, so containing the usage of energy by a rational design of the network and of the routing is crucial. Another issue is represented by traffic uncertainty: body sensors may produce data at a variable rate that is not exactly known in advance, for example because the generation of data is event-driven. Neglecting traffic uncertainty may lead to wrong design and routing decisions, which may compromise the functionality of the network and have very bad effects on the health of the patients. In order to address these issues, in this work we propose the first robust optimization model for jointly optimizing the topology and the routing in body area networks under traffic uncertainty. Since the problem may result challenging even for a state-of-the-art optimization solver, we propose an original optimization algorithm that exploits suitable linear relaxations to guide a randomized fixing of the variables, supported by an exact large variable neighborhood search. Experiments on realistic instances indicate that our algorithm performs better than a state-of-the-art solver, fast producing solutions associated with improved optimality gaps. Y1 - 2015 U6 - https://doi.org/10.1016/j.asoc.2015.04.037 VL - 37 SP - 971 EP - 982 PB - Elsevier ER - TY - JOUR A1 - D'Andreagiovanni, Fabio A1 - Mett, Fabian A1 - Nardin, Antonella A1 - Pulaj, Jonad T1 - Integrating LP-guided variable fixing with MIP heuristics in the robust design of hybrid wired-wireless FTTx access networks JF - Applied Soft Computing N2 - This study investigates how to model and solve the problem of optimally designing FTTx telecommunications access networks integrating wired and wireless technologies, while taking into account the uncertainty of wireless signal propagation. We propose an original robust optimization model for the related robust 3-architecture Connected Facility Location problem, which includes additional variables and constraints to model wireless signal coverage represented through signal-to-interference ratios. Since the resulting robust problem can prove very challenging even for a modern state-of-the art optimization solver, we propose to solve it by an original primal heuristic that combines a probabilistic variable fixing procedure, guided by peculiar Linear Programming relaxations, with a Mixed Integer Programming heuristic, based on an exact very large neighborhood search. A numerical study carried out on a set of realistic instances show that our heuristic can find solutions of much higher quality than a state-of-the-art solver. Y1 - 2017 U6 - https://doi.org/10.1016/j.asoc.2017.07.018 VL - 61 SP - 1074 EP - 1087 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Gleixner, Ambros T1 - Towards an accurate solution of wireless network design problems N2 - The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models. T3 - ZIB-Report - 16-12 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59010 SN - 1438-0064 ER -