Resumen de Conexiones y aplicaciones de la programación semi-definida: El problema de los momentos y la teoría de localización
Location theory is one of the most important fields of logistics that has grown from early foundations to maturity and advanced in several ways. It is a really interdisciplinary fieeld rooted in mathematics, computer science, operation research, economics, geography, and other areas. It is the diverse nature of the subject base of location analysis that has brought about the diversity of theoretical research and applications that have been developed.
Location theory answers to the question on how to situate one or several new facilities with respect to a set of existing facilities in order to minimize the sum of transportation costs between new and existing facilities. The transportation costs are usually assumed to be proportional to the distance between facilities and the distance is generally derived from a norm. The increasing need for location models to better fit different real situations, has made it necessary to develop new and exible location models.
To that end, Nickel and Puerto in 2005 introduced a new type of objective function that generalizes the most popular objective functions considered in literature. This objective function, called ordered median function, applies a penalty to the weighted distance from a client to the server, which is dependent on the position of that weighted distance in the vector of all weighted distances from the clients to the server.
From an application point of view there is no limitation for location theory. Many application areas including public facilities, private facilities, military environment, business areas and Health care systems can be seen in the related literature.
As early roots of locational analysis, several works of a geometrical nature have been done to deal with this problem. In this thesis we develop new algebraic approaches for solving three broad families of continuous location problems: continuous single facility ordered median location problems, continuous multifacility ordered median location problems and multiobjective location problems with ordered median objectives. The challenge is to design a common approach to solve all the above mentioned families of location problems, for different -norms and in finite dimensional space. These are essentially the main goals of this thesis. We shall apply a new methodology first proposed by Lasserre in 2001 called the moment-sum-of-squares (moment-SOS) approach. This approach was initially designed for solving polynomial optimization problems by establishing an equivalence between the PO problem and an infinite- dimensional semidefinite programming problem.
The applicability of the moment-SOS approach comes from solving a hierarchy of semidefinite re- laxations of increasing size. It is a powerful methodology when one wants to solve global optimization problems where the objective function is a polynomial and the feasible set is a compact basic semi- algebraic set. However, in view of present status of semidefinite solvers this approach is so far limited to problems of modest size only, unless some symmetries and/or structured sparsity are present in the problem data and they can be exploited.
This thesis consists of five main chapters. The first one will offer a basic theoretical background for the features that will be dealt with in next chapters. The main contributions of this thesis are: Chapter 2. The focus of this chapter is to provide a powerful tool to solve a large class of unconstrained location problems by solving a unique and explicitly given SDP problem. An extensive set of com- putational experiments is provided in order to test the effciency and applicability of our proposed method.
1 Chapter 3. This chapter is devoted to the application of the moment-SOS approach to the minimization of the ordered weighted average function of finitely many rational functions over a compact semi algebraic set. This approach goes beyond a trivial adaptation of any results available for the minimization of rational functions, since ordered weighted averages of rational functions are not, in general, either rational function or the supremum of rational functions so that current results cannot be applied to handle these problems. However, one can transform the problem into a new problem embedded in a higher dimensional space where it admits a suitable representation that can be cast in the minimization of another rational function in a convenient closed semi-algebraic set, that allows to approximate as close as desired the optimal value of the original problem. We prove that the optimal value is obtained exactly by solving few finitely many semidefinite programs of a given hierarchy. We apply this general framework to a broad family of continuous location problems, showing that some difficult problems (convex and non-convex) that up to date could only be solved on the plane and with Euclidean distance can be reasonably solved with different norms in finite dimensional spaces. We illustrate this methodology with some extensive computational results on constrained and unconstrained location problems.
Chapter 4. The main result in this chapter is a non-trivial extension of the approaches developed in the previous chapters to the multifacility case. This problem is of course harder to handle than the single facility one. To deal with this, we proposed a mixed integer nonlinear programming formulation based on a second order cone mixed integer program for the continuous multifacility ordered median location problem with any norm and in any dimension. We also present another formulation based on the theory of moments. However, the size of the SDP-relaxations used in these approaches grow rapidly with the size of the original problem. Then, we apply dimensionality reductions exploiting the sparsity and symmetry of the problems in order to be able to solve larger instances.
Chapter 5. In the process of locating a new facility each demand point wants to have the service as close as possible. Since most location problems are inherently multiobjective in nature, we proceed with multiobjective locations problems. This chapter provides an efficient algorithm to obtain the set of Pareto-optimal extreme points of finite dimension multiobjective ordered median location problems with polyhedral norms using the general theory of moments for polynomial optimization and different tools from real algebraic geometry. This approach allows us to extract the whole set of extreme point efficient solutions of these optimization problems.
2
