Optimization Online


Recoverable Robust Knapsack: the Discrete Scenario Case

Christina Büsing(cbuesing***at***math.tu-berlin.de)
Arie M.C.A. Koster(koster***at***math2.rwth-aachen.de)
Manuel Kutschka(kutschka***at***math2.rwth-aachen.de)

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 k to the objective and (ii) evaluate the effectiveness of our new class of valid inequalities.

Keywords: admission control, recoverable robustness, knapsack, extended cover inequalities

Category 1: Robust Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Technical Report, 018-2010, Technische Universität Berlin, 2010. http://www.math.tu-berlin.de/coga/publications/techreports/2010/

Download: [PDF]

Entry Submitted: 02/24/2011
Entry Accepted: 02/24/2011
Entry Last Modified: 02/24/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society