Projeto de rede com custos convexos e balanceamento de fluxos

Abstract

Network design problems are central to a large number of contexts including transportation, telecommunications and power systems. The idea is to establish a network of links (roads, optical fibers, electric lines, etc.) that enables the flow of commodities (people, data packets, electricity, etc.) in order to satisfy some demand characteristics.The interest of this work is fixed-charge network design problems, where, in order to use a link, one must pay a fixed cost that represents for example, the cost of constructing a road, or installing an electric line. Defined the relevance of such problems, it was developed a model of nonlinear mixed integer programming, seeking a breaktrroughtusing flow formulations and techniques of decomposition. The strategy for each subproblem is find an initial feasible solution and improve it by decomposition techniques like Benders Decompostion and Outer Approximation. The aim is to use both techniques together, where the goal is to quickly find the optimal solution. This is due to the great reduction of the tail-off effect when comparing to the classical GeneralizedBenders Decomposition. The utility of the method is also a function of the quality of the Benders cuts that can improve the linear programming relaxation of the master programs.