Search

La planificación del transporte público urbano colectivo (TPUC) basada en herramientas de apoyo a la decisión cobra cada vez más importancia, tanto en los países desarrollados como en los en vías de desarrollo. Una proporción importante de los viajes en las ciudades medianas y grandes son efectuados utilizando transporte público colectivo. Problemas como la asignación de flota y personal, han recibido amplio tratamiento, contándose con modelos de optimización para los cuales se dispone de algoritmos eficientes de resolución. En cambio el problema de optimización de rutas y frecuencias posee varias fuentes de complejidad (no linealidad, no convexidad, múltiples objetivos) que dificultan tanto su formulación como la derivación de algoritmos eficientes de resolución. En este trabajo se releva el estado del arte respecto a modelos y algoritmos para el problema de optimización de rutas y frecuencias, seleccionados en el contexto del desarrollo de una herramienta de apoyo a la planificación del sistema de TPUC para la ciudad de Montevideo, Uruguay (1.500.000 habitantes). Todos los trabajos relevados resuelven el problema utilizando algoritmos heurísticos, encontrándose varias aplicaciones de la técnica algoritmos genéticos. Las dimensiones de los casos de prueba son generalmente pequeñas, y no se hallaron abordajes para el problema con requerimientos de demanda variable en el tiempo, aspectos de interés para el caso de estudio que motiva este trabajo.

Consider a network where the links are subject to random, independent failures. The diameter constrained network reliability parameter R(G,K,D) measures the probability that the set K of terminals of the network are linked by operational paths of length less or equal to D. This parameter generalizes the classical network reliability, allowing to reflect performance objectives that restrict the maximum length of a path in the network. This is the case, for example, when the transmissions between every two terminal nodes in the subset K are required to experience a maximum delay D.T (where T is the delay experienced at a single node or link); then the probability that after random failures of the communication links, the surviving network meets the maximum delay requirement is the diameter constrained reliability R(G,K,D). This paper defines the diameter constrained network reliability, and gives a formulation in terms of events corresponding to the operation of the (length constrained) paths of the network. Based on this formulation, the exact value of the diameter constrained reliability is derived, for the special case where K=\{s,t\} and the upper bound D of the path length is 2. For other values of K and D an exact evaluation algorithm based on a factorization approach is proposed. As this algorithm has exponential worst case complexity, upper and lower bounds for K=\{s,t\} are developed, which in some cases may be used instead of the exact value

Ant Systems (AS) is a recently proposed meta-heuristic inspired on biological behaviors, which has been applied to a variety of combinatorial optimization problems, including the QAP (Quadratic Assignment Problems). In this work, we have studied the adaptation of the Ant Systems meta-heuristic to two different real-life assignment problems, which appear in educational institutions: the timetabling problem (assigning courses to classrooms and times), and the assignment of final proyects to students. There is no standard definition for these problems, as in each institution the rules and objectives are different. We have been successful in adapting. AS to tackle these problems as defined by our institution rules, showing the adaptability of this meta-heuristic to complex, real-life problems. In both cases the AS meta-heuristic obtained good quality solutions (in the timetabling case, at the cost of longer running times).

Very complex systems occur nowadays quite frequently in many technological areas and they are often required to comply with high dependability standards. To study their availability and reliability characteristics, Markovian models are commonly used. Due to the size and complexity of the systems, and due to the rarity of system failures, both analytical solutions and "crude" simulation can be inefficient or even non-relevant. A number of variance reduction Monte Carlo techniques have been proposed to overcome this difficulty; importance sampling methods are among the most efficient. The objective of this paper is to survey existing importance sampling schemes, to propose some improvements and to discuss on their different properties.

Una red de comunicaciones es un sistema compuesto por un conjunto de centros que reciben y envían información, y por un conjunto de conexiones que transportan esa información. La capacidad de una red de comunicaciones para resistir a posibles fallos de algunos de sus componentes se evalúa a través de distintas métricas de confiabilidad. Uno de los problemas que se plantean durante el diseño de una red, es el de elegir su topología precisamente para asegurar al máximo las comunicaciones. En este trabajo, abordamos una versión de este problema, en la que el objetivo es encontrar una topología más confiable a partir de una red dada por el usuario. La metodología empleada corresponde a la metaheurística "simulated annealing", de reciente utilización en el campo de la optimización combinatoria.

