Optimization Online


Recoverable Robust Knapsacks: $\Gamma$-Scenarios

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: In this paper, we investigate the recoverable robust knapsack problem, where the uncertainty of the item weights follows the approach of Bertsimas and Sim (2003,2004). In contrast to the robust approach, a limited recovery action is allowed, i.e., upto k items may be removed when the actual weights are known. This problem is motivated by the assignment of traffic nodes to antennas in wireless network planning. Starting from an exponential min-max optimization model, we derive an integer linear programming formulation of quadratic size. In a preliminary computational study, we evaluate the gain of recovery using realistic planning data.

Keywords: gain of recovery, recoverable robust optimization, knapsack problem, traffic demand uncertainty, integer linear programming

Category 1: Robust Optimization

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: submitted to INOC2011

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