Robustness Concepts for Knapsack and Network Design Problems Under Data Uncertainty

Manuel Kutschka ()
Additional contact information
Manuel Kutschka: INFORM GmbH

A chapter in Operations Research Proceedings 2014, 2016, pp 341-347 from Springer

Abstract: 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.

Keywords: Robustness Concept; Network Design Problem (NDP); Knapsack; Recoverable Robust; Robust KP (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-28697-6_48

Ordering information: This item can be ordered from
http://www.springer.com/9783319286976

DOI: 10.1007/978-3-319-28697-6_48

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().