Contributions to robust combinatorial optimization with budgeted uncertainty

Robust optimization (RO) has become a central framework to handle the uncertainty that arises in the parameters of optimizationproblems. While classical RO results can efficiently handle linear programs for a large variety of uncertainty sets, the situation is morecomplex for optimization problems involving discrete decisions. Efficient exact or approximate solution algorithms for such problemsmust exploit the combinatorial structure of the problems at hand.This thesis uses the budgeted uncertainty set, introduced by Bertsimas and Sim in (2003,2004), to address scheduling problems, vehicle routingproblems, constrained shortest path problems, and lot-sizing problems. We address the resulting robust combinatorial optimization problems along two complementary set of tools: exact and approximate combinatorial algorithms, and decomposition algorithms based on integerprogramming formulations. In addition to the results specific to each problem, we present an extension of the budgeted uncertainty that ismotivated by a connection with probabilistic constraints