Contributions to robust and bilevel optimization models for decision-making

Résumé

Combinatorial optimization problems have been extensively studied in the specialized literature since the mid-twentieth century. However, in recent decades, there has been a paradigm shift to the treatment of ever more realistic problems, which include sources of randomness and uncertainty in the data, multiple optimization criteria and multiple levels of decision. This thesis concerns the development of such concepts. Our objective is to study optimization models that incorporate uncertainty elements in the parameters defining the model, as well as the development of optimization models integrating multiple decision levels. In order to consider problems under uncertainty, we use Minmax Regret models from Robust Optimization; whereas the multiplicity and hierarchy in the decision levels is addressed using Bilevel Optimization. In Chapters 2, 3 and 4, we study different decision problems under uncertainty to which we give a robust solution that protects the decision-maker minimizing the maximum regret that may occur. This robust criterion analyzes the performance of the system under multiple possible scenarios, comparing its efficiency with the optimum one under each feasible scenario. We obtain, as a result, a solution whose efficiency is as close as possible to the optimal one in the set of feasible realizations of the uncertain parameters. In Chapter 2, we study a network design problem in which the costs, the pairs supplier-customer, and the demands can take uncertain values. Furthermore, the uncertainty in the parameters is modeled via polyhedral sets, thereby allowing relationships among the uncertain parameters. In Chapter 3, we propose time-dependent versions of the shortest path and traveling salesman problems in which the costs of traversing an arc depends on the relative position that the arc occupies in the path. Moreover, we assume that some of the parameters defining these costs can be uncertain. These models can be applied in the context of task sequencing or grid computing. The incorporation of time-dependencies together with uncertainties in the parameters gives rise to dependencies among the uncertain parameters, which require modeling the possible scenarios using more general sets than hypercubes, normally used in this context. In this chapter, we use general polyhedral sets with this purpose. To finalize this first block of applications, in Chapter 4, we analyze an optimization model in which the set of possible scenarios can be modified by making some investments in the system. In the problems studied in this first block, each feasible decision is evaluated based on the most unfavorable possible reaction of the system. In Chapters 5 and 6, we will still follow this idea, but assuming that the reaction to the initial feasible decision will be held by a follower or an adversary, instead of assuming the most unfavorable one. These two chapters are focused on the study of some bilevel models. Bilevel Optimization addresses optimization problems with multiple decision levels, different decision-makers in each level and a hierarchical decision order. In particular, in Chapter 5, we study some price setting problems in the context of portfolio selection. In these problems, the financial intermediary becomes a decision-maker and sets the transaction costs for investing in some securities, and the investor chooses her portfolio according to different criteria. Finally, in Chapter 6, we study a location problem with several decision-makers and opposite interests, that must set, sequentially, some location points. This bilevel location model can be applied in practical applications such as the location of semi-obnoxious facilities (power or electricity plants, waste dumps, etc.) or interdiction problems. All these models are stated from a Mathematical Programming perspective, analyzing their properties and developing formulations and algorithms, that are tested from a computational point of view. Furthermore, we pay special attention to justifying the validity of the models from the practical applications point of view. The models presented in this thesis share the characteristic of involving the resolution of nested optimization problems.