direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 18-2010

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Recoverable Robust Knapsacks: the Discrete Scenario Case
not available
admission control, recoverable robustness, knapsack, extended cover inequalities
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.
Download as [PDF]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe