Invited Session Mon.2.H 3013

Monday, 13:15 - 14:45 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Recoverable robust combinatorial optimization


Chair: Arie Koster



Monday, 13:15 - 13:40 h, Room: H 3013, Talk 1

Christina Büsing
k-distance recoverable robustness


Recoverable Robustness (RR) is a method to deal with uncertainties in optimization problems extending the classical concept of robustness by allowing limited recovery actions after all data is revealed. In this talk I will present a special case of RR where the recovery actions are limited by changing at most k elements of the previous fixed solution and apply this method to various combinatorial optimization problems. For the shortest path problem, we will see that small changes in the problem setting, e.g., choosing simple s,t-paths at the beginning instead of any s,t-path, strongly influences the complexity status and combinatorial structures of the optimal solutions. I will conclude the talk with an overview of current results on cutting planes for the recoverable robust knapsack polytope and an application to the train classification problem.



Monday, 13:45 - 14:10 h, Room: H 3013, Talk 2

Arie Koster
The recoverable robust knapsack problem

Coauthors: Christina Büsing, Manuel Kutschka


In this talk, we consider the knapsack problem with uncertain item weights. In contrast to the classical robust setting, a limited recovery action is allowed, i.e., up to 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 and the bandwidth packing problem from telecommunication.
We study two scenarios to represent the uncertainty. First, a finite set of realizations is discussed. Second, the uncertainty is modelled by the approach of Bertsimas and Sim (2003,2004) limiting the number of deviations from nominal values by a parameter \Gamma. For both cases, we present the results of a polyhedral study, generalizing the
well-known cover inequalities. Computational experiments conclude the presentation.


  Do you need Missouri Loans Online as soon as possible? On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.