Uno de los problemas fundamentales de la robótica móvil es la localización. En la gran mayoría de las tareas que debe realizar un robot móvil, es necesario mantener una estimación precisa de la posición del robot. El problema de la localización se puede ver como un problema de correspondencia entre el sistema de coordenadas local del robot y el sistema de coordenadas global del mapa. Dentro de las soluciones a este problema, el enfoque más simple se conoce como localización pasiva. La localización pasiva consiste en estimar la posición del robot a partir de un mapa y de las percepciones que obtiene el robot a medida que navega en el entorno. Existe otro enfoque conocido como localización activa que se diferencia de la localización pasiva en que el robot ejecuta acciones intencionalmente para mejorar su localización. En este sentido, la mayoría de los trabajos sobre localización activa tienen como principal objetivo seleccionar las acciones que dirijan al robot (o a sus sensores) hacia zonas del mapa relevantes, aumentando la riqueza de la información adquirida en las observaciones del entorno, y en consecuencia, mejorando la precisión y disminuyendo la incertidumbre de la estimación de la posición del robot en el mapa. Según la literatura, la localización activa ha tenido mejores resultados que la localización pasiva. Otra categorización aplicada a los problemas de localización los divide entre localización global y seguimiento de posición. Localización global consiste en que inicialmente el robot no sabe en que zona del entorno se encuentra y tiene como objetivo localizarse, mientras que en el seguimiento de posición el robot conoce su posición inicial y el objetivo es mantenerse ubicado a medida que navega por el entorno. Este trabajo estudia la localización activa en interiores en el contexto del problema de seguimiento de posición. El sistema propuesto en esta tesis extiende el trabajo de Li et al. Active localization with dynamic obstacles [2016, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1902-1909]. En el trabajo de Li et al. se mantiene un conjunto de hipótesis sobre los posibles estados del robot (x; y; θ) en el mapa, se agrupan utilizando DBSCAN y luego se elige un representante por agrupación. Los representantes y sus mapas asociados se colocan en un marco de referencia común, y se genera un mapa compuesto que permite saber cuales son los puntos del mapa que aportan más información sobre la localización. Luego, se elige la acción que dirija a los sensores hacia el punto que brinde mayor ganancia de información. Se espera que las observaciones del punto elegido descarten una cantidad relevante de hipótesis, mejorando la estimación sobre la posición del robot. Esta estrategia es aplicada en un contexto de localización global. En esta tesis se estudió la estrategia presentada por Li et al. y se extendió aplicándola al problema de seguimiento de posición, combinándola diversos algoritmos de agrupamiento como Kmeans++ y Spectral Clustering. Se realizaron experimentos en distintos escenarios simulados y en un escenario real, con una ruta de navegación preestablecida, comparando cuatro estrategias diferentes (tres de localización activa y una de localización pasiva). Los experimentos presentan mejores resultados en la estimación de la posición para las estrategias propuestas en esta tesis (basadas en Kmeans++ y Spectral Clustering) con respecto a la estrategia utilizada en el trabajo de Li et al. (basado en DBSCAN), y a un algoritmo de localización pasiva.

Tribunal: Dr. Eduardo Fernández, Dr. Andrés Pomi, M.Sc. María E. Urquhart Los modelos basados en restricciones permiten estudiar las redes metabólicas de diferentes cepas de microorganismos. Imponiendo la condición de estado estacionario, estos modelos definen un espacio de flujos que puede ser analizado mediante simulaciones de Monte Carlo para, por ejemplo, aproximar su volumen. Este volumen está relacionado con el repertorio de posibles respuestas del microorganismo a cambios en las condiciones externas. El cálculo del volumen es un problema complejo desde el punto de vista computacional, dado que el espacio de flujos suele desarrollarse en muchas dimensiones, por lo que Monte Carlo estándar no es suficiente para analizar los modelos más grandes. En este trabajo se estudió la posibilidad de usar muestreos por importancia y Hit-and-Run para mejorar los resultados del Monte Carlo estándar. La metodología desarrollada se puso a prueba en un modelo ramificado simple y en un modelo núcleo de E.coli compacto, con 25 reacciones y 17 metabolitos. Se validó este modelo observando que se comporta de manera muy similar al núcleo de E.coli y que además verifica el “growth-flexibility trade-off”. El muestreo por importancia no mejoró los resultados del Monte Carlo estándar, pero su aplicación permitió una mayor comprensión de esta técnica aplicada al muestreo en modelos metabólicos, abriendo líneas de trabajo futuro. Con Hit-and-Run se logró una aproximación al orden de magnitud del volumen del espacio de flujos, que puede resultar útil en modelos de muchas dimensiones. Se aplicaron estas técnicas para el análisis del núcleo de E.coli compacto, encontrándose resultados relevantes cuyas implicancias biológicas se analizaron. A modo de ejemplo, estudiando los volúmenes con distintas fermentaciones en el modelo, se encontró que no existe una sinergia en ningún par de fermentaciones que permita un mayor aumento en el volumen al estar las dos fermentaciones activadas a la vez. Se simuló también una capacidad máxima en el microorganismo imponiendo una restricción a la suma de los valores absolutos de los flujos, buscando un valor óptimo a partir de un indicador que comprende el volumen y la distancia promedio al centro de masa del espacio de soluciones. Por otro lado, al estudiar la relación entre crecimiento máximo y volumen, se encontró que se requiere reducir la cota inferior del crecimiento microbiano a valores inferiores al 60% del crecimiento máximo para obtener un volumen que no sea despreciable con respecto al volumen máximo (obtenido con cota inferior igual a cero). Si bien el problema de calcular volúmenes en muchas dimensiones de manera precisa está lejos de ser resuelto, estos y otros resultados encontrados muestran que la aplicación de simulaciones de Monte Carlo permite obtener conclusiones significativas a partir de modelos metabólicos, incluso cuando se trata de modelos simplificados.

