Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / Esta tesis propone un método para construir redes de regulación causales realistas, que tienen una tasa de falsos positivos más baja que las redes construidas con los métodos tradicionales. La primera contribución de esta tesis es integrar información heterogénea a partir de dos tipos de predicciones de red para determinar una explicación causal de las co-expresiones de genes observada. La segunda contribución de esta tesis es modelar esta integración como un problema de optimización combinatorial. Analizamos la complejidad computacional de este enfoque y demostramos que este problema y mostramos que este problema pertenece a la categoría complejidad NP-hard. Este análisis fue aceptado en la 15ª Conferencia Internacional de Verificación, Modelo de Control, e interpretación abstracta VMCAI 2014. Con el fin de tener una solución aproximada en un tiempo de ejecución práctico se propone también un enfoque heurístico. Esta es la tercera contribución de esta tesis. Nuestra evaluación en E.coli muestra que la red resultante de la aplicación de este método tiene una mayor precisión que la red de regulación putativa construida con herramientas tradicionales. Una publicación sobre este tema se somete a PLoS Computational Biology. La bacteria Acidithiobacillus ferrooxidans, que tiene importantes aplicaciones industriales, presenta retos particulares para la determinación experimental de la red de regulación. Usando las herramientas que hemos desarrollado hemos podido proponer una red de regulación putativa y analizarla para poner en relevancia el papel de los reguladores centrales. Esta es la cuarta contribución de esta tesis. En una segunda parte de esta tesis exploramos cómo estas relaciones regulatorias se manifiestan en un caso vinculado a la salud humana, desarrollando un método para completar una red vinculada a la enfermedad de Alzheimer. Este trabajo fue publicado en BMC Genomics (2010). Como addendum a esta tesis abordamos el problema matemático de diseñar sondas de microarray. Concluimos que para predecir completamente la dinámica de hibridización se necesita un modelo modificado para la energía de las estructuras secundarias de ADN adherido a una superficie y proponemos un plan para determinar tal función.

Magíster en Gestión de Operaciones / Ingeniero Civil Industrial / Muchos problemas de optimización consideran al precio del cobre como uno de los input más relevantes. A pesar de que los precios son altamente volátiles y nadie puede predecir con certeza cual será su valor, éstos pueden ser estimados y árboles de escenarios pueden ser construidos para manejar la incertidumbre asociada. En este trabajo se presenta una nueva metodología para el modelamiento y estimación de los precios del cobre, basada en dos ideas centrales. La primera radica en realizar una distinción entre el corto y el largo plazo (o también referidos como procesos transiente y estacionario), debido a que la evidencia muestra que en el corto plazo los precios son altamente volátiles moviéndose en torno a una tendencia, mientras que en el largo plazo los precios muestran reversión a la media tal como lo sugiere la teoría microeconómica. El segundo aporte central de este trabajo es la combinación de la información de mercado junto a la información histórica para la estimación de la tendencia de los precios en el corto plazo. El uso de la información de mercado resulta relevante ya que permite incorporar toda la información presente en el mercado (inventarios, expectativas, etc...) en la estimación del \drift del proceso transiente, ayudando de esta forma a un mejor pronóstico. Sumado a lo anterior, se presenta una extensión del modelo propuesto para incorporar más de un factor en la estimación de los precios del cobre. Así, se introduce un modelo multi-dimensional (no lineal), se derivan soluciones explícitas y se implementa un mecanismo para la estimación de sus parámetros. Finalmente, se presenta una nueva metodología para la generación de árboles de escenarios partiendo de las funciones de probabilidad acumulada y densidad, y esta se aplica para la generación de árboles de escenarios para los precios del cobre.

Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / Estudiamos el problema de bases de peso mínimo en matroides en un contexto donde los pesos en los elementos son inciertos. Inicialmente, para cada elemento $e$ de una matroide $(E,\I)$ se conocerá un conjunto no vacío $A_e \subseteq \mathbb R$, llamado área de incertidumbre, que contiene los posibles pesos del elemento $e$. El algoritmo puede escoger un conjunto de elementos $X\subseteq E$ a consultar, de manera que si un elemento $e$ es consultado se obtiene un peso $w_e \in A_e$ con un costo de consulta $c_e \in \mathbb R$ asociado. El objetivo es encontrar un conjunto $X \subseteq E$ que, al consultarlo, permita calcular una base de peso mínimo independiente del valor de las aristas no reveladas. A estos conjuntos se les llamará consultas factible; tenemos particular interés en encontrar una de costo mínimo. Esto es de especial interés en aplicaciones donde obtener datos exactos es díficil o costoso, pero datos vagos son de fácil acceso. El problema adaptativo bajo análisis competitivo fue estudiado anteriormente. En este trabajo consideramos el caso no adaptativo; es decir, cuando los elementos a consultar se eligen todos al mismo tiempo. Formalizamos el problema, definimos las bases de peso mínimo en el contexto incierto, caracterizamos su existencia y demostramos que son las bases de una matroide. Proveemos una caracterización de las consultas factibles de tamaño mínimo, probamos que los complementos de consultas factibles forman una matroide sencilla y esto nos permite idear un algoritmo que encuentra una consulta factible de costo mínimo con una cantidad polinomial tanto de recursos computacionales como de llamadas al oráculo de independencia de la matroide / FONDECYT Regular N° 1181180 y CMM - Conicyt PIA AFB170001

