ARAÚJO, P. H. M. Uma Heurística Langrangeana para o Problema de Ponderação de Rodadas. 2014. 84 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T20:24:27Z No. of bitstreams: 1 2014_dis_phmaraujo.pdf: 2899415 bytes, checksum: 09eb89cd95ed8aaebf416937c1fd27ac (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-02-09T15:42:02Z (GMT) No. of bitstreams: 1 2014_dis_phmaraujo.pdf: 2899415 bytes, checksum: 09eb89cd95ed8aaebf416937c1fd27ac (MD5) / Made available in DSpace on 2015-02-09T15:42:02Z (GMT). No. of bitstreams: 1 2014_dis_phmaraujo.pdf: 2899415 bytes, checksum: 09eb89cd95ed8aaebf416937c1fd27ac (MD5) Previous issue date: 2014 / In this dissertation, our main objective was to develop a technique for resolution to a problem in the area of telecommunications. The problem in question is called Round Weighting Problem (RWP) and was originally proposed in (KLASING; MORALES; P eRENNES, 2008). The context of the problem involves a wireless network where communications are performed by radio waves and the network operates through a network operation that satis es the constraints of the problem. Initially, we explain how a radio network is formed and describe the mode of operation of the radio network with restrictions using a mathematical model. Then, we formalize the RWP as an optimization problem, specifying their restrictions, corresponding to the generation of the set of possible network operations, and optimization criterion, regarding the use of network resources. Subsequently, we show a preliminary study of the Fractional Coloring problem (FC problem) and present a technique to solve this problem through the use of a lagrangian heuristic based on a lagrangian relaxation of an integer programming formulation of the problem. This resolution technique is then adapted to the RWP, consisting in the main contribution of our research. Finally, we show the computational results and analyzes of our implementations for the Fractional Coloring problem and RWP. / Nesta dissertação, nosso principal objetivo foi desenvolver uma técnica de resolução para um problema na área de telecomunicações. O problema em questão é chamado de problema de Ponderação de Rodadas (PR) e foi inicialmente proposto em [Klasing,Morales,Perennes, 2008]. O contexto do problema envolve uma rede sem fio, onde as comunicações são realizadas via ondas de rádio e a rede funciona através de uma operação da rede que satisfaz certas restrições. Inicialmente, explicamos como é formada uma rede de rádio e descrevemos a forma de operação da rede de rádio junto às restrições usando um modelo matemático. Em seguida, formalizamos o problema PR como um problema de otimização, especificando suas restrições, correspondente à geração do conjunto de possíveis operações da rede, e critério de otimização, referente ao uso dos recursos da rede. Posteriormente, mostramos um estudo preliminar do problema de Coloração Fracionária (CF) e apresentamos uma técnica de resolução deste problema através do uso de uma heurística lagrangeana baseada em uma relaxação lagrangeana de uma formulação de programação inteira do problema. Essa técnica de resolução é então adaptada para o problema PR, consistindo na principal contribuição de nossa pesquisa. Por fim, mostramos os resultados computacionais e análises das nossas implementações para os problemas CF e PR.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia de Automação e Sistemas, Florianópolis, 2016. / Made available in DSpace on 2017-05-23T04:10:14Z (GMT). No. of bitstreams: 1 345231.pdf: 9548916 bytes, checksum: 8d41b495c44f19df25a19bfa13d74723 (MD5) Previous issue date: 2016 / Abstract : The evolution of CMOS technology made possible integrated circuits with billions of transistors assembled into a single silicon chip, giving rise to the jargon Very-Large-Scale Integration (VLSI). The required clock frequency affects the performance of a VLSI circuit and induces timing constraints that must be properly handled by synthesis tools. During the physical synthesis of VLSI circuits, several optimization techniques are used to iteratively reduce the number of timing violations until the target clock frequency is met. The dramatic increase of interconnect delay under technology scaling represents one of the major challenges for the timing closure of modern VLSI circuits. In this scenario, effective interconnect synthesis techniques play a major role. That is why this thesis targets two timing optimization problems for effective interconnect synthesis: Incremental Timing-Driven Placement (ITDP) and Incremental Timing-Driven Layer Assignment (ITLA). For solving the ITDP problem, this thesis proposes a new Lagrangian Relaxation formulation that minimizes timing violations for both setup and hold timing constraints. This work also proposes a netbased technique that uses Lagrange multipliers as net-weights, which are dynamically updated using an accurate timing analyzer. The netbased technique makes use of a novel discrete search to relocate cells by employing the Euclidean distance to define a proper neighborhood. For solving the ITLA problem, this thesis proposes a network flow approach that handles simultaneously critical and non-critical segments, and exploits a few flow conservation conditions to extract timing information for each net segment individually, thereby enabling the use of an external timing engine. The experimental validation using benchmark suites derived from industrial circuits demonstrates the effectiveness of the proposed techniques when compared with state-of-the-art works.<br> / A evolução da tecnologia CMOS viabilizou a fabricação de circuitos integrados contendo bilhões de transistores em uma única pastilha de silício, dando origem ao jargão Very-Large-Scale Integration (VLSI). A frequência-alvo de operação de um circuito VLSI afeta o seu desempenho e induz restrições de timing que devem ser manipuladas pelas ferramentas de síntese. Durante a síntese física de circuitos VLSI, diversas técnicas de otimização são usadas para iterativamente reduzir o número de violações de timing até que a frequência-alvo de operação seja atingida. O aumento dramático do atraso das interconexões devido à evolução tecnológica representa um dos maiores desafios para o fluxo de timing closure de circuitos VLSI contemporâneos. Nesse cenário, técnicas de síntese de interconexão eficientes têm um papel fundamental. Por este motivo, esta tese aborda dois problemas de otimização de timing para uma síntese eficiente das interconexões de um circuito VLSI: Incremental Timing-Driven Placement (ITDP) e Incremental Timing-Driven Layer Assignment (ITLA). Para resolver o problema de ITDP, esta tese propõe uma nova formulação utilizando Relaxação Lagrangeana que tem por objetivo a minimização simultânea das violações de timing para restrições do tipo setup e hold. Este trabalho também propõe uma técnica que utiliza multiplicadores de Lagrange como pesos para as interconexões, os quais são atualizados dinamicamente através dos resultados de uma ferramenta de análise de timing. Tal técnica realoca as células do circuito por meio de uma nova busca discreta que adota a distância Euclidiana como vizinhança.Para resolver o problema de ITLA, esta tese propõe uma abordagem em fluxo em redes que otimiza simultaneamente segmentos críticos e não-críticos, e explora algumas condições de fluxo para extrair as informações de timing para cada segmento individualmente, permitindo assim o uso de uma ferramenta de timing externa. A validação experimental, utilizando benchmarks derivados de circuitos industriais, demonstra a eficiência das técnicas propostas quando comparadas com trabalhos estado da arte.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2014. / Made available in DSpace on 2015-03-18T21:02:06Z (GMT). No. of bitstreams: 1 332281.pdf: 4170079 bytes, checksum: c52c7417e7cc9dfabdf49d0d77f3d017 (MD5) Previous issue date: 2014 / Um grande número de problemas relacionados com o planejamento e a operação de sistemas de energia elétrica resultam em modelos de otimização de grande escala, não-lineares, inteiro-mistos e, consequentemente, não-convexos. Devido à presença de diversas restrições que acoplam o problema, a Relaxação Lagrangiana surge como uma abordagem natural como metodologia de solução, pois permite a decomposição do problema em subproblemas menores e independentes entre si. A teoria da dualidade garante que a função dual oferece limites inferiores para o problema primal de minimização. Além disso, a solução do problema dual fornece o melhor limite inferior possível e um bom ponto de partida para a etapa de recuperação primal. Como o problema dual é convexo mas não-diferenciável, algoritmos especializados de otimização precisam sem empregados. Os Métodos de Feixes estão entre os mais eficientes desses algoritmos e são tipicamente utilizados quando acurácia na solução e confiabilidade são uma preocupação. Nesta dissertação é realizada a análise comparativa de três variantes dos Métodos de Feixes para um problema de comissionamento de unidades geradoras termelétricas composto de 46 barras, 10 geradores e horizontes de planejamento de 24 a 168 horas. Resultados mostram que os Métodos de Feixes têm êxito na obtenção de uma boa solução para o problema dual.<br> / Abstract : A large number of problems related to the planning and operation of electrical power systems result in optimization models which are large-scale, nonlinear, mixed-integer, and thus nonconvex. Due to the presence of multiple coupling constraints, Lagrangian Relaxation appears as a natural approach for dealing with this kind of problems: it allows decomposing the problem into smaller and independent subproblems. Duality theory says that the resulting dual optimization problem gives lower bounds for the considered primal minimization problem. Moreover, solving the dual problem provides the best possible lower bound and a good starting point for primal recovery. Since the dual problem is convex but nonsmooth, specialized optimization algorithms need to be employed. Bundle methods are among the most efficient of these methods, and are used when accuracy in the solution and reliability are a concern. We assess the performance of three Bundle Methods variants using a Thermal Unit Commitment problem composed of 46 buses, 10 thermal generating units and planning horizons ranging from 24 to 168 hours. Results show that Bundle Methods succeed in obtaining a good solution for the dual problem.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2013. / Made available in DSpace on 2013-12-05T23:12:19Z (GMT). No. of bitstreams: 1 318856.pdf: 1230228 bytes, checksum: e1a7c96794e382372e29e54b3e261525 (MD5) Previous issue date: 2013 / A minimização da corrente de leakage é um passo essencial do projeto de circuitos digitais, uma vez que nas tecnologias CMOS recentes a potência de leakage tornou-se comparável à potência dinâmica. Gate sizing é uma técnica amplamente utilizada para minimização da potência de leakage devido à sua eficácia e ao baixo impacto que ele causa no fluxo standard cell. Em tal fluxo, o problema de sizing corresponde a selecionar, para cada porta do circuito, uma combinação de largura de porta e tensão de threshold disponível na biblioteca de células, de modo a satisfazer as restrições de projeto. A natureza discreta do problema, a qual o torna NP-difícil, e o grande número de portas nos circuitos contemporâneos têm motivado a busca por heurísticas eficientes, que sejam capazes de resolvê-lo em tempo de execução aceitável. Este trabalho apresenta três contribuições principais ao estado da arte. A primeira é uma formulação aperfeiçoada para o problema de sizing discreto baseada em Relaxação Lagrangeana (LR), a qual considera valores máximos de slew de entrada e de capacitância de saída das portas, impostas pelas bibliotecas standard cell. A segunda é uma heurística topológica gulosa para resolver a formulação LR proposta utilizando informações locais para guiar as decisões do algoritmo. A terceira contribuição reside em uma técnica híbrida de três passos para superar algumas das limitações da heurística topológica gulosa. Tal técnica híbrida inicia resolvendo a formulação LR assumindo um atraso crítico ligeiramente maior do que o atraso crítico-alvo e em seguida, aplica uma heurística rápida de recuperação de atraso para que o atraso crítico-alvo original seja satisfeito. Como terceiro passo, é usada uma heurística de recuperação de potência para reduzir ainda mais a potência de leakage explorando o espaço para otimização deixado pelos dois passos anteriores. Os experimentos práticos foram gerados utilizando-se a infraestrutura da Competição de Sizing Discreto do ISPD2012, a qual provê uma base comum para comparações justas com os trabalhos correlates mais recentes. Os resultados experimentais para a formulação LR usando a heurística topológica gulosa foram comparados com os resultados obtidos pelas três equipes melhor classificadas na Competição do ISPD 2012, os quais representavam o estado da arte no momento em que tais experimentos foram realizados. A potência de leakage obtida é, em média, 18,9%, 16,7% e 43,8% menor do que aquelas obtidas pelas três melhores equipes da Competição do ISPD2012, respectivamente, ao passo que o tempo de execução total é 38, 31 e 39 vezes menor. Com relação à técnica híbrida, a potência de leakage obtida é, em média, 8,15\\\\% menor do que aquela relatada pelo trabalho que representa o estado da arte na ocasião em que estes experimentos foram realizados, sendo o tempo total de execução uma ordem de magnitude menor. É Importante ressaltar que o trabalho estado da arte referido já havia superado as três melhores equipes da Competição do ISPD2012. <br>

Submitted by Danielle Karla Martins Silva (danielle.martins@ufpe.br) on 2015-03-12T15:32:44Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao_Frederico_Elihimas.pdf: 590657 bytes, checksum: 622161b46c696fcae55aa7fc7defd886 (MD5) / Made available in DSpace on 2015-03-12T15:32:44Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) dissertacao_Frederico_Elihimas.pdf: 590657 bytes, checksum: 622161b46c696fcae55aa7fc7defd886 (MD5) Previous issue date: 2013 / CNPq / Este trabalho faz, preliminarmente, um estudo da Álgebra Linear Simplética. Este estudo é crucial para uma introdução à estrutura da Grassmanniana Lagrangeana para então ser de nido o Índice de Maslov para curvas nesta variedade

