Solving probabilistic-robust optimization problems using methods from semi-infinite optimization

Optimization under uncertainty is one field of mathematics that is strongly inspired by real world problems. To handle uncertainties, e.g., in packing problems, inventory management or supply chains coordination several concepts of how to model uncertainty have arisen. To solve such problems by numeric methods, we typically have to decide between uncertainty concepts with or without distributional information. While uncertainty concepts without distribution information focus more on single scenarios such as a worst-case scenario, uncertainty concepts with distribution information allow, for example, to assign a probability to a set of uncertain parameters. As models of complex uncertainty allow the modeler to describe the problem in more details, the mathematical handling of these models gets harder. In this thesis, we concentrate on the numerical treatment of probabilistic-robust (probust) optimization problems. Although some special instances of these problems have been dealt with by reducing them to already known optimization problems, we are not aware of any results in the literature concerning solving techniques applicable to the class of probust optimization problems themselves. This thesis aims at filling this gap. We start by generalizing the concept of probust optimization problems known so far to be able to model our applications. Given appropriate transformations, we can show that generalized probust optimization problems can be handled the same way as the already known standard problem class. Then we focus on solving these standard probust optimization problems using methods that are inspired by concepts from semi-infinite optimization. On the one hand, we calculate lower bounds of the optimal value by a sequence of joint chance constrained optimization problems. We construct these problems by discretization schemes satisfying a special condition which leads to the convergence of the corresponding lower bounds to the solution of the standard probust optimization problem. Furthermore, we show that, e.g., a uniform discretization approach and an adapted variant of the Blankenship and Falk discretization fulfill this condition. On the other hand, we create upper bounds of the optimal value using a sequence of set-approximation problems. Here we substitute the set of feasible realizations that is connected to a fixed decision by a special set out of a given family of parametrized sets. We provide sufficient conditions to guarantee that the sequence of upper bounds converges towards the optimal value of the standard probust optimization problem. Additionally, we comment on how to select the family of parametrized sets based on structures within these optimization problems. In the end, we combine the introduced upper and lower bounds to define sandwiching algorithms. To understand the different solving methods in more detail, we consider geometric packing problems which can be solved analytically and can be interpreted visually. We define discretization schemes that use the structure of sets of feasible realizations to solve these problems. Hereby, we understand that modified discretization methods and a fast probability evaluation are critical to solve probust optimization problems efficiently. With this understanding, we solve a probust formulation of a specific inventory management problem - a water reservoir problem. As we do not recognize a special structure in the set of feasible realizations of these problems, nor an efficient discretization method, we have to derive these pieces of information from the problem instance. Therefore, we define a discretization method that scans the uncertainty set for “important” discretization points. With this method we are able to solve the probust water reservoir problem (approximately) and compare its solution with the solutions of other uncertainty models. Ultimately, we consider an application where we want to guarantee high quality products despite the quality of delivered goods and the production process itself is uncertain.