Set packing, location and related problems

Zusammenfassung

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.