El objetivo general del presente trabajo de título es realizar, mediante la aplicación de criterios técnicos de ingeniería, una evaluación técnica del desempeño de los algoritmos de Relajación Lagrangeana (RL) y Branch and Bound (B&B) en la búsqueda de soluciones para el problema de optimización de corto plazo en el sistema eléctrico interconectado del norte grande (SING). En la primera parte de la memoria se muestra el planteamiento general del problema de optimización de la operación de corto plazo, el cual corresponde a un problema de optimización entero-mixto y un conjunto de restricciones lineales mediante las cuales se establecen las características técnicas del sistema. Por otra parte, la función objetivo de dicho problema de optimización corresponde a la minimización de los costos asociados a la operación de las unidades en el horizonte de tiempo evaluado. Posteriormente, se muestra una revisión del estado del arte presentando algunas de las principales técnicas utilizadas para resolver este tipo de problema: Lista de Prioridad, Programación Dinámica, Unit Decommitment, RL, Método de Benders, B&B y Algoritmos Genéticos. Para realizar la evaluación sobre los algoritmos de RL y B&B, se realizan programas en Matlab de dichos métodos con el objeto de realizar pruebas que permitan efectuar un análisis comparativo de los rendimientos de ambos algoritmos. Se aplican dichos programas para resolver problemas de predespacho en un modelo reducido del SING. De esta forma se puede observar el rendimiento de cada algoritmo respecto de su capacidad de obtener soluciones factibles, calidad de las soluciones, uso de heurística para generar soluciones y tiempos de ejecución requeridos. Adicionalmente, se puede estudiar la flexibilidad de ambos algoritmos para considerar restricciones de mayor complejidad y sus limitaciones para resolver predespacho en sistemas de dimensiones reales. Se concluye que el algoritmo que presenta un rendimiento que permite resolver de manera más eficiente el problema de predespacho en el SING corresponde al algoritmo RL, lo anterior debido principalmente a los tiempos de ejecución requeridos para su aplicación en sistemas de dimensiones reales y a que las soluciones generadas presentan una precisión del orden del 99% respecto a las soluciones generadas por el otro algoritmo. Adicionalmente, se puede acotar que las actuales políticas de operación aplicadas en el SING no representan una gran complejidad de programación y por lo tanto, la heurística requerida no presenta una complejidad adicional.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Elétrica, Florianópolis, 2009 / Made available in DSpace on 2012-10-24T20:54:05Z (GMT). No. of bitstreams: 1 271856.pdf: 4759615 bytes, checksum: a55c7147f3f06f74758a645d8a1c486d (MD5) / A Programação da Operação do Sistema Elétrico pode ser formulada por um problema de otimização cujo objetivo é a minimização do custo de operação e atendendo a um conjunto de restrições associadas ao sistema e às unidades de produção. Em sistemas hidrotérmicos, a fim de se assegurar o uso eficiente dos recursos disponíveis e a obtenção de soluções viáveis, torna-se necessária usar uma modelagem detalhada tanto das fontes hidrelétricas como das termelétricas. Conseqüentemente, tem-se um problema de grande porte e não convexo, cuja solução não é trivial. Particularmente, neste projeto consideram se as não linearidades das funções de produção das fontes termelétricas e hidrelétricas, bem como todas as restrições relevantes para cada tipo de fonte, tais como restrições de rampa e zonas proibidas de operação, entre outras. Adicionalmente, modelam-se as restrições dos intercâmbios de transmissão e a função de custo futuro para as hidrelétricas. Como solução desse problema tem-se um programa de geração horário para um horizonte de dois dias. Dada a dificuldade de se resolver o problema em referência, propõe-se o uso da técnica de Relaxação Lagrangeana a qual tem sido usada com êxito em problemas semelhantes. Nesse contexto, decompõe-se o problema original nos subproblemas de atendimento à demanda, hidráulico, de alocação de unidades hidrelétricas e de alocação de unidades termelétricas. Uma vez que a solução dual é infactível, este trabalho utiliza a técnica do Lagrangeano Aumentado Inexato para realizar a Recuperação Primal, utilizando o mesmo esquema de decomposição proposto. Assim é possível obter uma solução viável para o problema da programação da operação eletroenergética. Os algoritmos implementados são testados com uma configuração do sistema baseado no caso brasileiro. Nos resultados obtidos, são analisados os esforços computacionais, inviabilidade da solução dual, perfis de geração hidrelétrica e termelétrica, recuperação primal e o uso da função de custo futuro. / The short-term hydrothermal scheduling of a power system can be formulated as anoptimization problem that aims to minimize the operating cost and meet a set of constraints associated with the system and the generating units. Particularly, in hydrothermal systems, in order to ensure the efficient use of the available resources, it is necessary to use a detailed modeling for hydro and thermal plants and, as a consequence, it is obtained a huge and nonconvex problem, whose solution is not trivial. In this work, we consider the nonlinearities associated with the production functions of hydro and thermal plants, as well as all the relevant constraints associated with each type of technology, such as ramping constraint for thermal plants and forbidden operating zones for hydro plants. Additionally, the transmission capacity between subsystems and the value of the water in the future for hydro plants are modeled. The solution for this problem is calculated for a two day horizon with hourly steps . Given the difficulty to solve the problem aforementioned the Lagrangian Relaxation technique is proposed, which has been successfully applied in similar problems. By this technique, the original problem is decomposed into smaller subproblems easier to solve. Given that the dual solution is unfeasible, this work makes use of the Inexact Aumented Lagrangian to perform the primal recovery in order to ensure a feasible solution. Based on these principles, a set of algorithms were developed and implemented resulting in a computational model that was tested for the Brazilian system. By means of this application, a detailed analysis with respect to the computational burden and solution quality is presented. The results allow us to conclude that the proposed model is useful to be applied in real life problems.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica. / Made available in DSpace on 2012-10-20T16:23:05Z (GMT). No. of bitstreams: 1 197468.pdf: 14614571 bytes, checksum: dfd09f23e1ae2d4456a2d37c269d62f0 (MD5) / O planejamento da operação de sistemas hidrotérmicos com predominância hidrelétrica possui características matemáticas as quais determinam que o problema correspondente seja solucionado de forma aproximada a partir de três outros problemas: planejamento da operação de médio prazo e de curto prazo, e a programação da operação energética. Os problemas referentes às etapas de médio e curto prazo possuem um ferramental bastante desenvolvido, sendo resultado do desenvolvimento técnico-metodológico obtido no setor elétrico ao longo das três últimas décadas. Todavia, desenvolvimento semelhante não ocorreu com o problema da programação, cujas principais contribuições têm sido restritas a sistemas termelétricos. Este trabalho visa fornecer uma contribuição para os aspectos ligados a formulação e solução do modelo da programação da operação, onde a modelagem do sistema hidrelétrico recebe atenção especial devido à predominância desse recurso no sistema brasileiro. Assim, neste trabalho é proposta uma modelagem detalhada da função de produção das unidades hidrelétricas que leva em consideração as não-linearidades presentes na cota de jusante, perdas hidráulicas, rendimentos do grupo turbina-gerador e, adicionalmente, a existência de múltiplos estados operativos relacionados com as zonas proibidas de operação. O problema resultante é de natureza não-linear, inteira-mista e de grande porte. Nesse sentido, este trabalho faz uso de diversas técnicas de programação matemática que decompõem o problema original em uma série de subproblemas mais simples de serem solucionados. Uma configuração hidrelétrica realista é utilizada para ilustrar o desempenho da estratégia de solução, aplicada ao problema hidrelétrico, onde as viabilidades conceitual e prática do modelo proposto podem ser comprovadas a partir da qualidade das soluções e dos tempos de processamento observados.

Ingeniero Civil Industrial / En esta memoria se utilizará el método de Relajación Lagrangeana a un problema de la vida real en el área de la planificación forestal. A esta planificación, además, se le agregará incertidumbre en el precio de las maderas, en base a la consideración de un número N de escenarios, lo cual aumenta la dificultad para la resolución de la instancia, lo que lleva a que se quiera evaluar el desempeño de este enfoque para la resolución de problemas con estas características. El objetivo principal del proyecto es lograr encontrar una solución cercana al óptimo para un modelo de programación lineal estocástico buscando maximizar el beneficio neto de la planificación de la cosecha de bosques, para instancias con más de 200 escenarios a partir de una Relajación Lagrangeana del problema y evaluar el desempeño de este enfoque conforme al número de escenarios y en comparación a CPLEX. Para lograr esto, se empleó la siguiente metodología: 1. Entender la Importancia de la evaluación de esta herramienta. 2. Plantear el Modelo de Programación Lineal Estocástico acorde al problema forestal. 3. Indagación en Bibliografía de la Relajación Lagrangeana. 4. Elección de restricciones a relajar, desarrollo de algoritmo y heurística de la Relajación Lagrangeana. 5. Análisis de los Resultados. Al evaluar los resultados, se pudo notar que la Relajación Lagrangeana no tenía un comportamiento estable al resolver el problema con un grafo de 290 arcos, 223 nodos y 15 bosques, esto comparado con casos más pequeños en el que su comportamiento es más típico en cuanto a la suavidad del descenso de la curva hacia el óptimo. A pesar de ello, se logró mejorar su comportamiento al normalizar los multiplicadores en cada iteración. Se emplearon métodos en que se fijaron variables binarias al valor 1, cuando cumplían en cierto grado las restricciones de no anticipatividad. Esto acompañado con la técnica de Warm Start entregaron resultados satisfactorios hasta los 162 escenarios, donde los tiempos de la Relajación Lagrangeana se dispararon dejando una fuerte impresión de que la metodología puede no ser la más adecuada para este tipo de problemas. Sin embargo, esto puede estar sesgado por la elección del software y/o las metodologías de programación empleadas por el alumno, por lo que no se considera definitivo el que se deba cerrar la investigación de esta metodología para los problemas de índole forestal.

