Localización con incertidumbre y métodos de clasificación/ location under uncertainty and classification methods

Resumen

This Ph.D. dissertation provides contributions to two scientific domains: Location Theory and Supervised Classification. We study problems in both domains; presenting mathematical programming models and developing efficient solution approaches. Consequently, the thesis is divided into two main parts, each of which is devoted to problems in one of the two mentioned domains. The first part of the thesis is focused on location theory. Specifically, we introduce models that try to extend or to generalize the p-center problem and covering problems. The well known discrete p-center problem is a minimax location problem that aims to locate a certain number of facilities such that the largest allocation distance between a client and a facility is minimized. We consider a stochastic version of the p-center problem, called the probabilistic p-center problem, where each client could require a service following an independent probability distribution. We propose and rigorously compare three exact approaches for this problem as well as a fast-performing heuristic approach. We further consider another extension of the p-center problem where the clients are divided into different strata depending on the type of demand they require. The objective is, thus, to minimize the weighted sum of the largest allocation distance within each stratum. We propose five different formulations for this problem. We strengthen the formulations through valid inequalities and present preprocessing techniques to reduce the number of variables in the solution process. Besides, this second model allows providing an efficient alternative heuristic approach to solve the above mentioned stochastic model. The third type of location model addressed in this dissertation is related to covering problems. In particular, a general model that tries to unify classic discrete covering location problems is introduced. This model includes also two important features that provide a more realistic framework: uncertainty and time-dependency. With this purpose, a Mathematical Programming model and a Lagrangian relaxation based heuristic solution procedure are proposed. To see the potentials and limits of the model, extensive computational experiments are carried out. The second part of the thesis is devoted to supervised classification. In the classification domain, Support Vector Machine (SVM) models are known to be one of the most effective classification models. Classical SVM models determine an optimal hyperplane that separates two classes of a dataset. An important aspect in SVM is the adequate selection of a small number of features to be involved in the classification process. A correct feature selection can yield to a better interpretation of the model among other advantages. We propose an SVM model with feature selection. We present a Mixed Integer Linear Programming (MILP) formulation, that includes feature selection constraints. Besides a MILP formulation, two strategies for improving the performance of the model are developed. Exact and heuristic approaches are also analyzed for this model. To conclude, we present extensive computational experiments reporting the results of well-known datasets in the literature of supervised classification. The objectives of these experiments are to compare this model with other models in the literature and to show the results of the presented heuristic and exact approaches.