TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2010

COGA 5-Wheel

Page Content

to Navigation

Preprints 2010

Recoverable Robust Knapsacks: the Discrete Scenario Case
Citation key Report-018-2010
Author Christina Büsing and Arie M. C. A. Koster and Manuel Kutschka
Year 2010
Number 018
Institution Technische Universität Berlin, Institut für Mathematik
Abstract Admission control problems have been studied extensively in the past. In a typical setting, resources like bandwidth have to be distributed to the different customers according to their demands maximizing the profit of the company. Yet, in real-world applications those demands are deviating and in order to satisfy their service requirements often a robust approach is chosen wasting benefits for the company. Our model overcomes this problem by allowing a limited recovery of a previously fixed assignment as soon as the data are known by violating at most k service promises and serving up to l new customers. Applying this approaches to the call admission problem on a single link of a telecommunication network leads to a recoverable robust version of the knapsack problem. In this paper, we show that for a fixed number of discrete scenarios this recoverable robust knapsack problem is weakly NP-complete and any such instance can be solved in pseudo-polynomial time by a dynamic program. If the number of discrete scenarios is part of the input, the problem is strongly NP-complete and in special cases not approximable in polynomial time, unless P=NP. Next to its complexity status we were interested in obtaining strong polyhedral descriptions for this problem. We thus generalized the well-known concept of covers to gain valid inequalities for the recoverable robust knapsack polytope. Besides the canonical extension of covers we introduce a second kind of extension exploiting the scenario-based problem structure and producing stronger valid inequalities. Furthermore, we present two extensive computational studies to (i) investigate the influence of parameters k and l to the objective and (ii) evaluate the effectiveness of our new class of valid inequalities.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe