Método de descomposición de Benders aplicado al problema de diseño de redes con carga fija

Abstract

New communication networks are constantly emerging to improve connectivity services and facilitate the interconnection of devices of various types. This involves the development of different technologies, such as device-to-device communications, wireless sensor networks and vehicular communications. Mathematical Optimization techniques have always been at the heart of such design problems to formulate and propose computationally efficient numerical algorithms. Benders Decomposition, which is the focus of this document, is one of the more powerful techniques of Mathematical Programming. To design efficient algorithms for large scale problems, the exploitation of the mathematical structure of the problem formulation is crucial. In this way, Benders Decomposition is one the most popular schemes, because it exploits the structure of the problem and decentralizes the overall computational burden. This method was proposed by Benders in 1962, with the main objective of tackling problems with complicating variables, which, when temporarily fixed, yield a problem significantly easier to handle. The Benders Decomposition algorithm has been successfully applied to a wide range of difficult optimization problems. Successful applications are found in many different fields, including planning and scheduling, health care, transportation and telecommunications, energy and resource management and chemical process design. The main purpose of this document is to describe this method and how it can be implemented in the context of network design. We present a general algorithm based on Benders Decomposition for solving the multicommodity uncapacited fixed-charge network design problem, which is the type of problem that we will focus on. This problem is defined on a directed graph. The key feature of this model is its use in evaluating the trade-off between infrastructure investment and operational costs. The former is modeled by the fixed cost paid for using a given connection. The latter is modeled by a linear transportation cost paid per unit of commodity routed on such a connection. The goal is to route all commodities from origins to destinations at minimal cost. In the final part of this document we conduct a numerical experiment in which a transportation network is designed according to a set of costs where some of them are considered unknown when decisions are made. An extension of the classical network design formulation is proposed in order to take into consideration this drawback.