Orientador: José Antonio Perrella Balestieri / Coorientador: João Andrade Carvalho Jr. / Banca: Ivonete Ávila / Banca: Christian Jeremi Coronado Rodriguéz / Resumo: Os gases siderúrgicos disponíveis em empresas do setor como resultado de seus principais processos de transformação são o gás de coqueria (COG), o gás de alto forno (BFG) e o gás de aciaria (LDG); que são bastante valorizados pelo fato de minimizarem a necessidade de emprego de gás natural ou outra fonte combustível. As centrais termelétricas estão entre as principais consumidoras desses combustíveis, e a distribuição de combustíveis siderúrgicos para as mesmas é um problema discutido na literatura técnica como uma forma de minimizar os desequilíbrios entre a geração e o consumo dos mesmos. Ao mesmo tempo, busca-se maximizar a eficiência energética da empresa e a confiabilidade/disponibilidade do seu suprimento às unidades consumidoras sem queima direta nas torres de queima (flares). A presente proposta de pesquisa tem por objetivo modelar e propor soluções para a otimização da distribuição de gases combustíveis em centrais termelétricas em ciclo combinado gás/vapor considerando os impactos que a troca de combustíveis operam sobre o acionador principal (no caso, o conjunto a gás) em termos de sua resposta à intercambiabilidade entre combustíveis. As modificações propostas neste trabalho otimizam simultaneamente a distribuição de gases subproduto no sistema de gases siderúrgicos; foram avaliadas 56 combinações de combustíveis, o que resultou numa faixa de potência ideal para a aplicação do estudo entre 30 MW e 80 MW, e outra faixa entre 10 MW e 30 MW que deve ser evitada quand... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The steel gases available in companies in the sector because of their main transformation processes are coke oven gas (COG), blast furnace gas (BFG) and steel gas (LDG). These are highly valued for minimizing the need to use natural gas or other fuel source. The thermoelectric power plants are among the main consumers of these fuels and the distribution of steel fuels for them is a problem discussed in the technical literature as a way to minimize the imbalances between generation and consumption. At the same time, it is a way to maximize the energy efficiency of the company and the reliability / availability of its supply to the consumer units without direct burning in the flares. The present research proposal aims to model and propose solutions for the optimization of the distribution of fuel gases in thermoelectric power stations in combined gas / steam cycle considering the impacts that the exchange of fuels operate on the main driver (in this case, the gas turbine) In terms of its response to interchangeability between fuels. The modifications proposed in this work simultaneously optimize the by-product gas distribution in the cogeneration gas system, 56 combinations of fuels were evaluated, which resulted in an ideal power range for the application of the study between 30,000 and 80,000 kW and another between 10,000 and 30,000 kW which should be avoided when the objective is positive net revenue. The case study shows that the proposed model finds the ideal solution in terms of total cost reduction when applying the COG in the NG mixture as well as in the substitution of NG by a mixture of by-products COG and BFG, which resulted in the three best net income results found in this analysis / Mestre

Magíster en Gestión de Operaciones / Ingeniero Civil Matemático / En este trabajo se estudian problemas de programación de tareas en un entorno de máquinas paralelas. A diferencia de la literatura clásica, asumimos que los trabajos pueden ser divididos en distintas partes, cada una de las cuales puede ser procesada en distintas máquinas. Antes de procesar cualquier parte de un trabajo, la máquina debe prepararse y requiere un tiempo de instalación. Primero se estudia el problema de minimizar la suma ponderada de tiempos de completación, para el cual se obtiene una $(2+\varepsilon)$-aproximación cuando los tiempos de instalación son todos iguales. Este resultado corresponde al primer algoritmo de aproximación de factor constante para este problema. Usando técnicas similares se diseña una 2-aproximación para el caso de una ponderación uniforme de los trabajos, que en particular mejora el factor 2.781 obtenido por Schalekamp et al. Finalmente, con un algoritmo de {\it programación en lista}, se obtiene una 4-aproximación para el problema original con tiempos de instalación dependientes del trabajo. Posteriormente se estudia el problema en máquinas no relacionadas, donde los tiempos de proceso e instalación dependen de cada máquina. Los algoritmos diseñados en esta sección están basados en técnicas de redondeo de relajaciones lineales. La primera relajación que se estudia permite diseñar una 3-aproximación para el problema. Al realizar un paso de {\it lift and project} sobre una restricción es posible fortalecer la relajación, lo que permite diseñar una $(1+\phi)$-aproximación, donde $\phi=\frac{\sqrt{5}+1}{2}$. Respecto a la inaproximabilidad del problema se demuestra una cota inferior igual a $\frac{e}{e-1}$ basada en un resultado de Feige para {\it Max-$k$-Cover}. Usando la relajación lineal fuerte se muestra una 2-aproximación para la versión del problema en que cada trabajo posee un conjunto restringido de máquinas en las que puede ser procesado, teniendo igual tiempo de instalación y procesamiento en todas ellas. Finalmente, se estudia relajaciones basadas en {\it configuraciones} sobre trabajos, es decir, las variables corresponden a vectores que representan la asignación de un trabajo a máquinas en una cierta programación. El programa lineal de configuraciones de trabajos posee una cantidad infinita de variables, sin embargo, se demuestra que es posible restringirse a una cantidad finita de ellas y que además es posible aproximar este programa lineal en tiempo polinomial a un factor de $1+\varepsilon$. Determinar el gap de integralidad de esta relajación queda como una pregunta abierta.

Magíster en Gestión de Operaciones / En este trabajo se desarrolla una metodología basada en un modelo de programación lineal entera mixta para la el diseño de cuadrantes, en el contexto del Plan Cuadrante de Seguridad Preventiva (PCSP) de Carabineros de Chile. El modelo presentado en este trabajo es una extensión del modelo de P-medianas con restricciones de equidad en la demanda por recursos policiales entre cada uno de los cuadrantes. Este último modelo arroja formas que no son del todo deseable, incluso creando cuadrantes inconexos. Por eso en este trabajo se incorpora una penalización en el tamaño de la frontera de cada distrito. Por otra parte, Carabineros de Chile se enfrenta a una demanda de recursos policiales cuya unidad de medición es denominada Unidad de Vigilancia Equivalente (U.V.E.). Esta demanda está dividida en dos componentes: una de reacción que es fija para cada subsector geográfico; y otra de prevención que depende del máximo de tres factores (nivel de delito, población, kilómetros viales). La primera componente de la demanda es sometida a restricciones de equidad, y la segunda al depender de la forma en que se divide la comuna, es penalizada en la función objetivo. El modelo propuesto que resuelve el diseño óptimo de cuadrantes resulta ser difícil de resolver para instancias superiores a los 100 bloques. Por este motivo se desarrollan varias reglas para disminuir el tamaño del problema para finalmente utilizar una heurística tipo Localización-Asignación, en la cual se divide el problema original en dos problemas, uno en el cual se determina el centro geométrico de los cuadrantes y otro en el que se le asignan a cada centro los bloques. Esta heurística fue implementada de dos maneras. En una se resolvía el problema de asignación a óptimalidad, y en la otra se resolvía la relajación lineal y se utiliza alguna regla de aproximación sacrificando algunas veces factibilidad. Estos métodos fueron aplicados a la comuna de Ñuñoa cuya instancia sobrepasa los 400 bloques. Los resultados de la heurística fueron satisfactorios, encontrando muchas soluciones factibles y de mejor calidad que las que pueden ser obtenidas a través de los métodos de optimización implementados en CPLEX. El desarrollo de esta metodología permite encontrar muchas soluciones factibles con garantías de equidad, lo cual es bueno para tener los tomadores de decisiones, que pueden a posteriori tener otras consideraciones en el diseño de cuadrantes.