La gestión de los recursos forestales implica la toma de decisiones a nivel estratégico, táctico y operativo, con consecuencias tanto a corto como a largo plazo. Uno de los componentes de esta cadena de toma de decisiones corresponde a la cosecha forestal, que es de importancia por su alto impacto en los costos de producción. Una planificación eficiente de las operaciones de cosecha puede reducir significativamente los costos asociados con la logística y mejorar el desempeño económico de las empresas del sector. En Uruguay, casi el 75% del total de las operaciones de cosecha forestal para la producción de celulosa es realizada por empresas contratistas, por lo que son un actor importante en la cadena de suministro. Este estudio tiene como objetivo optimizar la asignación y ruteo de los equipos de cosecha de los contratistas forestales, los cuales deben ser localizados entre los lugares a cosechar durante el año. Como parte de este trabajo se realiza una búsqueda sistemática de la literatura relacionada con la optimización de la planificación de la cosecha forestal. Se opta por utilizar la metodología de mapping study a tales efectos. Esta tesis propone un modelo de optimización combinatoria para este problema, basado en el Problema del Múltiple Vendedor Viajero con Múltiples Depósitos (MmTSP). Los experimentos numéricos han demostrado que las instancias de tamaño realista pueden ser resueltas por software de programación matemática estándar en un tiempo razonable. Esta formulación permite visualizar potenciales ganancias en planificación conjunta de varios contratistas en relación con la planificación por separado. Además se propone algoritmos para la reprogramación de las recorridas de cosechas, en los casos de falla de equipos o de indisponibilidad temporal de los bloques de cosecha, por ejemplo cuando el acceso a estos, se ve impedido por largo periodos de lluvia. Este modelo puede ser utilizado como una herramienta eficiente y práctica de apoyo a la programación anual de cosecha forestal y la asignación de equipo para las empresas contratistas, lo que conduce a mejores planes de calidad y oportunidades de mejora. The management of the forest resources involves decision making at strategic, tactical, and operational levels, with both short and long term consequences. One of the components of this decision making chain corresponds to forest harvesting, which is a step of vital importance because of its high impact on production costs. An efficient planning of harvesting operations can significantly lower costs associated with logistics and improve the economic performance of companies in the sector. In Uruguay, almost 75% of the total forestry operations destined to the production of pulp are in charge of contractor companies, which are an important player in the supply chain. This work aims to optimize the scheduling and routing of the contractors' harvesting equipment, which must be relocated between the places to be harvested in a season. As part of this thesis a systematic search of the literature related to optimization methods for forest harvest planning is carried was carried out employing the mapping study methodology. This work proposes a combinatorial optimization model for this problem, based on the Multi Depot Multiple Traveling Salesman Problem (MmTSP). Numerical experiments have shown that instances of realistic size can be solved by standard mathematical programming software in a reasonable time. This formulation allows to visualize the profits in the joint planning of several contractors against the case where each contractor makes a separate planning. In addition, some algorithms are proposed for the reprogramming of harvest tours in the case of equipments failure and in the case and in the case of temporary unavailability of the harvest blocks, for example when access is impeded by long periods of rain. This model can then be used as an eficient and practical tool for helping to develop the annual forest harvesting scheduling and equipment allocation for contractor companies, leading to better quality plans and improvement opportunities.

La utilización de unidades de procesamiento gráfico (GPUs) para la resolución de problemas de propósito general ha experimentado un crecimiento vertiginoso en los últimos años, sustentado en su amplia disponibilidad, su bajo costo económico y en contar con una arquitectura inherentemente paralela, así como en la aparición de lenguajes de programación de propósito general que han facilitado el desarrollo de aplicaciones en estas plataformas. En este contexto, el diseño de nuevos algoritmos paralelos que puedan beneficiarse del uso de GPUs es una línea de investigación prometedora e interesante. Las metaheurísticas son algoritmos estocásticos capaces de encontrar soluciones muy precisas (muchas veces óptimas) a problemas de optimización en un tiempo razonable. Sin embargo, como muchos problemas de optimización involucran tareas que exigen grandes recursos computacionales y/o el tamaño de las instancias que se están abordando actualmente se están volviendo muy grandes, incluso las metaheurísticas pueden ser computacionalmente muy costosas. En este escenario, el paralelismo surge como una alternativa exitosa con el fin de acelerar la búsqueda de este tipo de algoritmos. Además de permitir reducir el tiempo de ejecución de los algoritmos, las metaheurísticas paralelas a menudo son capaces de mejorar la calidad de los resultados obtenidos por los algoritmos secuenciales tradicionales.Si bien el uso de GPUs ha representado un dominio inspirador también para la investigación en metaheurísticas paralelas, la mayoría de los trabajos previos tenían como objetivo portar una familia existente de algoritmos a este nuevo tipo de hardware. Como consecuencia, muchas publicaciones están dirigidas a mostrar el ahorro en tiempo de ejecución que se puede lograr al ejecutar los diferentes tipos paralelos de metaheurísticas existentes en GPU. En otras palabras, a pesar de que existe un volumen considerable de trabajo sobre este tópico, se han propuesto pocas ideas novedosas que busquen diseñar nuevos algoritmos y/o modelos de paralelismo que exploten explícitamente el alto grado de paralelismo disponible en las arquitecturas de las GPUs. Esta tesis aborda el diseño de una propuesta innovadora de algoritmo de optimización paralelo denominada Búsqueda Genética Sistólica (SGS), que combina ideas de los campos de metaheurísticas y computación sistólica. SGS, así como la computación sistólica, se inspiran en el mismo fenómeno biológico: la contracción sistólica del corazón que hace posible la circulación de la sangre. En SGS, las soluciones circulan de forma síncrona a través de una grilla (rejilla) de celdas. Cuando dos soluciones se encuentran en una celda se aplican operadores evolutivos adaptados para generar nuevas soluciones que continúan moviéndose a través de la grilla (rejilla). La implementación de esta nueva propuesta saca partido especialmente de las características específicas de las GPUs. Un extenso análisis experimental que considera varios problemas de benchmark clásicos y dos problemas del mundo real del área de Ingeniería de Software, muestra que el nuevo algoritmo propuesto es muy efectivo, encontrando soluciones óptimas o casi óptimas en tiempos de ejecución cortos. Además, los resultados numéricos obtenidos por SGS son competitivos con los resultados del estado del arte para los dos problemas del mundo real en cuestión. Por otro lado, la implementación paralela en GPU de SGS ha logrado un alto rendimiento, obteniendo grandes reducciones de tiempo de ejecución con respecto a la implementación secuencial y mostrando que escala adecuadamente cuando se consideran instancias de tamaño creciente. También se ha realizado un análisis teórico de las capacidades de búsqueda de SGS para comprender cómo algunos aspectos del diseño del algoritmo afectan a sus resultados numéricos. Este análisis arroja luz sobre algunos aspectos del funcionamiento de SGS que pueden utilizarse para mejorar el diseño del algoritmo en futuras variantes.

