Date: September, 23rd, 11h30
Place: ULB Bruxelles
Abstract: Multistage optimization problems under uncertainty have attracted interest from both the theoretical and the practical level and robust optimization stands among the most established methodologies for dealing with such problems. In robust optimization, we look for a solution that optimizes the objective function for the worst possible scenario. We address this problem through the lens of decomposition methods. These methods are based on the decomposition of the robust problem into a master problem (MP) and several adversarial separation problems (APs). The master problem contains the original robust constraints, however, written only for finite numbers of scenarios. Additional scenarios are generated on the fly by solving the APs. In this context, we propose new dynamic programming algorithms to solve the APs for robust problems involving budgeted uncertainty, which are based on the maximum number of deviations allowed and on the size of the deviations. These algorithms can be applied to lot-sizing problems and vehicle routing problems among others.