Magíster en Gestión de Operaciones / Ingeniera Civil Industrial / En el mundo actual la mayoría de los problemas logísticos son dinámicos; sin embargo, la investigación desarrollada hasta hoy se concentra principalmente en enfoques basados en adaptaciones de algoritmos estáticos. El vertiginoso avance de la tecnología ha incrementado significativamente las posibilidades de diseñar modelos de ruteo dinámico, lo que debe ser explotado para mejorar la eficiencia en problemas reales. En esta tesis se aborda el problema que enfrenta el Servicio Técnico de Xerox en Santiago, el cual es una aplicación real del Problema Dinámico de Ruteo de Vehículos con Ventanas de Tiempo. El objetivo es atender a los clientes con el menor retraso posible dentro de los límites factibles, minimizando a la vez los costos de trasporte. La complejidad de este problema radica principalmente en su naturaleza dinámica, ya que la información de las llamadas se conoce una vez que son recibidas durante el día, por lo que las rutas diseñadas deben ser modificadas para incorporar la nueva información cuando entran al sistema nuevos clientes. Para resolver este problema se desarrolló un algoritmo que utiliza la información histórica de las llamadas para definir Idle Points o puntos de espera, a los cuales acuden los vehículos desocupados para anticipar la demanda futura y minimizar los tiempos de respuesta. Además, se considera un sistema de puntuación según la intensidad de la demanda con el cual se premia la cobertura de las zonas con mayor intensidad de demanda y un esquema de Generación Dinámica de Columnas, en el se utilizan las rutas generadas anteriormente para diseñar nuevas columnas cada vez que surge una nueva solicitud de un cliente. El modelo fue implementado computacionalmente en C++ utilizando Ilog Cplex como motor de optimización, con el fin de realizar simulaciones con datos disponibles de la operación real y evaluar su desempeño en comparación a una versión dinámica de un algoritmo Greedy. Respecto a este benchmark se obtienen mejoras de 26% en los costos totales evaluando instancias que corresponden a 120 días de operación real de todos los meses del año. Además, se compara el modelo con dos versiones simplificadas para medir el impacto de incluir la información histórica y el covering en el modelamiento. Se observa que ambas componentes del modelo permiten disminuir los tiempos de espera de los clientes. Finalmente se comparan los resultados obtenidos con la operación manual de Xerox, obteniendo mejoras significativas en el nivel de servicio y una reducción de un 23% en el tamaño de flota requerido para la atención. Se concluye que el enfoque propuesto se adapta de manera satisfactoria a problemas dinámicos cuya prioridad es el nivel de servicio ofrecido a los clientes.

Magíster en Gestión de Operaciones. Ingeniero Civil Industrial / El desarrollo de nuevas tecnologías en los últimos años, ha permitido reducir de manera significativa los costos de los sistemas GPS y de envío de información; a la vez han existido mejoras en el rendimiento de los algoritmos de optimización y un aumento de la capacidad computacional. Estos tres factores han impulsado la investigación de problemas dinámicos, en los que una parte de la información se va revelando ha medida que transcurre el tiempo, y en particular en problemas complejos como el ruteo de vehículos. En esta tesis se diseñó, implementó y evaluó una solución para el Problema de Ruteo de Vehículos Dinámico con Ventas de Tiempo, la que está basada en el método de descomposición de generación de columnas, que emplea un algoritmo de programación dinámica adaptado especialmente para el subproblema enfrentado. El modelo ocupado en esta tesis está basado en el presentado por Weintraub et al. [1999],que considera en su función objetivo métricas tanto de calidad de servicio como costos operacionales, además una componente de cobertura, la que busca mantener una distribución espacial de los técnicos que permita una reacción temprana a la llegada de los nuevos clientes. Se incluyen también puntos de espera para los vehículos ociosos, al igual que en Briceño [2014], en zonas donde la aparición de nuevos clientes es más probable. Para evaluar la solución, se ocuparon dos casos de estudio que enfrentan problemas dinámicos desarrollados en la ciudad de Santiago. El primero corresponde al servicio técnico de reparaciones de la empresa multinacional Xerox, y el segundo al servicio de emergencias de reparaciones eléctricas de CAM; en ambos casos, el principal objetivo es brindar una alta calidad de servicio, lo que se traduce en bajos tiempos de retraso y espera a sus clientes, que generan en promedio 300 y 200 llamados diarios respectivamente. La implementación de la solución fue realizada en el lenguaje de programación Python ocupando Gurobi como motor de optimización. Cada instancia se compone de una semana real de operación, y fueron generadas a partir de las base de datos históricas de ambos casos. Los resultados muestran que los tiempos de resolución del algoritmo de programación dinámica propuesto, son significativamente menores que los requeridos para resolver el subproblema de generación de columnas directamente como problema de programación entera mixta. Se observa además que el rendimiento de la solución depende fuertemente de la relación entre el número de clientes y vehículos. En el Capítulo 5 de resultados, se analiza en detalle cómo las distintas características de cada instancia, además de las distintas configuraciones de parámetros afectan el rendimiento del algoritmo propuesto.