Se ha demostrado que las neuronas grilla y de lugarjuegan un rol importante en la cognición espacial de las ratas,. Las neuronas grilla proporcionan un odómetro neuronal para la integración de trayectorias a partir de información propioceptiva. Por otro lado las neuronas de lugar combinan información multimodal, alotética e idiotética, para formar una representación global de la localizacción en el espacio. En este trabajo se presenta un módulo basado en neuronas grilla y su integración a un modelo de cognición espacial teniendo en cuenta estudios del comportamiento y la neurofisiología de las ratas. El disparo de las neuronas grilla es generado utilizando un modelo basado en la interferencia de múltiples osciladores. Además se utiliza un lazo de realimentación desde el módulo de neuronas de lugar hacia las neuronas grilla, para tolerar el error acumulado a partir de la integración de la información propioceptiva. El modelo se evalúa en entornos robóticos simulados y reales, utilizando un protocolo de experimentación diseñado para ser utilizado con ratas, para estudiar las estrategias de localización espacial y en un experimento de larga duración para estudiar su tolerancia al error.

Tribunal : Kishor S. Trivedi, Guillermo Durán, Sergio Nesmachnow, Reinaldo Vallejos, Gerardo Rubino, Bruno Tuffin. Esta tesis aborda el problema del cálculo y estimación de la confiabilidad de redes con restricción de diámetro (DCR). Este problema es una generalización del cómputo de la confiabilidad clásica de redes (CLR). Se ha dedicado un esfuerzo considerable al estudio de la confiabilidad, debido a la relevancia que dichas métricas han tomado en contexto de redes reales durante los últimos 50 años, y al hecho de que el problema tiene complejidad computacional NP-hard aún bajo fuertes simplificaciones. La restricción de diámetro ha ganado relevancia debido al surgimiento de contextos en los cuales las latencias o número de saltos de los paquetes impactan en el desempeño de la red; por ejemplo voz sobre IP, P2P e interfaces ricas dentro de aplicaciones web.

