Abstract
“The Price of Robustness” by Bertsimas and Sim [4] represented a breakthrough in the development of a tractable robust counterpart of Linear Programming Problems. However, the central modeling assumption that the deviation band of each uncertain parameter is single may be too limitative in practice: experience indeed suggests that the deviations distribute also internally to the single band, so that getting a higher resolution by partitioning the band into multiple sub-bands seems advisable.
In this work, we study the robust counterpart of a Linear Programming Problem with uncertain coefficient matrix, when a multi-band uncertainty set is considered. We first show that the robust counterpart corresponds to a compact LP formulation. Then we investigate the problem of separating cuts imposing robustness and we show that the separation can be efficiently operated by solving a min-cost flow problem. Finally, we test the performance of our new approach to Robust Optimization on realistic instances of a Wireless Network Design Problem subject to uncertainty.
This work was partially supported by the German Federal Ministry of Education and Research (BMBF), project ROBUKOM, grant 03MS616E, and by the DFG Research Center Matheon - Mathematics for key technologies, project B23 - Robust optimization for network applications.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Ahuja, R.K., Magnanti, T., Orlin, J.B.: Network flows: theory, algorithms, and applications. Prentice Hall, Upper Saddle River (1993)
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Springer, Heidelberg (2009)
Bertsimas, D., Brown, D., Caramanis, C.: Theory and Applications of Robust Optimization. SIAM Review 53(3), 464–501 (2011)
Bertsimas, D., Sim, M.: The Price of Robustness. Oper. Res. 52(1), 35–53 (2004)
Bienstock, D.: Histogram models for robust portfolio optimization. J. Computational Finance 11, 1–64 (2007)
D’Andreagiovanni, F.: Pure 0-1 Programming Approaches to Wireless Network Design. Ph.D. Thesis, Sapienza Università di Roma, Roma, Italy (2010)
Fischetti, M., Monaci, M.: Robustness by cutting planes and the Uncertain Set Covering Problem. ARRIVAL Project Tech. Rep. 0162, Università di Padova, Padova, Italy (2008)
Koster, A.M.C.A., Kutschka, M., Raack, C.: Robust Network Design: Formulations, Valid Inequalities, and Computations. ZIB Tech. Rep. 11-34, Zuse-Institut Berlin, Berlin, Germany (2011)
International Telecommunication Union (ITU): DSB Handbook - Terrestrial and satellite digital sound broadcasting to vehicular, portable and fixed receivers in the VHF/UHF bands (2002)
Mannino, C., Rossi, F., Smriglio, S.: The Network Packing Problem in Terrestrial Broadcasting. Oper. Res. 54(6), 611–626 (2006)
Mannino, C., Rossi, F., Smriglio, S.: A Unified View in Planning Broadcasting Networks. DIS Tech. Rep. 08-07, Sapienza Università di Roma, Roma, Italy (2007)
Mulvey, J.M., Vanderbei, R.J., Zenios, S.A.: Robust Optimization of Large-Scale Systems. Oper. Res. 43, 264–281 (1995)
Nemhauser, G., Wolsey, L.: Integer and Combinatorial Optimization. John Wiley & Sons, Hoboken (1988)
Rappaport, T.S.: Wireless Communications: Principles and Practice, 2nd edn. Prentice Hall, Upper Saddle River (2001)
Watson, J.-P., Hart, W.E., Murray, R.: Formulation and optimization of robust sensor placement problems for contaminant warning systems. In: Buchberger, S.G., et al. (eds.) Proc. of WDSA 2006, ASCE, Cincinnati, USA (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Büsing, C., D’Andreagiovanni, F. (2012). New Results about Multi-band Uncertainty in Robust Optimization. In: Klasing, R. (eds) Experimental Algorithms. SEA 2012. Lecture Notes in Computer Science, vol 7276. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30850-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-30850-5_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30849-9
Online ISBN: 978-3-642-30850-5
eBook Packages: Computer ScienceComputer Science (R0)