Dynamic partitioning applied to the recoverable robust knapsack problem

Session : SS6 / SS6 : Optimisation robuste : application et algorithmes
Jeudi 11 février 15:00 - 17:00 Salle : RP12
Marco Silva, Michael Poss, Nelson Maculan et Philippe Michelon

This study is interested in recent algorithms developed to handle multistage robust optimization problems (MRO) by a dynamic partitioning approach of the uncertainty and their power to naturally handle mixed integer optimization problems. In order to accomplish this task the study will investigate the recoverable robust knapsack problem, where the uncertainty of the item weights follows the budget uncertainty set approach of Bertsimas and Sim (2004) and a limited recovery action of up to k items is allowed after the actual weights are known. This problem is motivated by the assignment of traffic nodes to antennas in wireless network planning.

Mots clés : knapsack problem, robust optimization, dynamic partitioning