Skip to main content
Top

2016 | OriginalPaper | Chapter

Robustness Concepts for Knapsack and Network Design Problems Under Data Uncertainty

Author : Manuel Kutschka

Published in: Operations Research Proceedings 2014

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This article provides an overview of the author’s dissertation (Kutschka, Ph.D. thesis, RWTH Aachen University, 2013 [10]). In the thesis, we consider mathematical optimization under data uncertainty using MIP techniques and following the robust optimization approach. We investigate four robustness concepts, their parametrization, application, and evaluation. The concepts are \(\varGamma \)-robustness, its generalization multi-band robustness, the novel more general submodular robustness, and the two-stage recoverable robustness. We investigate the corresponding robust generalizations of the knapsack problem (KP) presenting IP formulations, detailed polyhedral studies including new classes of valid inequalities, and algorithms. In particular, for the submodular KP, we establish a connection to polymatroids and for the recoverable robust KP, we develop a nontrivial compact reformulation and carry out detailed computational experiments. Further, we consider the \(\varGamma \)-robust and multi-band brobust generalizations of the network design problem (NDP) presenting MIP formulations, new detailed polyhedral insights with new classes of valid inequalities, and algorithms. For example, we derive alternative formulations for these robust NDPs by generalizing metric inequalities. Furthermore, we present representative computational results for the \(\varGamma \)-robust NDP using real-life measured uncertain data from telecommunication networks based on our work with the German ROBUKOM project.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Altin, A., Amaldi, E., Belotti, P., Pinar, M.C.: Provisioning virtual private networks under traffic uncertainty. Networks 49(1), 100–155 (2007)CrossRef Altin, A., Amaldi, E., Belotti, P., Pinar, M.C.: Provisioning virtual private networks under traffic uncertainty. Networks 49(1), 100–155 (2007)CrossRef
2.
go back to reference Atamtürk, A., Narayanan, V.: Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5), 618–622 (2008)CrossRef Atamtürk, A., Narayanan, V.: Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5), 618–622 (2008)CrossRef
3.
go back to reference Atamtürk, A., Narayanan, V.: The submodular knapsack polytope. Discrete Optim. 6(4), 333–344 (2009)CrossRef Atamtürk, A., Narayanan, V.: The submodular knapsack polytope. Discrete Optim. 6(4), 333–344 (2009)CrossRef
4.
go back to reference Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1), 49–71 (2003)CrossRef Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1), 49–71 (2003)CrossRef
5.
go back to reference Bertsimas, D., Sim, M.: The Price of Robustness. Oper. Res. 52(1), 35–53 (2004)CrossRef Bertsimas, D., Sim, M.: The Price of Robustness. Oper. Res. 52(1), 35–53 (2004)CrossRef
6.
go back to reference Bienstock, D.: Histogram models for robust portfolio optimization. J. Comput. Finance 11, 1–64 (2007) Bienstock, D.: Histogram models for robust portfolio optimization. J. Comput. Finance 11, 1–64 (2007)
7.
go back to reference Bienstock, D., D’Andreagiovanni, F.: Robust wireless network planning. In: Proceedings AIRO 2009, the 40th Annual Conference of the Italian Operational Research Society, pp. 131–132 (2009) Bienstock, D., D’Andreagiovanni, F.: Robust wireless network planning. In: Proceedings AIRO 2009, the 40th Annual Conference of the Italian Operational Research Society, pp. 131–132 (2009)
8.
go back to reference Büsing, C., D’Andreagiovanni, F.: New results about multi-band uncertainty in robust optimization. In: Klasing, R. (ed.) Experimental Analysis—SEA 2012, LNCS, vol. 7276, pp. 63–74. Springer (2012) Büsing, C., D’Andreagiovanni, F.: New results about multi-band uncertainty in robust optimization. In: Klasing, R. (ed.) Experimental Analysis—SEA 2012, LNCS, vol. 7276, pp. 63–74. Springer (2012)
10.
go back to reference Kutschka, M.: Robustness concepts for knapsack and network design problems under data uncertainty: gamma-, multi-band, submodular, and recoverable robustness. Ph.D. thesis, RWTH Aachen University (2013). ISBN: 978-3-95404-593-8 (Cuvillier Verlag, 2013) Kutschka, M.: Robustness concepts for knapsack and network design problems under data uncertainty: gamma-, multi-band, submodular, and recoverable robustness. Ph.D. thesis, RWTH Aachen University (2013). ISBN: 978-3-95404-593-8 (Cuvillier Verlag, 2013)
11.
go back to reference Liebchen, C., Lübbecke, M.E., Möhring, R.H., Stiller, S.: The concept of recoverable robustness, linear programming recovery, and railway applications. In: R. Ahuja, R. Möhring, C. Zaroliagis (eds.) Robust and Online Large-Scale Optimization, LNCS, vol. 5868, pp. 1–27. Springer (2009) Liebchen, C., Lübbecke, M.E., Möhring, R.H., Stiller, S.: The concept of recoverable robustness, linear programming recovery, and railway applications. In: R. Ahuja, R. Möhring, C. Zaroliagis (eds.) Robust and Online Large-Scale Optimization, LNCS, vol. 5868, pp. 1–27. Springer (2009)
12.
go back to reference Mattia, S.: Robust optimization with multiple intervals. Technical Report R. 7 2012, Istituto di Analisi dei Sistemi ed Informatica (IASI), Consiglio Nazionale delle Ricerche (CNR), viale Manzoni 30, 00185 Rome, Italy (2012) Mattia, S.: Robust optimization with multiple intervals. Technical Report R. 7 2012, Istituto di Analisi dei Sistemi ed Informatica (IASI), Consiglio Nazionale delle Ricerche (CNR), viale Manzoni 30, 00185 Rome, Italy (2012)
Metadata
Title
Robustness Concepts for Knapsack and Network Design Problems Under Data Uncertainty
Author
Manuel Kutschka
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-28697-6_48