Abstract

Network Systems appear in a countless number of theoretical and practical areas such as Combinatorics, Optimization, Computer Science, Transportation, Telecommunications and Bioinformatics, to mention few of them. A network usually embodies both the input and output of a generic tool called Network Design or Network Optimization. Due the practical applications of Network Design problems, one must take into account - in the different stages of the decision making process - the natural presence of uncertainty in the problem data. Examples of uncertain parameters include the travel time between two cities, the future demand of a client, or the relevance of a protein-complex in a biological process. Likewise, the dynamism of real processes usually bans the possibility of foreseeing with complete precision the classification of clients within different hierarchies, the availability of a place for hosting a facility, or whether a pair of genes actually interacts in a particular process. In the Mathematical Optimization field, the two main approaches to tackle uncertainty are Stochastic Optimization and Robust Optimization. The former relies on the knowledge about the probabilistic behavior of the uncertain data, and typically hedges against the expected value of the parameters. The latter does not make any assumption about the stochastic behavior of the uncertain parameters, and usually protects against the worst-case realization of the data. This project deals with Network Design problems appearing in the areas of Bioinformatics, Design and Construction of Transportation Systems, and Infrastructure Fortification Planning. The considered problems are contextualized in a decision setting where uncertainty should be incorporated by means of Stochastic and/or Robust Optimization modeling frameworks. Chronologically, the first year will be devoted to study the robust counterpart of the Maximum Weight Connected Subgraph Problem, which has relevant appli- cations in the analysis of regulatory networks, metabolic networks and protein-protein interaction (PPI) networks. During the second year, the main focus will be on the study of a robust and stochastic Two-Stage Network Design and Construction Problem; this novel problem has importance in the strategic planning of transportation networks since it combines the decisions about the structure of the desired network and the decisions regarding its actual construction. Finally, in the third year, we will concentrate on the devel- opment of a decision-making tool for deciding a fortification plan to endure critical network systems (such as power, transportation or telecommunication networks); this tool relies on the resolution a new problem called Stochastic Steiner Tree Interdiction Problem. The studied problems will be formulated as Mixed Integer Programming models, which will be first approached from a theoretical and/or structural point of view. This means that we will first characterize the corresponding polyhedral structure, so as to attempt to find facet-defining inequalities or other strong valid inequalities, and derive reduction procedures. Once that proper formulations have been obtained, sophisticated algorithmic frameworks will be designed for obtaining optimal (or nearly optimal) solutions for the problems on a large set of real or realistic instances. Afterwords, an extensive and systematic experimental procedure will be carried out for evaluating the performance of the proposed algorithms and, more relevant, studying the characteristics of the proposed models and of the considered instances. The main goals of this project are twofold. First, to extend and complement the field of Robust and Stochastic Network Design by studying new optimization problems strongly linked with real applications. Second, to provide effective decision-making tools, based on modeling and algorithmic frameworks, for the applications herein described.