Para sistemas que proveen algún tipo de servicio mientras están operativos y dejan de proveerlo cuando fallan, es de interés determinar parámetros como, por ejemplo, la probabilidad de encontrar el sistema en falla en un instante cualquiera, el tiempo medio transcurrido entre fallas, o cualquier medida capaz de reflejar la capacidad del sistema para proveer servicio. Las determinaciones de estas medidas de seguridad de funcionamiento se ven afectadas por diversos factores, entre ellos, el tamaño del sistema y la rareza de las fallas. En esta tesis se estudian algunos métodos concebidos para determinar estas medidas sobre sistemas grandes y altamente confiables, es decir sistemas formados por gran cantidad de componentes, en los que las fallas del sistema son eventos raros. Ya sea en forma directa o indirecta, parte de las las expresiones que permiten determinar las medidas de interés corresponden a la probabilidad de que el sistema se encuentre en algún estado de falla. De un modo u otro, estas expresiones evaluan la fracción —ponderada por la distribución de probabilidad de las configuraciones del sistema—entre el número de configuraciones en las que el sistema falla y la totalidad de las configuraciones posibles. Si el sistema es grande el cálculo exacto de estas probabilidades, y consecuentemente de las medidas de interés, puede resultar inviable. Una solución alternativa es estimar estas probabilidades mediante simulación. Uno de los mecanismos para hacer estas estimaciones es la simulación de tipo Monte Carlo, cuya versión más simple es la simulación en crudo o estándar. El problema es que si las fallas son raras, el número de iteraciones necesario para estimar estas probabilidades mediante simulación estándar con una precisión aceptable, puede resultar desmesuradamente grande. En esta tesis se analizan algunos métodos existentes para mejorar la simulación estándar en el contexto de eventos raros, se hacen análisis de varianza y se prueban los métodos sobre una variedad de modelos. En todos los casos la mejora se consigue a costa de una reducción de la varianza del estimador con respecto a la varianza del estimador estándar. Gracias a la reducción de varianza es posible estimar la probabilidad de ocurrencia de eventos raros con una precisión aceptable, a partir de un número razonable de iteraciones. Como parte central del trabajo se proponen dos métodos nuevos, uno relacionado con Spliting y otro relacionado con Monte Carlo Condicional. Splitting es un método de probada eficiencia en entornos en los que se busca evaluar desempeño y confiabilidad combinados, escasamente utilizado en la simulación de sistemas altamente confiables sobre modelos estáticos (sin evolución temporal). En vi su formulación básica Splitting hace un seguimiento de las trayectorias de un proceso estocástico a través de su espacio de estados y multiplica su número ante cada cruce de umbral, para un conjunto dado de umbrales distribuidos entre los estados inicial y final. Una de las propuestas de esta tesis es una adaptación de Splitting a un modelo estático de confiabilidad de redes. En el método propuesto se construye un proceso estocástico a partir de un tiempo ficticio en el cual los enlaces van cambiando de estado y se aplica Splitting sobre ese proceso. El método exhibe elevados niveles de precisión y robustez. Monte Carlo Condicional es un método clásico de reducción de varianza cuyo uso no está muy extendido en el contexto de eventos raros. En su formulación básica Monte Carlo Condicional evalúa las probabilidades de los eventos de interés, condicionando las variables indicatrices a eventos no raros y simples de detectar. El problema es que parte de esa evaluación incluye el cálculo exacto de algunas probabilidades del modelo. Uno de los métodos propuestos en esta tesis es una adaptación de Monte Carlo Condicional al análisis de modelos Markovianos de sistemas altamente confiables. La propuesta consiste en estimar las probabilidades cuyo valor exacto se necesita, mediante una aplicación recursiva de Monte Carlo Condicional. Se estudian algunas características de este modelo y se verifica su eficiencia en forma experimental. For systems that provide some kind of service while they are operational and stop providing it when they fail, it is of interest to determine parameters such as, for example, the probability of finding the system failed at any moment, the mean time between failures, or any measure that reflects the capacity of the system to provide service. The determination of these measures —known as dependability measures— is affected by a variety of factors, including the size of the system and the rarity of failures. This thesis studies some methods designed to determine these measures on large and highly reliable systems, i.e. systems formed by a large number of components, such that systems’ failures are rare events. Either directly or indirectly, part of the expressions for determining the measures of interest correspond to the probability that the system is in some state of failure. Somehow, this expressions evaluate the ratio —weighted by the probability distribution of the systems’ configurations— between the number of configurations in which the system fails and all possible configurations. If the system is large, the exact calculation of these probabilities, and consequently of the measures of interest, may be unfeasible. An alternative solution is to estimate these probabilities by simulation. One mechanism to make such estimation is Monte Carlo simulation, whose simplest version is crude or standard simulation. The problem is that if failures are rare, the number of iterations required to estimate this probabilities by standard simulation, with acceptable accuracy, may be extremely large. In this thesis some existing methods to improve the standard simulation in the context of rare events are analyzed, some variance analyses are made and the methods are tested empirically over a variety of models. In all cases the improvement is achieved at the expense of reducing the variance of the estimator with respect to the standard estimator’s variance. Due to this variance reduction, the probability of the occurrence of rare events, with acceptable accuracy, can be achieved in a reasonable number of iterations. As a central part of this work, two new methods are proposed, one of them related to Splitting and the other one related to Conditional Monte Carlo. Splitting is a widely used method in performance and performability analysis, but scarcely applied for simulating highly reliable systems over static models (models with no temporal evolution). In its basic formulation Splitting keeps track of the trajectories of a stochastic process through its state space and it splits or multiplies the number of them at each threshold cross, for a given set of thresholds distributed between the initial and the final state. One of the proposals of this thesis is an adaptation of Splitting to a static network reliability model. In the proposed method, a fictitious time stochastic process in which the network links keep changing their state is built, and Splitting is applied to this process. The method shows to be highly accurate and robust. Conditional Monte Carlo is a classical variance reduction technique, whose use is not widespread in the field of rare events. In its basic formulation Conditional Monte Carlo evaluates the probabilities of the events of interest, conditioning the indicator variables to not rare and easy to detect events. The problem is that part of this assessment includes the exact calculation of some probabilities in the model. One of the methods proposed in this thesis is an adaptation of Conditional Monte Carlo to the analysis of highly reliable Markovian systems. The proposal consists in estimating the probabilities whose exact value is needed, by means of a recursive application of Conditional Monte Carlo. Some features of this model are discussed and its efficiency is verified experimentally.

La industria láctea tiene una importancia preponderante en la economía uruguaya por lo que representa un campo interesante para el desarrollo de modelos y herramientas de informática e investigación operativa para la resolución de problemas de interés práctico. Quienes operan los sistemas lecheros deben tomar decisiones sobre como asignar los recursos alimenticios a una demanda rígida representada por el rodeo lechero. Hasta el momento dicha asignación se realiza en forma intuitiva siguiendo ciertas tradiciones y algunas reglas prácticas de manejo. En este trabajo se estudia este problema, formulando distintos modelos de programación matemática que representan con grado de fidelidad creciente distintas aproximaciones a la realidad. En particular, se tiene en cuenta un rodeo con un conjunto de cabezas de ganado, que puede ser de características homogéneas o heterogéneas; y un conjunto de potreros en los que hay disponible pasturas, así como la posibilidad de alimentar con ración en establos; se busca maximizar la producción de leche (o alternativamente el beneficio económico), teniendo en cuenta el balance de energía entre requerimientos (mantenimiento y producción) y oferta (aporte energético de los alimentos consumidos). Estos modelos generan las bases para realizar una asignación de recursos sobre una base racional que puede mejorar los resultados obtenidos de forma intuitiva como usualmente realizan los productores. Se estudian también diversas formas de encontrar soluciones numéricas para estos modelos, las cuales se basan en formulaciones individuales (se identifica individualmente cada vaca del rodeo) o grupales (se identifican grupos de animales). Una posibilidad explorada es la aplicación de métodos de solución basados en Programación Matemática,que por su gran consumo de recursos computacionales solamente logran resolver de forma exacta instancias muy pequeñas del problema (pudiendo también suministrar soluciones aproximadas para instancias de mayor tamaño). Como alternativa, se proponen y estudian implementaciones de Algoritmos Genéticos, basadas en diferentes representaciones, que son capaces de encontrar soluciones de buena calidad en tiempos de cómputo más razonables. El trabajo incluye también resultados experimentales de las diversas propuestas formuladas. Para esto, se desarrolla un conjunto de casos de prueba, de complejidad creciente, y basados en datos reales. Con estos casos, se estudia el comportamiento y limitaciones de los métodos de resolución exacta, así como la precisión obtenida por las diferentes variantes de algoritmos genéticos implementadas. Los resultados permiten verificar que los métodos exactos no son viables para la formulación individual, mientras que los algoritmos genéticos obtienen buenos resultados en tiempos breves incluso en instancias de hasta 4000 animales. Por otra parte, se pudo verificar que al trabajar en grupos de animales el algoritmo exacto es más apropiado que el algoritmo genético, aunque este último también obtuvo muy buenos resultados para las pruebas realizadas incluso en instancias de hasta 10000 vacas; observándose en particular que la codificación basada en grupos tiene una eficiencia mucho mayor que aquella basada en individuos. Además del estudio de precisión y eficiencia computacional, se realiza un análisis de interpretación de los resultados en sus implicancias a nivel del sistema de producción, lo que permite detectar ciertos patrones en el uso de los recursos alimenticios que abren vías para estudios futuros en la temática.