La mesa de ayuda es un área importante en la resolución de incidentes de tecnologías de información en las empresas, tanto dentro (para la misma empresa y sus empleados) como fuera (para los clientes que la empresa ofrece sus servicios y productos). Sin embargo, la planificación de la resolución de incidentes se hace difícil debido a la imprevisibilidad y espontaneidad de éstos. Dichos incidentes afectan de manera diversa a la continuidad de negocio con consecuencias y tiempo de resolución de diversa magnitud. Asimismo, los técnicos en la mesa de ayuda tienen un tiempo de resolución diverso, con experiencia laboral distinta y son un número finito de personas. Dicho problema se le conoce en problemas de asignación de tareas como “asignación estocástica en línea”. El algoritmo MinIncrease permite la resolución de problemas de asignación estocásticos en línea. Sin embargo, el problema reside en que los técnicos son personas de diversa experiencia que pueden estar divididos en técnicos con mucha o poca experiencia en el ambiente de una mesa de ayuda. No es preciso que al mejor técnico se le asignen incidentes triviales ni que algún técnico no trabaje hasta que aparezca un incidente de su dificultad apropiada. Es por ello que el algoritmo MinIncrease sólo no basta. El siguiente proyecto presenta el diseño de un algoritmo metaheurístico GRASP para la mejoría de un algoritmo MinIncrease. La combinación de estos algoritmos permitirá que los incidentes, a pesar de que su aparición sea imprevista, puedan asignarse a los técnicos de la mesa de ayuda de manera eficiente. / Tesis

Orientador: Edilaine Martins Soler / Coorientadora: Maristela Oliveira dos Santos / Banca: Andrea Gonçalves Vianna / Banca: Marcos Mansano Furlan / Resumo: Os sistemas de abastecimento de água são de fundamental importância pois são responsáveis por levar água de qualidade a população. No Brasil, para as empresas de saneamento, o custo da energia elétrica é cobrado de acordo com a hora do dia, sendo o horário compreendido entre as 18h e as 21h chamado de horário de pico, onde a energia elétrica é mais cara. Grande parte dos gastos com energia elétrica nos sistemas de abastecimento de água são atribuídos as bombas hidráulicas, que, no geral, são acionadas quando os níveis dos tanques chegam ao mínimo, permanecendo ligadas até que se atinjam seus níveis máximos, sem levar em consideração o horário em que esta operação é feita. Diante disto, este trabalho propõe um modelo matemático para a otimização energética mais próximo da realidade dos sistemas de abastecimento de água. Testes numéricos foram realizados através da implementação do modelo no software GAMS e resolvido pelo pacote de otimização CPLEX para diferentes instâncias, afim de validar o modelo proposto e a comprovar à eficiência do planejamento da operação das bombas hidráulicas em relação a operação feita na prática nos sistemas de abastecimento de água. / Abstract: Water supply systems are of fundamental importance once they are responsible for providing quality water to the population. In Brazil, for sanitation companies, the cost of electricity is charged according to the period of the day, with the period between 6 and 9 p.m. known as the peak hours, during which electricity is more expensive. The majority of costs with electricity in the water supply systems are due to the hydraulic pumps, which are, usually, activated when tank levels reach the minimum level and then they remain on until their maximum levels are reached, without taking into account the period during which this operation is performed. With this in mind, this study proposes a mathematical model for the electricity usage optimization closer to the reality in water supply systems. Numerical tests were performed through the implementation of the GAMS software model and solved by the CPLEX optimization package for different instances, in order to validate the proposed model and to prove the efficiency of the planning of the operation of hydraulic pumps about the operation made in practice in water supply systems. / Mestre