Recoverable Robust Knapsacks: the Discrete Scenario Case

Christina Büsing, Arie M. C. A. Koster, and Manuel Kutschka

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]