Robust optimization (RO) is a popular framework to handle the uncertainty that arises in optimization problems. The essence of RO lies in imposing that feasible solutions satisfy the robust constraints for all parameter realizations in a given uncertainty set U. We consider in this project Combinatorial Robust Optimization (CRO), the subfield of RO that studies combinatorial optimization (CO) problems. Moreover, we assume that the uncertainty set is the so-called budgeted uncertainty set UΓ introduced by Bertismas and Sim and extremely popular in combinatorial optimization and network optimization literatures. Set UΓ considers that each uncertain parameter varies between its mean value and its peak value and that the number of parameters that simultaneously reach their peak value is bounded by Γ. We denote the resulting optimization problems by Г-CRO.
The classical approach to RO trades the robust constraints for convex reformulations using, for instance, conic duality or Fenchel duality. While useful for optimization problems without discrete variables, these non-linear reformulations appear quite limited for combinatorial optimization problems, very often breaking their combinatorial structures. For this reason, two other approaches have emerged:
- Purely combinatorial approaches such as the result from Bertsimas and Sim (2003) which shows how to solve purely binary min max Г-CRO problems with cost uncertainty by solving up to n times the deterministic counterpart, where n is the number of variables of the problem.
- Decomposition approaches, which separate any Г-CRO problem into a master problem (MP) and adversary separation problems (AP). MP contains the deterministic constraints as well as the robust constraints written only for finite numbers of scenarios. The APs are solved to check whether we need to extend the numbers of scenarios used in MP, resulting in a row-and-column generation algorithms. Here, the combinatorial structure of UΓ can be used to develop efficient combinatorial algorithms.
The purpose of this research axis is to further investigate these combinatorial approaches. Since combinatorial approaches are usually problem-dependent, we focus on specific CO problems. Recent research has considered constrained shortest path, lot-sizing, and simple scheduling problems. In addition to exact solution algorithms, we will also study approximation algorithms, which have been little applied to such kind of problems.