Magíster en Gestión de Operaciones / todos desarrollados en estudios previos. Para este tipo de problemas, la formEn este trabajo se desarrolla un nuevo enfoque para resolver el problema de diseño de redes no capacitadas con fuente única en base a la combinación de méulación multicommodity que desagrega las demandas ha sido utilizada extensamente y se ha probado que se obtienen mejores resultados que con la formulación de flujo en redes clásica al comparar sus relajaciones lineales. En este trabajo se muestra que dicha formulación puede mejorar aún más al duplicar y dirigir arcos no-dirigidos. Con este concepto, se desarrolla un método de ascenso dual específico para el problema de diseño con fuente única que entrega cotas inferiores de buena calidad. Dentro de este método se propone un esquema de clasificación de commodities que permite una representación reducida del problema y que entrega mejores cotas inferiores en las instancias testeadas. Adicionalmente, este método también entrega una subred de tamaño reducido que se utiliza para encontrar soluciones primales factibles. Se muestra, que en este sentido, el método de ascenso dual es una excelente herramienta de selección de arcos en términos del potencial que tiene la subred de encontrar soluciones primales de buena calidad. Para obtener la solución primal, se utiliza la formulación multicommodity original o un esquema de generación de filas dependiendo del tamaño de la instancia. Se testean los distintos enfoques en instancias de distintos tamaños de redes en forma de grilla generadas aleatoriamente variando sus parámetros y su relación de costos fijos a costos de flujo, testeando instancias que en su equivalente de formulación multicommodity llegan a más de 16 millones de variables. / Este trabajo ha sido parcialmente financiado por Comisión Nacional de Investigación Científica y Tecnológica (CONICYT)

Given an undirected network with L possible facility types for each edge, and a partition of the nodes into L levels, the Multi-level Network Design (MLND) problem seeks a fixed cost minimizing design that spans all the nodes and connects the nodes at each level by facilities of the corresponding or higher type. This problem generalizes the well-known Steiner network problem and the hierarchical network design problem, and has applications in telecommunication, transportation, and electric power distribution network design. In a companion paper we introduced the problem, studied alternative model formulations, and analyzed the worst-case performance of heuristics based on Steiner network and spanning tree solutions. This paper develops and tests a dual-based algorithm for the Multi-level Network Design (MLND) problem. The method first performs problem preprocessing to fix certain design variables, and then applies a dual ascent procedure to generate upper and lower bounds on the optimal value. We report extensive computational results on large, random networks (containing up to 500 nodes, and 5000 edges) with varying cost structures. The integer programming formulation of the largest of these problems has 20,000 integer variables and over 5 million constraints. Our tests indicate that the dualbased algorithm is very effective, producing solutions guaranteed to be within 0 to 0.9% of optimality.

Surveillance is an important application for unmanned aerial vehicles (UAVs). The sensed information often has high priority and it must be made available to human operators as quickly as possible. Due to obstacles and limited communication range, it is not always possible to transmit the information directly to the base station. In this case, other UAVs can form a relay chain between the surveillance UAV and the base station. Determining suitable positions for such UAVs is a complex optimization problem in and of itself, and is made even more difficult by communication and surveillance constraints. To solve different variations of finding positions for UAVs for surveillance of one target, two new algorithms have been developed. One of the algorithms is developed especially for finding a set of relay chains offering different trade-offs between the number of UAVsand the quality of the chain. The other algorithm is tailored towards finding the highest quality chain possible, given a limited number of available UAVs. Finding the optimal positions for surveillance of several targets is more difficult. A study has been performed, in order to determine how the problems of interest can besolved. It turns out that very few of the existing algorithms can be used due to the characteristics of our specific problem. For this reason, an algorithm for quickly calculating positions for surveillance of multiple targets has been developed. This enables calculation of an initial chain that is immediately made available to the user, and the chain is then incrementally optimized according to the user’s desire.