Magíster en Ciencias de la Ingeniería, Mención Ingeniería Eléctrica / El trabajo de tesis compara en forma sistemática las diferencias de rendimiento entre las principales metodologías de solución del problema de Predespacho (UC) y muestra la aplicación de la relajación lagrangeana a casos reales del Sistema Interconectado del Norte Grande (SING). Se propone una metodología para la creación de casos sintéticos de UC que permitan obtener diversidad a distintas escalas sin que resulten alejados de la realidad, siendo ésta la principal contribución del presente trabajo junto con los resultados estadísticos que favorecen MIP por sobre LR para sistemas de medianas dimensiones. La relajación lagrangeana (LR) y la programación entero mixta (MIP) son los métodos de solución que han encontrado el mayor número de aplicaciones prácticas al UC. Sin embargo, las comparaciones de rendimiento y calidad entre ambas, aunque propuestas conceptualmente y cuyas nociones intuitivas se encuentran dispersas en la bibliografía especializada, adolecen de falta de generalidad, escasa representación de la realidad, ausencia de especificaciones computacionales o, inclusive, éstas pueden haber quedado obsoletas. Ante la escasez de librerías de modelos de UC o, al menos, de métodos de creación de casos de aplicación, en el presente trabajo se propone y aplica un generador de casos sintéticos de prueba de UC. Este método formula casos basados en la combinación de datos estandarizados con la generación aleatoria de parámetros. De esta forma, los problemas de UC creados adquieren diversidad (universalidad) sin que las instancias se alejen demasiado de la realidad. La diversidad de las instancias generadas es controlada mediante los parámetros de las funciones de distribución de probabilidades, tanto para la selección de unidades candidatas como para la variedad en los parámetros técnicos característicos. Estas instancias son resueltas por los métodos para resolver el UC en una misma plataforma computacional. El método de LR encuentra soluciones factibles para 429 instancias de las 480 (89,4%), cumpliendo con el gap objetivo de 0,01% en tan sólo 90 casos (18,8%), mientras que el MIP encuentra la solución óptima para el 98,3% de los casos. Los resultados obtenidos verifican que para el rango de 10 a 100 unidades, la mejor solución entera factible alcanzada por LR tiene una menor calidad (valor mayor de la función objetivo en problemas de minimización) que la encontrada por el optimizador MIP. Los resultados permiten determinar que el sobrecosto (respecto al MIP) esperado de las soluciones mediante LR fue de 6,03%. El aumento de la dispersión en los parámetros técnicos beneficia ambos métodos al obtener la mejor solución factible en menores tiempos de ejecución. De esta forma se muestra que no sólo la calidad de la solución por LR se ve afectada por unidades similares, sino que también afecta al método MIP. Se comprueba que a medida que los problemas son más difíciles (juzgando por la adaptabilidad y por el número de unidades), la cota inferior de LR resulta en promedio mayor (mejor) a la cota inferior promedio por MIP. Respecto al caso práctico inspirado en el SING, la calidad de la solución por LR se ve especialmente deteriorada cuando las restricciones de mínimos técnicos de las unidades obligan que la solución óptima entera se aleje de la relajación lineal. Si bien para este caso la resolución mediante MIP también se dificulta requiriendo de hasta un 60% más tiempo de ejecución, este efecto es comparativamente menor al deterioro de la calidad de la solución observada mediante LR (que resulta hasta 4.5% mayor que MIP). Conceptualmente, este hallazgo se explica por los valores de actualización de los multiplicadores en LR, lo que se traduce en imposibilidad para explorar zonas del espacio de soluciones. Como conclusión general, el estudio entrega evidencia práctica a favor de la tendencia observada en la revisión bibliográfica en relación a privilegiar desarrollos de tipo MIP, la cual es aplicable a sistemas medianos como el caso real en estudio basado en el SING chileno. Esta conclusión no se extiende para otros sistemas reales de grandes dimensiones (eg. CAISO, MISO, UCTE). Como futuros desarrollos se sugiere explorar esquemas integrados LR-MIP explotando las mejoras de la cota inferior que proporciona LR en comparación con la relajación lineal del MIP y la creación de soluciones factibles por el método LR para inicializar el MIP.