Set packing, location and related problems

Resumen

Este trabajo surge del estudio de distintos problemas de optimización combinatoria, que están relacionados de una forma u otra. Se encuentra dividido en dos partes. La primera parte se centra en el estudio de formulaciones de empaquetamiento de conjuntos, las cuales son de vital importancia en la Programación Entera. El empaquetamiento de conjuntos está estrechamente ligado al problema de particionamiento de conjuntos, uno de los ejemplos paradigmáticos en optimización combinatoria. El problema de particionamiento de conjuntos consiste en encontrar una partición de mínimo coste de un conjunto de objetos y de hecho es equivalente al problema de empaquetamiento de conjuntos. Estos sirven de marco común para problemas de optimización como planificación de máquinas, subastas combinatorias y gestión del tráfico en redes. Otros problemas combinatorios relacionados y bien conocidos son el empaquetamiento de nodos, coloreado de grafos y clique máximo. La segunda parte de la tesis se sitúa algo más lejos de la programación entera pura. En ella se estudian distintos problemas de optimización que surgen en una amplia variedad de disciplinas y que guardan relación con los modelos de la primera parte. La primera parte de esta tesis está compuesta de tres capítulos. El primero se centra en aspectos generales del empaquetamiento de conjuntos, mientras que los otros dos estudian instancias particulares de este problema que surgen en el contexto de la Teoría de la Localización. Estos dos últimos capítulos están dedicados a la propuesta y estudio de dos nuevas variantes del problema de localización sin capacidades. Este es un problema conocido de localización que consiste en decidir sobre el número de servicios a instalar y sobre los usuarios asignados a cada uno de estos servicios. En esta primera parte del trabajo, se profundiza en el estudio poliédrico de los modelos, haciendo énfasis en la determinación de desigualdades válidas, facetas y técnicas de levantamiento. El objetivo principal es conseguir mejores formulaciones matemáticas para problemas de empaquetamiento de conjuntos. Otro objetivo es estudiar nuevos problemas de localización que surgen cuando existen restricciones adicionales respecto a la asignación de usuarios a servicios, a saber, usuarios que no pueden compartir un servicio o usuarios que deben ser atendidos por la misma instalación. La metodología común a estos capítulos se completa con la implementación de algoritmos de separación que permitan incorporar las estructuras encontradas en la resolución computacional de los modelos. Tras analizar los resultados obtenidos computacionalmente, se evidencia la mejora producida al introducir las nuevas desigualdades y técnicas de resolución. La segunda parte de la tesis reúne tres problemas que surgen de dominios aparentemente muy distintos, pero que en realidad guardan relación con el empaquetamiento de conjuntos, la localización o ambos. Se trata del haplotipaje de organismos diploides, el etiquetado óptimo de mapas y la detección de grupos de nodos clave en redes sociales. Cada uno se estudia en un capítulo diferente y en todos los casos se proponen formulaciones matemáticas, se estudian posibles estrategias para reforzar las formulaciones y se lleva a cabo la implementación y prueba de los modelos. Para ello, la metodología empleada será la usual en este tipo de enfoques, incluyendo la propuesta de variables de decisión y restricciones que modelen el problema, el desarrollo de desigualdades que ayuden a mejorar la formulación resultante y la posible comparación con otras formulaciones, así como la implementación de técnicas de resolución específicas en algunos casos. Para el primero de estos problemas, el objetivo es mejorar los modelos existentes de programación matemática. La propuesta de nuevas variables de decisión resulta crucial para llegar a un modelo con mejores cotas, el cual resulta ser más eficiente que el ya existente para tres de cuatro conjuntos de prueba. El objetivo central a la hora de abordar el problema del etiquetado de mapas es conseguir elaborar de forma automática mapas menos ambiguos. Para ello, se toma inspiración de los llamados modelos de mediana ordenada en localización. Finalmente, el estudio de los nodos clave de una red se centra en adaptar la medida de centralidad de autovector al problema de relevancia grupal. Como resultado, se obtiene un modelo que no solo obtiene el grupo central óptimo sino también las comunidades alrededor de sus miembros.