En una red en la que los enlaces están sujetos a fallas aleatorias e independientes la confiabilidad mide la probabilidad de que el conjunto de nodos terminales esté conectado por enlaces operativos. El parámetro de confiabilidad diámetro acotada extiende el concepto de confiabilidad clásica, estableciendo restricciones en el largo de los caminos que comunican a los nodos terminales dos a dos. En general el cálculo exacto de la confiabilidad diámetro acotada tiene complejidad NP-Hard. En estos casos se recurre a aproximaciones basadas en la simulación Monte Carlo. En el contexto de redes altamente confiables técnicas tradicionales como el método Monte Carlo Crudo no logran un buen desempeño en la estimación de la medida de confiabilidad diámetro acotada. Una alternativa es aplicar métodos de reducción de varianza aplicados al cálculo de la confiabilidad diámetro acotada considerando dos nodos terminales: Muestreo por Importancia y Método Recursivo de Reducción de Varianza. Para el Método Recursivo de Reducción de Varianza se requiere también un algoritmo de selección de conjuntos de corte. Se presentan ejemplos numéricos en los que se verifica la mejora en la performance global respecto al Monte Carlo Crudo y se comparan las características y el desempeño de los métodos propuestos.

El desarrollo de la tecnología en el área de las comunicaciones ha derivado diversas líneas de investigación. Entre ellas, la confiabilidad de la red, definida como la probabilidad de que la red permanezca operativa ante fallas eventuales de sus componentes. El cálculo exacto de la probabilidad de funcionamiento de una red vulnerable a fallas es un problema combinatorio perteneciente a la clase NP-difícil. Usualmente se recurre a métodos aproximados para su estimación. El método de Reducción Recursiva de la Varianza (RVR) es una alternativa, que se caracteriza por su bajo costo computacional, particularmente en redes donde la ocurrencia de fallas es un evento raro (probabilidad de falla cercana a 0). Esta tesis se basa en el método RVR aplicado al modelo de arista-confiabilidad diámetro acotada (se asume falla solamente en los enlaces). Este modelo estudia la probabilidad de que la red comunique un conjunto de nodos objetivo a través de caminos de largo acotado. Es el caso de la comunicación por videoconferencia. Se presenta el estado del arte de la medida de arista-confiabilidad clásica (sin restricciones de diámetro) y su generalización, la arista-confiabilidad diámetro acotada. Se desarrolla el análisis cuantitativo de la robustez del método RVR para estimar la aristaconfiabilidad diámetro acotada en escenarios donde la ocurrencia de fallas es un evento raro. Junto con las redes clásicas se incluye el estudio de la red de transporte de la empresa estatal de telecomunicaciones ANTEL. Los resultados indican que si bien el método RVR, en la versión implementada, tiene desempeño computacional ampliamente satisfactorio, no es robusto en redes altamente confiables.

Actualmente el tráfico sobre Internet se encuentra creciendo día a día, siendo la distribución de video el principal impulsor de dicho aumento. Tal como se presenta en [32], hoy en día el 40% del tráfico total de Internet se corresponde con la distribución de contenidos audiovisuales, mientras que se espera que para el 2014 este alcance el 57%. A su vez, dentro de las diferentes formas de distribución de video, la distribución de video en vivo se encuentra creciendo en importancia. Debido a este contexto, en los últimos años se han desarrollado múltiples aplicaciones de streaming entre pares, o también llamados P2PTV (Peer-to-Peer TV). Algunos ejemplos de estas aplicaciones son PPlive [103], TVUnetwork [127], PPstream [104], SopCast [121], etc. Todas aplicaciones con protocolo e implementaciones cerradas.Dada esta realidad, este trabajo se centra en el diseño e implementación de GoalBit,la primer red P2P para la distribución de video en vivo, gratuita y de código abierto. Siguiendo el exitoso enfoque de BitTorrent [19], se diseña el GoalBit Transport Protocol,mediante el cual es posible distribuir un streaming de video en vivo sobre una red de pares. Se define el GoalBit Packetized Stream con el fin de especificar la forma de paquetizar un streaming de audio y video, encapsulándolo dentro del protocolo de transporte. En base a estas especificaciones, se apoya a la comunidad open-source en la implementación de un cliente de referencia llamado GoalBit.Tanto a nivel de pruebas empíricas, como en emulaciones realizadas, se observó que la estrategia de selección de piezas, la cual define que piezas un par debe solicitar a otro, es un factor de gran relevancia en la continuidad y latencia del streaming. En este tesis se extiende el trabajo [109], introduciendo una nueva estrategia de selección de piezas y comparándola con las presentadas en dicho trabajo. Por otro lado, se continua con el trabajo realizado en [110] sobre la medición de la calidad de experiencia mediante la tecnología PSQA, integrando dicha medición al cliente GoalBit,obteniendo de esta manera una visión global y completa del estado de la distribución del streaming en la red. Finalmente, a modo de validar nuestras ideas, se desarrollan un conjunto de extensiones al protocolo GoalBit, entre los que se encuentran el prototipo de una red de distribución de contenidos y un prototipo de un monitor de contenidos genérico. Tanto el cliente GoalBit, como sus extensiones fueron probados en escenarios reales, obteniendo resultados muy prometedores.

