Abstract
Finding robust solutions of an optimization problem is an important issue in practice. The established concept of Ben-Tal et al. [2] requires that a robust solution is feasible for all possible scenarios. However, this concept is very conservative and hence may lead to solutions with a bad objective value and is in many cases hard to solve. Thus it is not suitable for most practical applications. In this paper we suggest an algorithm for calculating robust solutions that is easy to implement and not as conservative as the strict robustness approach. We show some theoretical properties of our approach and evaluate it using linear programming problems from NetLib.
partially supported by grant SCHO 1140/3-1 within the DFG programme Algorithm Engineering.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Erera, A.L., Morales, J.C., Svalesbergh, M.: Robust optimization for empty repositioning problems. Operations Research 57(2), 468–483 (2009)
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)
Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Programming A 99, 351–376 (2003)
Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Mathematics of Operations Research 23(4), 769–805 (1998)
Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Programming A 88, 411–424 (2000)
Bertsimas, D., Sim, M.: The price of robustness. Operations Research 52(1), 35–53 (2004)
Cicerone, S., D’Angelo, G., Di Stefano, G., Frigioni, D., Navarra, A., Schachtebeck, M., Schöbel, A.: Recoverable robustness in shunting and timetabling. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 28–60. Springer, Heidelberg (2009)
Drezner, Z., Klamroth, K., Schöbel, A., Wesolowsky, G.: The weber problem. In: Drezner, Z., Hamacher, H.W. (eds.) Location Theory - Applications and Theory, ch. 1, pp. 1–36. Springer, Heidelberg (2001)
Fischetti, M., Monaci, M.: Light robustness. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 61–84. Springer, Heidelberg (2009)
El Ghaoui, L., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM Journal of Matrix Anal. Appl. 18, 1034–1064 (1997)
Goerigk, M., Schöbel, A.: An empirical analysis of robustness concepts for timetabling. In: Erlebach, T., Lübbecke, M. (eds.) Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Dagstuhl, Germany. OpenAccess Series in Informatics (OASIcs), vol. 14, pp. 100–113. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2010)
Gurobi Optimization, Inc., Houston, Texas. Gurobi Optimizer Reference Manual Version 3.0 (September 2010)
Juel, H., Love, R.F.: Hull properties in locationproblems. European Journal of Operational Research 12, 262–265 (1983)
Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (1997)
Liebchen, C., Lübbecke, M., Möhring, R., Stiller, S.: The concept of recoverable robustness, linear programming recovery, and railway applications. In: Ahuja, R.K., Möhring, R.H., Zaroliagis, C.D. (eds.) Robust and Online Large-Scale Optimization. LNCS, vol. 5868, pp. 1–27. Springer, Heidelberg (2009)
Plastria, F.: Localization in single facility location. European Journal of Operational Research 18, 215–219 (1984)
Soyster, A.L.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research 21, 1154–1157 (1973)
Stiller, S.: Extending concepts of reliability. Network creation games, real-time scheduling, and robust optimization. PhD thesis, TU Berlin (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goerigk, M., Schöbel, A. (2011). A Scenario-Based Approach for Robust Linear Optimization. In: Marchetti-Spaccamela, A., Segal, M. (eds) Theory and Practice of Algorithms in (Computer) Systems. TAPAS 2011. Lecture Notes in Computer Science, vol 6595. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19754-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-19754-3_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19753-6
Online ISBN: 978-3-642-19754-3
eBook Packages: Computer ScienceComputer Science (R0)