• search hit 29 of 153
Back to Result List

Recoverable Robust Knapsacks: the Discrete Scenario Case

Please always quote using this URN:urn:nbn:de:0296-matheon-10257
  • The knapsack problem is one of the basic problems in combinatorial optimization. In real-world applications it is often part of a more complex problem. Examples are machine capacities in production planning or bandwidth restrictions in telecommunication network design. Due to unpredictable future settings or erroneous data, parameters of such a subproblem are subject to uncertainties. In high risk situations a robust approach should be chosen to deal with these uncertainties. Unfortunately, classical robust optimization outputs solutions with little profit by prohibiting any adaption of the solution when the actual realization of the uncertain parameters is known. This ignores the fact that in most settings minor changes to a previously determined solution are possible. To overcome these drawbacks we allow a limited recovery of a previously fixed item set as soon as the data are known by deleting at most k items and adding up to l new items. We consider the complexity status of this recoverable robust knapsack problem and extend the classical concept of cover inequalities to obtain stronger polyhedral descriptions. Finally, we present two extensive computational studies to investigate the influence of parameters k and l to the objective and evaluate the effectiveness of our new class of valid inequalities.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christina Büsing, Arie M. C. A. Koster, Manuel Kutschka
URN:urn:nbn:de:0296-matheon-10257
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/01/25
Release Date:2012/01/25
Tag:Knapsack Problem; Robust Optimization
Institute:Technische Universität Berlin
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05-06 Proceedings, conferences, collections, etc.
Preprint Number:875
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.