This thesis studies the application of sequential and parallel evolutionary algorithms to the scheduling problem in heterogeneous computing and grid environments, a key problem when executing tasks in distributed computing systems. Since the 1990's, this class of systems has been increasingly employed to provide support for solving complex problems using high-performance computing techniques. The scheduling problem in heterogeneous computing systems is an NP-hard optimization problem, which has been tackled using several optimization methods in the past. Among many new techniques for optimization, evolutionary computing methods have been successfully applied to this class of problems. In this work, several evolutionary algorithms in their sequential and parallel variants are specically designed to provide accurate solutions for the problem, allowing to compute an eficient planning for heterogeneous computing and grid environments. New problem instances, far more complex than those existing in the related literature, are introduced in this thesis in order to study the scalability of the presented parallel evolutionary algorithms. In addition, a new parallel micro-CHC algorithm is developed, inspired by useful ideas from the multiobjective optimization field. Eficient numerical results of this algorithm are reported in the experimental analysis performed on both well-known problem instances and the large instances specially designed in this work. The comparative study including traditional methods and evolutionary algorithms shows that the new parallel micro-CHC is able to achieve a high problem solving eficacy, outperforming previous results already reported for the problem and also having a good scalability behavior when solving high dimension problem instances. In addition, two variants of the scheduling problem in heterogeneous environments are also tackled, showing the versatility of the proposed approach using parallel evolutionary algorithms to deal with both dynamic and multi-objective scenarios. Esta tesis estudia la aplicación de algoritmos evolutivos secuenciales y paralelos para el problema de planicación de tareas en entornos de cómputo heterogéneos y de computación grid. Desde la década de 1990, estos sistemas computacionales han sido utilizados con éxito para resolver problemas complejos utilizando técnicas de computación de alto desempeo. El problema de planificación de tareas en entornos heterogéneos es un problema de optimización NP-difícil que ha sido abordado utilizando diversas técnicas. Entre las técnicas emergentes para optimización combinatoria, los algoritmos evolutivos han sido aplicados con éxito a esta clase de problemas. En este trabajo, varios algoritmos evolutivos en sus versiones secuenciales y paralelas han sido especificamente diseados para alcanzar soluciones precisas para el problema de planicación de tareas en entornos de heterogéneos, permitiendo calcular planificaciones eficientes para entornos que modelan clusters de computadores y plataformas de computación grid. Nuevas instancias del problema, con una complejidad mucho mayor que las previamente existentes en la literatura relacionada, son presentadas en esta tesis con el objetivo de analizar la escalabilidad de los algoritmos evolutivos propuestos. Complementariamente, un nuevo método, el micro-CHC paralelo es desarrollado, inspirado en ideas ítiles provenientes del área de optimización multiobjetivo. Resultados numéricos precisos y eficientes se reportan en el análisis experimental realizado sobre instancias estándar del problema y sobre las nuevas instancias especificamente diseñadas en este trabajo. El estudio comparativo que incluye a métodos tradicionales para planificación de tareas, los nuevos métodos propuestos y algoritmos evolutivos previamente aplicados al problema, demuestra que el nuevo micro-CHC paralelo es capaz de alcanzar altos valores de eficacia, superando a los mejores resultados previamente reportados en la literatura del área y mostrando un buen comportamiento de escalabilidad para resolver las instancias de gran dimensión. Además, dos variantes del problema de planificación de tareas en entornos heterogéneos han sido inicialmente estudiadas, comprobándose la versatilidad del enfoque propuesto para resolver las variantes dinámica y multiobjetivo del problema.

Esta tesis presenta un estudio de la metaheurïstica Ant Colony Optimization (ACO) y de la aplicación de técnicas de computación de alto desempeño a dicha metaheurïstica. En particular, se aborda la aplicación de ACO a la resolución del Problema de Steiner Generalizado (GSP). El GSP consiste en el diseño de una subred de costo mínimo que verifique ciertos requerimientos prefijados de conexión entre pares de nodos distinguidos. En el trabajo se presentan versiones ACO con dos enfoques constructivos de la solución distintos. El primero de los enfoques se basa en incorporar aristas hasta completar un camino, mientras que el segundo determina los K caminos más cortos y realiza una selección entre ellos. También se propone una novedosa formulación de un modelo celular aplicado a la metaheurística ACO y su posible paralelización Se incluye los resultados de un estudio experimental exhaustivo de todas las propuestas formuladas en este trabajo, comprendiendo la evaluación de los enfoques basados en aristas y en caminos y el analizas del efecto del tamaño de la población, de la cantidad de caminos y de incorporar operadores de búsqueda local para el enfoque basado en caminos. El estudio permitió comprobar que la utilización de un enfoque basado en caminos con la incorporación del operador de búsqueda local iterado obtiene resultados competitivos con las mejores técnicas disponibles en la actualidad. Asimismo, se evaluaron las versiones secuencial y paralela del modelo celular propuesto, constatándose que el desempeño computacional de la implementación paralela es muy promisoria, aunque se producen leves pérdidas en la calidad de las soluciones con relación a estructurar la población en la forma tradicional

