Set packing, location and related problems

• Autores: María de Las Mercedes Pelegrín García
• Directores de la Tesis: Alfredo Marín Pérez (dir. tes.)
• Lectura: En la Universidad de Murcia ( España ) en 2019
• Idioma: inglés
• Número de páginas: 171
• Títulos paralelos:
  • Empaquetamiento de conjuntos, localización y problemas relacionados
• Tribunal Calificador de la Tesis: Ángel Corberán Salvador (presid.) , Elena Fernández Aréizaga (secret.) , Francisco Saldanha Da Gama (voc.)
• Enlaces
  • Tesis en acceso abierto en: DIGITUM
• Resumen
  • español

    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.

  • English

    This work emerges from the study of several combinatorial optimization problems, which are related in one way or another. It is divided into two parts. The first part of the thesis is devoted to the study of set packing programs, which are of crucial relevance in Integer Programming. Set packing is a close relative of set partitioning, one of the paradigmatic examples within combinatorial problems. Set partitioning consists of making a minimum cost partition of a set of objects and is in fact equivalent to set packing. They serve as common framework for optimization problems such as scheduling, combinatorial auctions and traffic network congestion. Other related well-known combinatorial problems include node packing, graph coloring and maximum clique. The second part of the thesis is a bit further from pure integer programming, but still close to set packing. We study different combinatorial problems arising in a wide range of disciplines, including Computational Biology, Cartography and Network Analysis, which are somewhat related to those of the previous part.

    The first part of the thesis is made of three chapters. The first of them concerns general aspects of set packing, while the other two study particular instances of this problem arising in the context of Locational Analysis. These two chapters are devoted to proposing and studying two new variants of the uncapacitated plant facility location problem. This is a well-known problem in locational analysis that consists of deciding on a number of services to be installed and on clients allocation to the facilities. This first part of the dissertation focuses on polyhedral study of the models, placing an emphasis on deriving valid inequalities, facets and lifting techniques. The main goal is to obtain better mathematical programming models for set packing problems. Another objective is to study new location problems arising when additional constraints are considered on users allocation. More precisely, two previously overlooked scenarios are introduced, namely when users cannot be served by the same center or when some pairs of users must be assigned to the same facility. The common methodology for these chapters is completed by implementing separation algorithms that allow to incorporate the newly found structures to standard solution techniques. After analysing the results of our computational experience, we conclude that the improvement due to the new inequalities and techniques is significant.

    The second part of the thesis gathers three problems from domains that are apparently very different but in fact related to set packing, facility location or both. These include haplotyping of diploid organisms, optimal map design and identification of key members in social networks. Each of them is studied in a different chapter and, in all the cases, mathematical programming formulations are proposed, possible enhancement are studied and computational tests are conducted. The methodology would be that customary for these kind of approaches, including proposing decision variables and constraints to model the problem, deriving valid inequalities to improve the resulting formulation and possible comparison with other models. Furthermore, specific solving techniques are implemented when needed. For the first of the mentioned problems, the aim is to improve existing mathematical programming models. Proposing new decision variables will be crucial to develop a model featuring better bounds, which will be more efficient than the existing one for three out of four datasets. On the other hand, the main goal when tackling map labeling is the automatic design of less ambiguous maps. The proposed models are inspired by ordered median problems in the context of facility location. Finally, the study of key nodes in a network focuses on adapting eigenvector centrality to the problem of group relevance. As a result, a model that uncovers the group of key nodes together with their communities is proposed.