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 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 - TY - GEN A1 - Uslu, Svenja A1 - Werner, Axel T1 - A Two-Phase Method for the Biobjective k-Architecture Connected Facility Location Problem and Hypervolume Computation N2 - We apply customized versions of the ε-constraint Method and the Two-Phase Method to a problem originating in access network planning. We introduce various notions of quality measures for approximated/partial sets of nondominated points, utilizing the concept of hypervolume for biobjective problems. We report on computations to assess the performance of the two methods in terms of these measures. T3 - ZIB-Report - 15-08 KW - Biobjective Optimization KW - Connected Facility Location KW - Hypervolume Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53753 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 - 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 - THES A1 - Mett, Fabian T1 - The Connected Facility Location Problem Y1 - 2015 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 - 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 - JOUR A1 - Leitner, Markus A1 - Ljubic, Ivana A1 - Sinnl, Markus A1 - Werner, Axel T1 - ILP heuristics and a new exact method for bi-objective 0/1 ILPs: Application to FTTx-network design JF - Computers & Operations Research Y1 - 2016 U6 - https://doi.org/10.1016/j.cor.2016.02.006 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 - 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 -