El uso de redes Peer-to-Peer (P2P) es una forma escalable para ofrecer servicios de video sobre Internet. Este documento hace foco en la definición, desarrollo y evaluación de una arquitectura P2P para distribuir video en vivo. El diseño global de la red es guiado por la calidad de experiencia (Quality of Experience - QoE), cuyo principal componente en este caso es la calidad del video percibida por los usuarios finales, en lugar del tradicional diseño basado en la calidad de servicio (Quality of Service - QoE) de la mayoría de los sistemas. Para medir la calidad percibida del video, en tiempo real y automáticamente, extendimos la recientemente propuesta metodología Pseudo-Subjective Quality Assessment (PSQA). Dos grandes líneas de investigación son desarrolladas. Primero, proponemos una técnica de distribución de video desde múltiples fuentes con las características de poder ser optimizada para maximizar la calidad percibida en contextos de muchas fallas y de poseer muy baja señalización (a diferencia de los sistemas existentes). Desarrollamos una metodología, basada en PSQA, que nos permite un control fino sobre la forma en que la señal de video es dividida en partes y la cantidad de redundancia agregada, como una función de la dinámica de los usuarios de la red. De esta forma es posible mejorar la robustez del sistema tanto como sea deseado, contemplando el límite de capacidad en la comunicación. En segundo lugar, presentamos un mecanismo estructurado para controlar la topología de la red. La selección de que usuarios servirán a que otros es importante para la robustez de la red, especialmente cuando los usuarios son heterogéneos en sus capacidades y en sus tiempos de conexión. Nuestro diseño maximiza la calidad global esperada (evaluada usando PSQA), seleccionado una topología que mejora la robustez del sistema. Además estudiamos como extender la red con dos servicios complementarios: el video bajo demanda (Video on Demand - VoD) y el servicio MyTV. El desafío en estos servicios es como realizar búsquedas eficientes sobre la librería de videos, dado al alto dinamismo del contenido. Presentamos una estrategia de "caching" para las búsquedas en estos servicios, que maximiza el número total de respuestas correctas a las consultas, considerando una dinámica particular en los contenidos y restricciones de ancho de banda. Nuestro diseño global considera escenarios reales, donde los casos de prueba y los parámetros de configuración surgen de datos reales de un servicio de referencia en producción. Nuestro prototipo es completamente funcional, de uso gratuito, y basado en tecnologías bien probadas de código abierto.

This thesis presents a challenging telecommunication network design problem, in which the network designer has to assure not only connectivity, but also some degree of performance guarantee and survivability to the solution. We introduce a topological and capacity design, with node-pair constraints of heterogeneous bounds. These constraints take into account the throughput, the number of node-disjoint paths, and the maximum number of hops. Moreover, the capacity to place on each link is chosen from a pool of available cable types, each with its maximum capacity and fixed cost, in other words the cost function is stepwise with respect to capacity usage. The solution space of the problem in study is composed by each one of the node-pair demands. An in-depth combinatorial study was done, leading to the development of a new coding for genetic

Se presenta una propuesta docente para introducir el concepto de algoritmos recursivos en cursos de matemática o ciencia de la computación a nivel de estudios pre-universitarios. La estrategia de la propuesta se basa en la integración de la construccción por parte de los estudiantes tanto del concepto de recursión como de la correspondencia entre este y su formulación en el proceso de aprendizaje. La construcción del concepto por parte de los estudiantes es investigada en el marco de la teoría de Jean Piaget, Epistemología Genética. Específicamente, el principio según el cual el origen del razonamiento por recurrencia es inherente a la contrucción de la serie de los números naturales. (La Formation des Raisonemments Recurrentiels, Jean Piaget, 1963), es extendido al razonamiento sobre otras estructuras, dando lugar a la siguiente premisa: la fuente de pensamiento que hace posible diseñar soluciones recursivas de problemas se encuentra en formas elementales de razonar que surgen de la comprensión por parte de los estudiantes de las relaciones entre los elementos a los cuales sus acciones son aplicadas cuando intentan resolver instancias de problemas. Se presenta el trabajo empírico realizado para investigar la transformación del conocimiento instrumental de los estudiantes al conceptual y la construcción de la correspondencia entre el concepto y su formalización. Se propone usar como formalismos la matemática y ciencia de la computación y el trabajo conjunto de sus educadores, son esenciales para superar numerosos obstáculos en el aprendizaje de conceptos compartidos para ambas disciplinas. La propuesta docente deriva de los resultados del análisis de la información obtenida en entrevistas individuales y clases colectivas realizadas con estudiantes pre-universitarios. Aún considerando el caracter experimental de las mismas, se ha identificado cierta evidencia del impacto de la estrategia en el aprendizaje efectivo del concepto y su aplicación en el diseño de algoritmos recursivos. Finalmente, este trabajo toma en consideración la necesidad de establecer lazos entre la investigación en educación en ciencia de la computación y en marcos teóricos pertenecientes a disciplinas relacionadas con el campo de la educación. De esta forma pretende contribuir al establecimiento del área como una disciplina académica.