Browsing by Author "Verschae, José"

Now showing 1 - 15 of 15
  • Thumbnail Image
    Item
    Análisis de double tree-shortcutting para el problema del vendedor viajero
    (2018) Rogers, Manuel; Verschae, José; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    El problema del vendedor viajero consiste en, dado un grafo completo, encontrar un ciclo de costo mínimo que visite todos los nodos del grafo exactamente una vez. Este problema es difícil de resolver y está presente en múltiples áreas de la optimización, ya sea como el objetivo principal o un sub-problema. Dentro de las áreas más comunes en donde se puede encontrar este problema están la logística de equipos o ruteo de vehículos. La relevancia actual de buscar optimizar rutas y tours en distintos rubros ha impulsado la investigación de este problema, por lo que se han hecho varios análisis desde hace décadas y aún se realizan avances sobre sus diversas variantes. El análisis de los algoritmos de aproximación que forman ciclos Eulerianos para el problema del vendedor viajero se centra en la formación de dicho ciclo y no en la conversión del ciclo Euleriano a un tour utilizando técnicas de shortcutting. En particular, estaba la pregunta abierta para algoritmos de Double Tree Shortcutting en el caso Euclideano de si es posible tener un factor de aproximación menor a 2. En esta tesis cerramos esa pregunta mediante la construcción de una instancia en donde existe un ciclo Hamiltoniano que tiene un peso equivalente al del árbol generador de costo mínimo y no existen reducciones relevantes de costos al convertir el ciclo Euleriano del árbol generador duplicado en uno Hamiltoniano sin importar de qué manera se haga la transformación. Esta instancia particular se contrasta con un escenario esperado de puntos aleatorios, en donde sí se puede reducir el costo del ciclo en un factor constante. Otro resultado de esta tesis es una aproximación a un factor constante de la reducción máxima que se puede hacer con técnicas de shortcutting a un ciclo Euleriano que viene de un árbol generador duplicado. Finalmente, se aborda un caso particular, el cual es cualquier instancia en donde no existan shortcuts que tengan una reducción local de los costos importante. En este caso, se puede concluir que el peso del árbol generador mínimo es cercano al peso del camino más largo de dicho árbol, lo cual implica que el árbol generador duplicado tiene un factor de aproximación menor a 2 sin necesidad de realizar ningún atajo. Esto es un primer avance en caracterizar el factor de aproximación del algoritmo Double Tree Shortcutting y parametrizarlo en función de la estructura de las instancias.
  • No Thumbnail Available
    Item
    Breaking symmetries to rescue sum of squares in the case of makespan scheduling
    (2020) Verdugo, V.; Verschae, José; Wiese, A.
  • Thumbnail Image
    Item
    Complexity, lower bounds, and algorithms for searching infected nodes in uncertain trees
    (2023) Baboun Larach, José; Verschae, José; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Abordamos el desafío de identificar nuevos brotes de COVID-19 a través de la red de aguas residuales de una ciudad. Es posible que tengamos información parcial de la red. En particular, una serie de tuberías no identificables que aparecen en los datos no transportan flujo en la realidad. Resolvemos el problema de encontrar nuevos brotes realizando una secuencia de consultas adaptativas en los nodos de un grafo acíclico dirigido, el cual modela la red. Una consulta determina si el nodo infectado envía agua contaminada a través del nodo consultado, asumiendo que el agua fluye a través de un árbol dirigido desconocido. Nuestro modelo es robusto ante cualquier realización del árbol. Mostramos que el problema es NP-difícil cuando se intenta minimizar el número de consultas en el peor caso. Luego presentamos algunas características de la solución óptima, incluyendo propiedades y cotas inferiores para los escenarios promedio y peor caso. Demostramos que el treewidth del grafo no es una cota inferior de la altura de la estrategia de búsqueda óptima. Para resolver el problema computacionalmente, presentamos tres algoritmos heurísticos. El Algoritmo de Entropía proporciona soluciones efectivas cercanas a la solución óptima para el caso sin incertidumbre. Sin embargo, su tiempo de ejecución puede ser exponencial en el número de diferentes caminos del grafo. El Algoritmo de Separación de Caminos retorna resultados ligeramente peores, pero se puede implementar en tiempo polinomial. Finalmente, conectamos con el marco de Group Testing. Damos un algoritmo óptimo para el caso sin restricciones en el tamaño del conjunto a testear, así como una 5-aproximación para cuando este tamaño está acotado por el número separador del grafo multiplicado por el grado de entrada. Nuestros hallazgos tienen impacto en las áreas de Group Testing, investigación de operaciones, diseño de algoritmos y epidemiología en aguas residuales.
  • Thumbnail Image
    Item
    DUAL TECHNIQUES FOR SCHEDULING ON A MACHINE WITH VARYING SPEED
    (2018) Megow, Nicole; Verschae, José
  • Thumbnail Image
    Item
    Una generalización de las desigualdades de knapsack cover
    (2018) Morales Muñoz, Ignacio; Verschae, José; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    Los problemas de cubrimiento aparecen naturalmente en optimización discreta. En su versión más básica, debemos elegir un conjunto de artículos de costo mínimo que cubra una determinada demanda. Este es el clásico problema de la mochila en su versión de cubrimiento o Minimum Knapsack, que es NP-hard. A diferencia de la versión original, la relajación lineal natural de esta versión tiene un gap de integralidad no acotado. Carret al. (2000) idearon un conjunto de desigualdades, las knapsack-cover inequalities, para fortalecer esta relajación y reducir el gap a 2.En esta tesis, consideramos un contexto natural donde cada elemento se puede tomar de manera fraccionada, pero con costo no lineal, lo que es una generalización del problema anterior. Extendemos las knapsack-cover inequalities para el caso de funciones de costos lineales por partes, mostramos que su relajación y un algoritmo primal-dual mantienen el gap de integralidad en 2. Al aproximar funciones de costos generales no decrecientes y continua por la izquierda por funciones lineales por partes, podemos obtener un algoritmo primal-dual (2+")-aproximado para estas funciones generales. Finalmente, probamos nuestro algoritmo computacionalmente usando datos basados en el problema de generación de energía con demanda simple, donde se tiene una demanda eléctrica y un conjunto de centrales de producción con funciones de costo no lineales y discontinuas. Mostramos que nuestro algoritmo primal-dual alcanza errores promedio por debajo del 4% al compararse con la solución dual obtenida. Además, observamos que disminuye el error al aumentar la demanda. Una pregunta abierta es si nuestras desigualdades se pueden utilizar para problemas más generales, como el Unsplittable Flow-cover Problem on a path con costos no lineales que, en cierto sentido, agrega una dimensión temporal al problema. Esto abriría la posibilidad de considerar problemas de generación de energía dinámicos.
  • Thumbnail Image
    Item
    Identifying outbreaks in sewer networks: An adaptive sampling scheme under network's uncertainty
    (2024) Baboun Larach, José; Beaudry, Isabelle S.; Castro Cepero, Luis Mauricio; Gutiérrez González, Felipe Iván; Jara Vallejos, Alejandro Antonio; Rubio Orellana, Benjamín Eduardo; Verschae, José
    Motivated by the implementation of a SARS-Cov-2 sewer surveillance system in Chile during the COVID-19 pandemic, we propose a set of mathematical and algorithmic tools that aim to identify the location of an outbreak under uncertainty in the network structure. Given an upper bound on the number of samples we can take on any given day, our framework allows us to detect an unknown infected node by adaptively sampling different network nodes on different days. Crucially, despite the uncertainty of the network, the method allows univocal detection of the infected node, albeit at an extra cost in time. This framework relies on a specific and well-chosen strategy that defines new nodes to test sequentially, with a heuristic that balances the granularity of the information obtained from the samples. We extensively tested our model in real and synthetic networks, showing that the uncertainty of the underlying graph only incurs a limited increase in the number of iterations, indicating that the methodology is applicable in practice.
  • Thumbnail Image
    Item
    Primal-Dual algorithms for precedence constrained covering problems
    (2017) Mccormick, S. Thomas; Peis, Britta; Verschae, José; Wierz, Andreas
  • No Thumbnail Available
    Item
    Real-time Avionics Optimization
    (2011) Eisenbrand, Friedrich; Niemeier, Martin; Skutella, Martin; Verschae, José; Wiese, Andreas
    We report on the solution of a difficult optimization problem which arises in avionics industry. When constructing the on-board controlling-network of an airplane, the engineers need to solve a computationally highly complex problem. The goal is to assign periodic tasks to the processors on the plane and define a schedule for each processor. Current state-of-the-art approaches to tackle the problem are by far not powerful enough to solve instances of real-world size. With the help of the powerful algorithm engineering paradigm we analyzed the mathematical properties of the scheduling problem and designed sophisticated software based on the structural insights. We were able to design a model that outperformed current state-of-the-art approaches by several orders of magnitude. In particular, we could solve industrial size real-world instances to optimality. Our methods lead, for the first time, to an industrial strength tool to schedule aircraft sized instances
  • Thumbnail Image
    Item
  • Thumbnail Image
    Item
    Searching for infections: algorithms for multiple sampling on trees and planar graphs
    (2023) Rubio Orellana, Benjamín Eduardo; Verschae, José; Pontificia Universidad Católica de Chile. Escuela de Ingeniería
    En el contexto de la pandemia de COVID-19, la capacidad de detectar y rastrear la propagacion del virus se ha vuelto esencial para implementar políticas preventivas efectivas. Con este fin, la epidemiología basada en aguas residuales ha sido estudiada recientemente en forma de pruebas de PCR en muestras de aguas residuales, produciendo resultados prometedores en el monitoreo del estado y las concentraciones de carga viral dentro de diferentes comunidades. En esta tesis, formulamos el problema de encontrar nuevas fuentes de infeccion como un problema de búsqueda en un grafo dirigido que representa la red de aguas residuales. Comenzamos modelando formalmente el problema de encontrar estrategias óptimas que minimicen el número máximo de pasos necesarios para encontrar la fuente de una infección en el peor de los casos. Suponiendo una estructura de árbol en el grafo, obtenemos un algoritmo de tiempo O(K|V |) para encontrar estrategias óptimas que tomen como máximo K muestras diarias. Además, inspirados en escenarios reales, analizamos el problema de trabajar con una representación incierta de la red y obtenemos cotas superiores e inferiores para el número máximo de pasos necesarios por una estrategia óptima en diferentes clases de grafos en este entorno. Específicamente, logramos demostrar una cota superior de O((! + ) log |V |) para grafos con un ancho de árbol de como máximo ! y un grado de entrada , y una cercana cota inferior de ⌦(p|V |) para grafos planares. Además, presentamos una heurística codiciosa para muestrear en grafos inciertos. Todos los algoritmos fueron probados usando datos reales obtenidos de la red de aguas residuales de San Pedro de la Paz, Chile. Las simulaciones realizadas muestran que utilizando 5 y 10 muestras diarias, el enfoque heurístico necesita como máximo 18 y 10 pasos respectivamente, y en promedio 8.65 y 5.34 pasos. Esto muestra que es teóricamente posible aplicar las estrategias desarrolladas para encontrar fuentes de infección en redes de tamaño real en tiempo razonable, incluso al trabajar con incertidumbre en el sistema.
  • Thumbnail Image
    Item
    Splitting versus setup trade-offs for scheduling to minimize weighted completion time
    (2016) Correa Correa, José Vicente; Verdugo, Víctor; Verschae, José
  • Thumbnail Image
    Item
    Strong LP formulations for scheduling splittable jobs on unrelated machines
    (2015) Correa Correa, José Vicente; Marchetti Spaccamela, Alberto; Matuschke, Jannik; Stougie, Leen; Svensson, Ola; Verdugo, Víctor; Verschae, José
  • Thumbnail Image
    Item
    Symmetry Exploitation for Online Machine Covering with Bounded Migration
    (2020) Gálvez, W.; Soto, J. A.; Verschae, José
  • No Thumbnail Available
    Item
    The Online Set Aggregation Problem
    (2018) Carrasco, Rodrigo A.; Pruhs, Kirk; Stein, Cliff; Verschae, José
  • Thumbnail Image
    Item
    The Power of Recourse for Online MST. and TSP
    (2016) Megow, Nicole; Skutella, Martin; Verschae, José; Wiese, Andreas