Tesis (Estadística e Investigación Operativa)

URI permanente para esta colecciónhttps://hdl.handle.net/11441/10847

Examinar

Mostrando 1 - 20 de 72

Novel mathematical optimization Models for Group counterfactual Analysis
(2024-09-20) Ramírez Ayerbe, Miren Jasone; Carrizosa Priego, Emilio José; Romero Morales, María Dolores; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
In Explainable Artificial Intelligence, Supervised Classification models are sought to have a good trade-off between prediction accuracy and interpretability. Once the classifier has been trained, it would be convenient to have procedures to identify how records should be changed in their features to be classified in the "good" class, e.g., to be classified as a good payer for a loan or a healthy person for a medical condition. Such modified solutions, the so-called counterfactual explanations, are addressed in this thesis. This dissertation is devoted to extending the study of counterfactual analysis across different dimensions. Specially, we delve into group analysis, where, instead of considering a single instance to whom a single explanation is assigned, we consider a group of instances to be perturbed and calculate a tuple of explanations for all of them. We also take into account complex data and expand the study beyond Supervised Classification. In the Introduction, we introduce the Group Counterfactual Analysis problem, providing a critical discussion on the ingredients defining this problem. In Chapter 2, we present several novel optimization models for Group Counterfactual Analysis, covering all possible allocation rules between counterfactuals and instances. First, a one-for-one allocation model is presented, where different linking constraints are included, such as imposing global sparsity. Second, optimization models for multiple allocation rules, namely, many-for-one, one-for-all, and one-for-many are formulated and illustrated. For the latter one, another sparse version is also studied. We solve the problem of minimizing the number of counterfactual explanations needed to cover a group of instances, imposing a maximum number of features that can be changed for all the instances that are linked to the same counterfactual. A novel column generation framework is introduced to solve this problem. All the models are valid for score-based classifiers, and detailed for linear classifiers and additive tree models. In Chapter 3, we focus on the nature of the data, specifically we develop a novel mathematical optimization model for functional data, when the one-for-one allocation rule is used. The goal is to identify the samples of the dataset from which the counterfactual explanation is made of, as well as how they are combined so that the individual instance and its counterfactual are as close as possible. We develop a model that is flexible enough to: incorporate several distance measures, including the popular Dynamic Time Warping distance; be used for score-based classifiers, specifically detailing it for additive tree models; and achieve two types of sparsity, namely in terms of the number of features perturbed and the number of samples used to create the counterfactual. In Chapter 4 we apply the concept of Counterfactual Analysis beyond classification. Particularly, we extend it to Data Envelopment Analysis (DEA). DEA is used as a benchmarking tool to compare the performance of an entity or firm to that of a group of other firms, and by comparison associate its efficiency. Specifically, to establish the best practice performance and assess how efficiently a firm operates compared to this standard, DEA employs linear or mixed integer programming to model the correlation between various inputs and outputs of the firm. We define DEA counterfactuals or targets as alternative combinations of inputs and outputs that are close to the original inputs and outputs of the firm and lead to desired improvements in its efficiency. This problem is formulated as a bilevel optimization model, that we transform it to a single level one, by utilizing the optimality conditions of the DEA problem. Finally, conclusions and future work are briefly discussed in Chapter 5.
Conic programming for routing and location problems
(2024-01-19) Valverde Martín, Carlos; Puerto Albandoz, Justo; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Esta tesis doctoral desarrolla nuevos problemas en el campo de los modelos de transporte, con una perspectiva orientada al uso de drones. En este trabajo se definen nuevos modelos de transporte, tomando ciertos elementos de los problemas de localización, los cuales se resuelven con herramientas de la investigación operativa, como la optimización. La tesis se divide en dos partes. La Parte I se compone de cinco capítulos que abordan diferentes aspectos. El Capítulo 1 introduce el marco teórico que permite comprender los problemas que se desarrollan y cuáles son los últimos avances alcanzados en la literatura. En el Capítulo 2 se establecen qué objetivos se persiguen en este trabajo. El Capítulo 3 presenta los resultados obtenidos hasta la fecha. A continuación, en el Capítulo 4, se lleva a cabo una discusión detallada de dichos resultados. Finalmente, en el Capítulo 5 se presentan las conclusiones generales extraídas de la tesis. La Parte II también está compuesta por seis capítulos, del 6 al 11. Cada uno de los capítulos en la Parte II puede ser abordado de manera independiente y representa una contribución original de investigación en sí mismo. En el Capítulo 6, se aborda una extensión del problema del cartero rural que se centra en diseñar rutas que deben visitar diferentes elementos dimensionales en lugar de simplemente aristas. Este problema modela la planificación de rutas para drones u otros vehículos, donde es necesario visitar múltiples ubicaciones geográficas para entregar bienes o servicios, y luego pasar directamente a la siguiente ubicación utilizando desplazamientos en línea recta. En este capítulo, se presentan dos familias de formulaciones de programación matemática. La primera familia se basa en un modelo por etapas y captura diversas características con aplicaciones prácticas, pero tiene la desventaja de utilizar índices de tres variables. La segunda familia de formulaciones prescinde de estas etapas y utiliza propiedades de conectividad para garantizar la correcta definición de las rutas. Estas formulaciones se comparan utilizando instancias con diferentes formas, como conjuntos representables con conos de segundo orden (SOC), entornos poliédricos y poligonales. Los resultados computacionales presentados en este trabajo demuestran que los modelos son efectivos y que las formulaciones pueden resolver de manera óptima instancias de tamaño mediano, similares a otros problemas combinatorios con entornos que han sido estudiados en la literatura. Para resolver instancias más grandes, también se presenta un algoritmo heurístico que consta de dos fases: agrupación y un metaheurístico de búsqueda local. Este algoritmo ofrece buenos resultados al generar soluciones factibles cercanas al óptimo que, además, puede utilizarse para inicializar los solvers con dichas soluciones. El Capítulo 7 se enfoca en dos problemas distintos de diseño de rutas en el espacio continuo que involucran entornos y barreras: el problema del camino más corto y el problema del viajante de comercio con entornos y barreras. La presencia de estos dos elementos, entornos y barreras, hace que los problemas sean más desafiantes en comparación con sus contrapartes estándar. Al combinar ambos aspectos, surge un nuevo problema que hasta la fecha no ha sido abordado. No obstante, este problema tiene aplicaciones relevantes en actividades de inspección y vigilancia, así como en la industria de reparto, especialmente cuando existe una demanda uniformemente distribuida en ciertas regiones. En el capítulo se presentan formulaciones de programación matemática para ambos problemas, asumiendo barreras lineales y entornos representables con conos de segundo orden. Estos supuestos conducen a formulaciones enteras mixtas con conos de segundo orden , las cuales son sometidas a preprocesamiento y se refuerzan mediante desigualdades válidas. Además, se llevan a cabo experimentos computacionales que demuestran que el método exacto puede resolver instancias con 75 entornos y un rango de 125 a 145 barreras. El Capítulo 8 aborda problemas de localización de instalaciones en un espacio continuo con vecinos y barreras. Específicamente, se analiza el problema de la p-mediana con vecinos y barreras lineales en dos situaciones diferentes. Como primer bloque de construcci ón, se aborda el problema asumiendo que los entornos no son visibles entre sí y, por lo tanto, no existen rutas rectilíneas que unan dos entornos sin cruzar barreras. Bajo esta hipótesis, se obtiene una formulación válida de programación lineal entera mixta. Al eliminar esa hipótesis, se obtiene el problema más general y realista, pero con el inconveniente de ser más desafiante. Adaptando los elementos de la primera formulación, también se desarrolla otra formulación válida de programación bilineal entera mixta. Ambas formulaciones manejan barreras lineales y entornos que son representables con conos de segundo orden, los cuales se preprocesan y fortalecen con desigualdades válidas. Estas formulaciones de programación matemática también son fundamentales para generar un algoritmo matheurístico adaptado que proporciona soluciones de buena calidad para ambos problemas en un tiempo de cómputo corto. El capítulo también detalla una amplia experiencia computacional que demuestra que los enfoques exactos y heurísticos son útiles: el enfoque exacto puede resolver instancias con hasta 50 entornos y diferentes números de barreras en una hora de tiempo de CPU, mientras que el matheurístico siempre devuelve excelentes soluciones factibles en menos de 100 segundos. El Capítulo 9 se centra en mejorar la planificación de rutas utilizando drones. Se examina la coordinación entre un nave principal y un dron para encontrar las rutas más eficientes que deben seguir para visitar diferentes objetivos representados como grafos. El objetivo es minimizar la distancia total recorrida por ambos vehículos, al mismo tiempo que se cumplen los requisitos de visitas a los objetivos en términos de porcentajes. Se analizan distintos enfoques según las suposiciones realizadas sobre la ruta de la nave principal: i) la nave se puede mover en un plano continuo (plano euclídeo), ii) en una poligonal, o iii) en un grafo general. En todos los casos, se desarrollan formulaciones exactas mediante modelos de programación cónica entera mixta de segundo orden que se comparan en un conjunto de pruebas para evaluar su rendimiento. La complejidad de estos métodos exactos dificulta la búsqueda de soluciones óptimas en un tiempo de cálculo reducido. Por lo tanto, además de las formulaciones exactas, también presentamos un procedimiento matheurístico que permite obtener soluciones de alta calidad en un tiempo razonable. Los experimentos computacionales demuestran la utilidad de nuestros métodos en diferentes escenarios. En el Capítulo 10 se examina un modelo que combina el movimiento de un dron con cierta autonomía que puede visitar múltiples puntos, junto con un vehículo base que puede moverse libremente en el espacio continuo. Este vehículo desempeña el papel de cargar la batería del dron, mientras que el dron se encarga de visitar diferentes objetivos, representados por puntos o poligonales. En el caso de las poligonales, se establece el requisito de que el dron atraviese una fracción específica de sus longitudes, que representan actividades de vigilancia o inspección. El objetivo principal del problema consiste en minimizar la distancia total ponderada recorrida por ambos vehículos. Para abordar este problema, se desarrolla y mejora una formulación de programación cónica entera mixta de segundo orden, utilizando desigualdades válidas y proporcionando límites adecuados para las M grandes que aparecen en el modelo. Además, se propone una estrategia matemática re- finada que permite obtener soluciones de calidad en un tiempo de cálculo reducido. La calidad de las soluciones generadas por ambos enfoques se compara y analiza exhaustivamente utilizando un conjunto aleatoria de instancias con diferentes números y formas de objetivos, lo que demuestra la utilidad de nuestro enfoque y su aplicabilidad en diversas situaciones. En el Capítulo 11 se analizan los desafíos de optimización asociados a la coordinación de un sistema compuesto por un vehículo principal y una ota de drones. Cada dron es lanzado desde el vehículo principal para llevar a cabo una tarea especí ca. Una vez completada la tarea, los drones regresan al vehículo principal para recargar sus baterías y prepararse para una nueva tarea. Estas tareas implican visitar parcialmente grafos con una longitud determinada, con el propósito de brindar servicios o realizar actividades de vigilancia e inspección. El objetivo principal consiste en minimizar el tiempo total de los desplazamientos realizados por el vehículo principal, al mismo tiempo que se cumplen ciertos requisitos en términos de porcentajes de visitas a los grafos objetivo. Para abordar este problema, se desarrollan formulaciones exactas utilizando programas de conos de segundo orden con variables enteras, los cuales son comparados en un conjunto de pruebas para evaluar su rendimiento. Además, se presenta un algoritmo matheurístico que genera soluciones razonables. Los experimentos computacionales demuestran la utilidad de esta metodología en diversos escenarios.
Enhancing Classification and Regression Tree-Based Models by means of Mathematical Optimization
(2022-12-19) Molero del Río, María Cristina; Blanquero Bravo, Rafael; Carrizosa Priego, Emilio José; Romero Morales, María Dolores; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
This PhD dissertation bridges the disciplines of Operations Research and Machine Learning by developing novel Mathematical Optimization formulations and numerical solution approaches to build classification and regression tree-based models. Contrary to classic classification and regression trees, built in a greedy heuristic manner, formulating the design of the tree model as an optimization problem allows us to easily include, either as hard or soft constraints, desirable global structural properties. In this PhD dissertation, we illustrate this flexibility to model: sparsity, as a proxy for interpretability, by controlling the number of non-zero coefficients, the number of predictor variables and, in the case of functional ones, the proportion of the domain used for prediction; an important social criterion, the fairness of the model, which aims to avoid predictions that discriminate against race, or other sensitive features; and the cost-sensitivity for groups at risk, by ensuring an acceptable accuracy performance for them. Moreover, we provide in a natural way the impact that continuous predictor variables have on each individual prediction, thus enhancing the local explainability of tree models. All the approaches proposed in this thesis are formulated through Continuous Optimization problems that are scalable with respect to the size of the training sample, are studied theoretically, are tested in real data sets and are competitive in terms of prediction accuracy against benchmarks. This, together with the good properties summarized above, is illustrated through the different chapters of this thesis. This PhD dissertation is organized as follows. The state of the art in the field of (optimal) decision trees is fully discussed in Chapter 1, while the next four chapters state our methodology. Chapter 2 introduces in detail the general framework that threads the chapters in this thesis: a randomized tree with oblique cuts. Particularly, we present our proposal to deal with classification problems, which naturally provides probabilistic output on class membership tailored to each individual, in contrast to the most popular existing approaches, where all individuals in the same leaf node are assigned the same probability. Preferences on classification rates in critical classes are successfully handled through cost-sensitive constraints. Chapter 3 extends the methodology for classification in Chapter 2 to additionally handle sparsity. This is modeled by means of regularizations with polyhedral norms added to the objective function. The sparsest tree case is theoretically studied. Our ability to easily trade in some of our classification accuracy for a gain in sparsity is shown. In Chapter 4, the findings obtained in Chapters 2 and 3 are adapted to construct sparse trees for regression. Theoretical properties of the solutions are explored. The scalability of our approach with respect to the size of the training sample, as well as local explanations on the continuous predictor variables, are illustrated. Moreover, we show how this methodology can avoid the discrimination of sensitive groups through fairness constraints. Chapter 5 extends the methodology for regression in Chapter 4 to consider functional predictor variables instead. Simultaneously, the detection of a reduced number of intervals that are critical for prediction is performed. The sparsity in the proportion of the domain of the functional predictor variables to be used is also modeled through a regularization term added to the objective function. The obtained trade off between accuracy and sparsity is illustrated. Finally, Chapter 6 closes the thesis with general conclusions and future lines of research.
New Advances In Data Science Problems Through Hyperplanes Location
(2022-06-02) Japón Sáez, Alberto; Blanco Izquierdo, Víctor; Puerto Albandoz, Justo; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
This thesis dissertation focus on developing new approaches for different Data Science problems from a Location Theory perspective. In particular, we concentrate on locating hyperplanes by means of solving Mixed Integer Linear and Non Linear Problems. Chapter 1 introduces the baseline techniques involved in this work, which encompass Support Vector Machines, Decision Trees and Fitting Hyperplanes Theory. In Chapter 2 we study the problem of locating a set of hyperplanes for multiclass classification problems, extending the binary Support Vector Machines paradigm. We present four Mathematical Programming formulations which allow us to vary the error measures involved in the problems as well as the norms used to measure distances. We report an extensive battery of computational experiment over real and synthetic datasets which reveal the powerfulness of our approach. Moreover, we prove that the kernel trick can be applicable in our method. Chapter 3 also focus on locating a set of hyperplanes, in this case, aiming to minimize an objective function of the closest distances from a set of points. The problem is treated in a general framework in which norm-based distances between points and hyperplanes are aggregated by means of ordered median functions. We present a compact formulation and also a set partitioning one. A column generation procedure is developed in order to solve the set partitioning problem. We report the results of an extensive computational experience, as well as theoretical results over the scalability issues and geometrical analysis of the optimal solutions. Chapter 4 addresses the problem of finding a separating hyperplane for binary classification problems in which label noise is considered to occur over the training sample. We derive three methodologies, two of them based on clustering techniques, which incorporate the ability of relabeling observations, i.e., treating them as if they belong to their contrary class, during the training process. We report computational experiments that show how our methodologies obtain higher accuracies when training samples contain label noise. Chapters 5 and 6 consider the problem of locating a set of hyperplanes, following the Support Vector Machines classification principles, in the context of Classification Trees. The methodologies developed in both chapters inherit properties from Chapter 4, which play an important role in the problems formulations. On the one hand, Chapter 5 focuses on binary classification problems where label noise can occur in training samples. On the other hand, Chapter 6 focus on solving the multiclass classification problem. Both chapters present the results of our computational experiments which show how the methodologies derived outperform other Classification Trees methodologies. Finally, Chapter 7 presents the conclusions of this thesis.
Computational Methods for the Analysis of Complex Data
(2021-07-07) Sillero Denamiel, María Remedios; Blanquero Bravo, Rafael; Carrizosa Priego, Emilio José; Ramírez Cobo, Josefa; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
This PhD dissertation bridges the disciplines of Operations Research and Statistics to develop novel computational methods for the extraction of knowledge from complex data. In this research, complex data stands for datasets with many instances and/or variables, with different types of variables, with dependence structures among the variables, collected from different sources (heterogeneous), possibly with non-identical population class sizes, with different misclassification costs, or characterized by extreme instances (heavy-tailed data), among others. Recently, the complexity of the raw data in addition to new requests posed by practitioners (interpretable models, cost-sensitive models or models which are efficient in terms of running times) entail a challenge from a scientific perspective. The main contributions of this PhD dissertation are encompassed in three different research frameworks: Regression, Classification and Bayesian inference. Concerning the first, we consider linear regression models, where a continuous outcome variable is to be predicted by a set of features. On the one hand, seeking for interpretable solutions in heterogeneous datasets, we propose a novel version of the Lasso in which the performance of the method on groups of interest is controlled. On the other hand, we use mathematical optimization tools to propose a sparse linear regression model (that is, a model whose solution only depends on a subset of predictors) specifically designed for datasets with categorical and hierarchical features. Regarding the task of Classification, in this PhD dissertation we have explored in depth the Naïve Bayes classifier. This method has been adapted to obtain a sparse solution and also, it has been modified to deal with cost-sensitive datasets. For both problems, novel strategies for reducing high running times are presented. Finally, the last contribution of this dissertation concerns Bayesian inference methods. In particular, in the setting of heavy-tailed data, we consider a semi-parametric Bayesian approach to estimate the Elliptical distribution. The structure of this dissertation is as follows. Chapter 1 contains the theoretical background needed to develop the following chapters. In particular, two main research areas are reviewed: sparse and cost-sensitive statistical learning and Bayesian Statistics. Chapter 2 proposes a Lasso-based method in which quadratic performance constraints to bound the prediction errors in the individuals of interest are added to Lasso-based objective functions. This constrained sparse regression model is defined by a nonlinear optimization problem. Specifically, it has a direct application in heterogeneous samples where data are collected from distinct sources, as it is standard in many biomedical contexts. Chapter 3 studies linear regression models built on categorical predictor variables that have a hierarchical structure. The model is flexible in the sense that the user decides the level of detail in the information used to build it, having into account data privacy considerations. To trade off the accuracy of the linear regression model and its complexity, a Mixed Integer Convex Quadratic Problem with Linear Constraints is solved. In Chapter 4, a sparse version of the Naïve Bayes classifier, which is characterized by the following three properties, is proposed. On the one hand, the selection of the subset of variables is done in terms of the correlation structure of the predictor variables. On the other hand, such selection can be based on different performance measures. Additionally, performance constraints on groups of higher interest can be included. This smart search integrates the flexibility in terms of performance for classification, yielding competitive running times. The approach introduced in Chapter 2 is also explored in Chapter 5 for improving the performance of the Naïve Bayes classifier in the classes of most interest to the user. Unlike the traditional version of the classifier, which is a two-step classifier (estimation first and classification next), the novel approach integrates both stages. The method is formulated via an optimization problem where the likelihood function is maximized with constraints on the classification rates for the groups of interest. When dealing with datasets of especial characteristics (for example, heavy tails in contexts as Economics and Finance), Bayesian statistical techniques have shown their potential in the literature. In Chapter 6, Elliptical distributions, which are generalizations of the multivariate normal distribution to both longer tails and elliptical contours, are examined, and Bayesian methods to perform semi-parametric inference for them are used. Finally, Chapter 7 closes the thesis with general conclusions and future lines of research.
New models and methods for classification and feature selection. a mathematical optimization perspective
(2021-07-27) Benítez Peña, Sandra; Blanquero Bravo, Rafael; Carrizosa Priego, Emilio José; Ramírez Cobo, Josefa; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
The objective of this PhD dissertation is the development of new models for Supervised Classification and Benchmarking, making use of Mathematical Optimization and Statistical tools. Particularly, we address the fusion of instruments from both disciplines, with the aim of extracting knowledge from data. In such a way, we obtain innovative methodologies that overcome to those existing ones, bridging theoretical Mathematics with real-life problems. The developed works along this thesis have focused on two fundamental methodologies in Data Science: support vector machines (SVM) and Benchmarking. Regarding the first one, the SVM classifier is based on the search for the separating hyperplane of maximum margin and it is written as a quadratic convex problem. In the Benchmarking context, the goal is to calculate the different efficiencies through a non-parametric deterministic approach. In this thesis we will focus on Data Envelopment Analysis (DEA), which consists on a Linear Programming formulation. This dissertation is structured as follows. In Chapter 1 we briefly present the different challenges this thesis faces on, as well as their state-of-the-art. In the same vein, the different formulations used as base models are exposed, together with the notation used along the chapters in this thesis. In Chapter 2, we tackle the problem of the construction of a version of the SVM that considers misclassification errors. To do this, we incorporate new performance constraints in the SVM formulation, imposing upper bounds on the misclassification errors. The resulting formulation is a quadratic convex problem with linear constraints. Chapter 3 continues with the SVM as the basis, and sets out the problem of providing not only a hard-labeling for each of the individuals belonging to the dataset, but a class probability estimation. Furthermore, confidence intervals for both the score values and the posterior class probabilities will be provided. In addition, as in the previous chapter, we will carry the obtained results to the field in which misclassified errors are considered. With such a purpose, we have to solve either a quadratic convex problem or a quadratic convex problem with linear constraints and integer variables, and always taking advantage of the parameter tuning of the SVM, that is usually wasted. Based on the results in Chapter 2, in Chapter 4 we handle the problem of feature selection, taking again into account the misclassification errors. In order to build this technique, the feature selection is embedded in the classifier model. Such a process is divided in two different steps. In the first step, feature selection is performed while at the same time data is separated via an hyperplane or linear classifier, considering the performance constraints. In the second step, we build the maximum margin classifier (SVM) using the selected features from the first step, and again taking into account the same performance constraints. In Chapter 5, we move to the problem of Benchmarking, where the practices of different entities are compared through the products or services they provide. This is done with the aim of make some changes or improvements in each of them. Concretely, in this chapter we propose a Mixed Integer Linear Programming formulation based in Data Envelopment Analysis (DEA), with the aim of perform feature selection, improving the interpretability and comprehension of the obtained model and efficiencies. Finally, in Chapter 6 we collect the conclusions of this thesis as well as future lines of research.
Mixed Integer Nonlinear Optimization. Applications to Competitive Location and Supervised Classification
(2015-02-25) Nogales Gómez, Amaya; Blanquero Bravo, Rafael; Carrizosa Priego, Emilio José; Romero Morales, María Dolores; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
This PhD dissertation focuses on the study of Mixed Integer Nonlinear Programming (MINLP) problems [34] for two important and current applications: competitive location on networks [59, 64] and Support Vector Machines (SVM) [56, 152, 153]. Location problems on a network in a competitive environment were first introduced in [82]. They have been deeply studied in operations research and applied in problems such as market area analysis [122], demand estimation [123], or location of retail centres [78]. The SVM has proved to be one of the state-of-the-art methods for Supervised Classification [2, 6, 85, 160]. Successful applications of the SVM are found, for instance, in health care [22, 46, 81], fraud detection [43], credit scoring [113] and cancellations forecasting [138]. In its general form, an MINLP problem can be represented as: min f(x1, x2) s.t. gi(x1, x2) ≤ 0 ∀i = 1, . . . , I x1 ∈ Z n1 x2 ∈ R n2 , where n1 is the number of integer variables, n2 is the number of continuous variables, I is the number of constraints and f, gi are arbitrary functions such that f, gi : Z n1 ×R n2 → R. The general class of MINLP problems is composed by particular cases such as Mixed Integer Linear Programming (MILP) problems, when f, gi ∀i = 1, . . . , I are linear functions, Mixed Integer Quadratic Programming (MIQP) problems, when f is quadratic or Quadratically Constrained Quadratic Programming (QCQP) problems, when f, gi are quadratic functions. There are two main lines of research to solve this kind of problems: to develop packages for general MINLP problems [32, 55] or to exploit the specific structure of the problem. In this PhD dissertation we focus on the latter. Concerning the first application, we study the problem of locating one or several facilities on a competitive environment in order to maximize the market share. We study the single and p-facility Huff location model on a network and the single Huff origin-destination trip model [95]. Both models are formulated as MINLP problems and solved by a specialized branch and bound, where bounding rules are designed using DC (difference of convex) and Interval Analysis tools. In relation to the second application, we present three different SVM-type classifiers, focused either on robustness or interpretability. In order to build the classifier, different approaches are proposed based on the solution of MINLP problems, or particular cases of it such as MILP, MIQP or QCQP problems, and globally optimized using a commercial branch and bound solver [55, 100, 101].
Integración Montecarlo en la determinación de orbitales atómicos y moleculares
(1995-10-03) Rodríguez Huertas, Rosa; Fernández Núñez, Manuel; Infante Macías, Rafael; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Algunas cuestiones sobre detección y estimación de señales en teoría de la información
(1976-09-23) Parras Guijosa, Luis; Infante Macías, Rafael; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Programación con restricciones aleatorias y algunas aplicaciones económicas
(1979-07-02) Muñoz Vázquez, Agustín; Infante Macías, Rafael; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Optimización de un problema de transporte
(1979-03-26) Gutiérrez Fernández, Miguel; Infante Macías, Rafael; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Procedimientos ortogonales aplicados al Bootstrap
(2004-02-17) Gheziel, Mohamed; López Blázquez, José Fernando; Castaño Martínez, Antonia; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
La memoria se divide en ocho capítulos. En los primeros cuatro se hace una revisión del tema a tratar y se introducen las herramientas que serán utilizadas en los siguientes capítulos tales como desarrollos ortogonales para estimadores y procedimientos bootstrap de estimación. En el capítulo 5 se introducen los estimadores bootstrap ortogonales del sesgo y de la varianza. Estos estimadores se obtienen truncando los desarrollos ortogonales de los estimadores con varianza finita y estimando los coeficientes de Fourier mediante un procedimiento bootstrap combinado con técnicas de regresión múltiple. El resultado fundamental es que estos estimadores poseen un error cuadrático medio inferior al obtenido por el procedimiento clásido de Monte Carlo. En el capítulo 6 se extiende el procedimiento anterior al caso no paramétrico y se presenta además un procedimiento específico para aquellos estimadores cuya versión bootstrap pueda escribirse en términos de los conteos multinomiales que indican el número de veces que cada observación aparece en la muestra bootstrap. En el capítulo 7 se presenta un método basado en métodos de inversión de Fourier para la aproximación de la distribución bootstrap de sumas de variables aleatorias. El último capítulo describe como han sido implementadas en el ordenador las rutinas descritas en los capítulos precedentes así como los códigos fuente en lenguaje MAPLE.
New methods and results in the optimisation of solar power tower plants
(2019-12-03) Ashley, Thomas Ian; Carrizosa Priego, Emilio José; Fernández Cara, Enrique; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Renewable energy technology has seen great advances in recent decades, combined with an ever increasing interest in the literature. Solar Power Tower (SPT) plants are a form of Concentrating Solar Power (CSP) technology which continue to be developed around the world, and are formed of subsystems that are open to optimisation. This thesis is concerned with the development of new methods and results in the optimisation of SPT plants, with particular focus on operational optimi- sation. Chapter 1 provides background information on the energy sector, before describing the design and modelling of an SPT plant. Here, the optical theory behind the transfer of incident radiation in the system is developed and the relevant equations presented. In Chapter 2, the cleaning operations of the heliostat eld are optimised for a xed schedule length using Binary Integer Linear Programming (BILP). Problem dimensionality is addressed by a clustering algorithm, before an ini- tial solution is found for the allocation problem. Finally, a novel local search heuristic is presented that treats the so-called route \attractiveness" through the use of a sequential pair-wise optimisation procedure that minimises a weighted attractiveness measure whilst penalising for overall energy loss. Chapters 3-6 investigate the aiming strategy utilised by the heliostat eld when considering a desired ux distribution pro le and operational constraints. In Chapter 3, a BILP model was developed, where a pre-de ned set of aim- ing points on the receiver surface was chosen. The linear objective function was constrained with linear equalities that related to distribution smoothing (to pro- tect receiver components from abnormal ux loads) via the use of penalisation. Chapter 4 extended this model by instead considering continuous variables with no xed grid of aiming points. This led to an optimisation problem with a non- linear, non-convex objective function, with non-linear constraints. In this case, a gradient ascent algorithm was developed, utilising a non-standard step-size selection technique. Chapter 5 further extended the aiming point optimisation topic to consider the dynamic case. In this sense, the aiming strategy across a period of time could be optimised, taking into account SPT plant technologi- cal limitations. Two algorithms were considered, Penalisation and Augmented Lagrangian, where theoretical properties for optimality and solution existence were presented. Finally Chapter 6 considered the efects of inclement weather on the optimisation model presented in Chapter 3. Stochastic processes were in- vestigated to determine optimal aiming strategies at a xed point in time when weather data could not be known for certain. All research presented in this thesis is illustrated using real-world data for an SPT plant, and conclusions and recommendations for future work are presented.
Contributions to robust and bilevel optimization models for decision-making
(2019-03-15) Leal Palazón, Marina; Conde Sánchez, Eduardo; Puerto Albandoz, Justo; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Los problemas de optimización combinatorios han sido ampliamente estudiados en la literatura especializada desde mediados del siglo pasado. No obstante, en las últimas décadas ha habido un cambio de paradigma en el tratamiento de problemas cada vez más realistas, en los que se incluyen fuentes de aleatoriedad e incertidumbre en los datos, múltiples criterios de optimización y múltiples niveles de decisión. Esta tesis se desarrolla en este contexto. El objetivo principal de la misma es el de construir modelos de optimización que incorporen aspectos inciertos en los parámetros que de nen el problema así como el desarrollo de modelos que incluyan múltiples niveles de decisión. Para dar respuesta a problemas con incertidumbre usaremos los modelos Minmax Regret de Optimización Robusta, mientras que las situaciones con múltiples decisiones secuenciales serán analizadas usando Optimización Binivel. En los Capítulos 2, 3 y 4 se estudian diferentes problemas de decisión bajo incertidumbre a los que se dará una solución robusta que proteja al decisor minimizando el máximo regret en el que puede incurrir. El criterio minmax regret analiza el comportamiento del modelo bajo distintos escenarios posibles, comparando su e ciencia con la e ciencia óptima bajo cada escenario factible. El resultado es una solución con una eviciencia lo más próxima posible a la óptima en el conjunto de las posibles realizaciones de los parámetros desconocidos. En el Capítulo 2 se estudia un problema de diseño de redes en el que los costes, los pares proveedor-cliente y las demandas pueden ser inciertos, y además se utilizan poliedros para modelar la incertidumbre, permitiendo de este modo relaciones de dependencia entre los parámetros. En el Capítulo 3 se proponen, en el contexto de la secuenciación de tareas o la computación grid, versiones del problema del camino más corto y del problema del viajante de comercio en el que el coste de recorrer un arco depende de la posición que este ocupa en el camino, y además algunos de los parámetros que de nen esta función de costes son inciertos. La combinación de la dependencia en los costes y la incertidumbre en los parámetros da lugar a dependencias entre los parámetros desconocidos, que obliga a modelar los posibles escenarios usando conjuntos más generales que los hipercubos, habitualmente utilizados en este contexto. En este capítulo, usaremos poliedros generales para este cometido. Para analizar este primer bloque de aplicaciones, en el Capítulo 4, se analiza un modelo de optimización en el que el conjunto de posibles escenarios puede ser alterado mediante la realización de inversiones en el sistema. En los problemas estudiados en este primer bloque, cada decisión factible es evaluada en base a la reacción más desfavorable que pueda darse en el sistema. En los Capítulos 5 y 6 seguiremos usando esta idea pero ahora se supondrá que esa reacción a la decisión factible inicial está en manos de un adversario o follower. Estos dos capítulos se centran en el estudio de diferentes modelos binivel. La Optimización Binivel aborda problemas en los que existen dos niveles de decisión, con diferentes decisores en cada uno ellos y la decisión se toma de manera jerárquica. En concreto, en el Capítulo 5 se estudian distintos modelos de jación de precios en el contexto de selección de carteras de valores, en los que el intermediario nanciero, que se convierte en decisor, debe jar los costes de invertir en determinados activos y el inversor debe seleccionar su cartera de acuerdo a distintos criterios. Finalmente, en el Capítulo 6 se estudia un problema de localización en el que hay distintos decisores, con intereses contrapuestos, que deben determinar secuencialmente la ubicación de distintas localizaciones. Este modelo de localización binivel se puede aplicar en contextos como la localización de servicios no deseados o peligrosos (plantas de reciclaje, centrales térmicas, etcétera) o en problemas de ataque-defensa. Todos estos modelos se abordan mediante el uso de técnicas de Programación Matemática. De cada uno de ellos se analizan algunas de sus propiedades y se desarrollan formulaciones y algoritmos, que son examinados también desde el punto de vista computacional. Además, se justica la validez de los modelos desde un enfoque de las aplicaciones prácticas. Los modelos presentados en esta tesis comparten la peculiaridad de requerir resolver distintos problemas de optimización encajados.
Mixturas de distribuciones: Modelización de experiencias con asimetría en los datos
(2003-04-24) Atienza Martínez, María Nieves; García de las Heras, Joaquín Antonio; Muñoz Pichardo, Juan Manuel; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Una de las estrategias de la Estadística para describir y explicar una realidad compleja es la representación de la misma mediante modelos probabilísticos. En esta línea se enmarca la presente memoria, teniendo como principal objetivo la modelización de fenómenos aleatorios a través de mixturas finitas de distribuciones. En concreto, aquellas experiencias aleatorias con asimetría en los datos. Inicialmente, esta memoria surge tratando de abordar un problema real al que se tiene que enfrentar la gestión de hospitales y servicios de salud para programar y financiar adecuadamente los mismos. El estudio del tiempo de hospitalización de los pacientes, variable conocida como “estancia hospitalaria”. La estancia hospitalaria es un índice del consumo de recursos ampliamente utilizado en la gestión hospitalaria. En particular, se utiliza en la dirección, planificación y control de calidad del servicio. Usualmente los datos observados de esta variable presentan asimetría positiva, por ello, tradicionalmente se han utilizado modelos Lognormal, Gamma y Weibull. En esta perspectiva, Marazzi y otros, presentan criterios para decidir sobre cual de los tres modelos anteriores representar mejor la variable citada. En esta memoria, se pretende ampliar el estudio a través de un modelo más general basado en mixturas finitas de distribuciones, en particular, de las distribuciones antes citadas. El modelo consiste en una mixtura de tres componentes pertenecientes a cada una de las tres familias. Este modelo de “mixturas mixtas” proporciona una flexibilidad extra necesaria cuando una sola de las familias no conduce a una explicación satisfactoria de la realidad. Conviene resaltar que, además de la gestión hospitalaria, existen otras muchas situaciones reales descritas por variables que se debaten entre la modelización por alguna de las tres distribuciones: lognormal, Gamma o Weibull. Para ilustras esta aplicación, a continuación se recogen algunas de ellas: Microbiología: Estudio de las posibles consecuencias de la preparación de comidas en ciertos patógenos alimenticios. Neurología: Estudio de la actividad de las neuronas. Veterinaria: Estudio de la duración de viremias en ganado vacuno. Mecánica: Estudios de resistencia de materiales. Meteorología: Concentración de vapor de agua en las nubes y en el estudio de pluviometría. Geología: Estudio de los tamaños de las partículas de sedimentos fluviales. Geofísica: Estudio de las frecuencias de terremotos de cierta magnitud. Epidemiología: Estimación del periodo de incubación del SIDA. La memoria se ha estructurado de la siguiente forma: En el primer capítulo se recogen definiciones, propiedades y conceptos necesarios para el desarrollo de la misma. Se presentan las distribuciones objeto de estudio con algunas de sus características. También, se introduce la modelización mediante mixturas de distribuciones. Se revisa el método de estimación de máxima verosimilitud, poniendo de manifiesto sus propiedades y recogiendo condiciones suficientes para que las mismas se verifiquen. Se finaliza este capítulo con el estudio de un procedimiento iterativo, ampliamente utilizado en el área de las mixturas, para el cálculo de los estimadores de máxima verosimilitud de los diferentes parámetros: el algoritmo EM. En el segundo capítulo se estudian condiciones suficientes que permitan comprobar la identificabilidad de experimentos modelizados a través de mixturas finitas de distribuciones. Dado que los resultados existentes sobre identificabilidad de mixturas no son aplicables al modelo bajo estudio en esta memoria, se propone un nuevo resultado que relaja las condiciones de resultados propuestos en la literatura sobre el tema. El capítulo finaliza con la comprobación de la identificabilidad de distintas familias de mixturas, mediante este nuevo resultado. Para comprobar que en el conjunto de mixturas mixtas de las familias Lognormal, Gamma y Weibull, las soluciones de las ecuaciones de verosimilitud cumplen las condiciones de consistencia (recogidas en el Capítulo 1), en el tercer capítulo se proponen algunos resultados que facilitan la verificación de dichas condiciones para las mixturas de uniones de ciertas familias paramétricas de funciones de densidad como son las familias exponenciales y otro tipo de familias más generales que incluyen a las distribuciones Weibull. Por último, el Capítulo 4 aborda el problema de la estimación de máxima verosimilitud de los parámetros del modelo presentado, a través de la aplicación del algoritmo EM. Asimismo, se estudian los elementos necesarios para la aplicación de dicho algoritmo y un método de aceleración del mismo. A continuación, se presenta un conjunto de simulaciones del modelo con el objetivo de ilustrar la validez de las técnicas propuestas en esta memoria. Este capítulo se concluye con la aplicación a conjuntos de datos reales de la variable estancia hospitalaria.
Programación matemática para las máquinas de vector de apoyo: mathematical programming for support vector machines
(2006) Martín Barragán, Belén; Romero Morales, María Dolores; Carrizosa Priego, Emilio José; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
En esta Tesis Doctoral, presentamos algunas propuestas en las que las herramientas de la Programación Matemática se usan para obtener clasificadores que tengan algunas propiedades interesantes. En aplicaciones prácticas, el principal objetivo es obtener c
Algunas aportaciones a los métodos de optimización del análisis clúster mediante la Descomposición en Valores Singulares (D.V.S.)
(1996) González Caballero, Juan Luis; Ramírez Labrador, José; Valderrama Bonnet, Mariano J.; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
En este trabajo se propone un procedimiento de clasificación general que permite obtener grupos naturales en conjuntos donde se sospecha que existen mas de uno. El procedimiento se basa en obtener el modelo q-factorial derivado de la descomposición en va
Localización multicriterio de centros peligrosos
(1992) Saameño Rodríguez, Juan José; Infante Macías, Rafael; Muñoz Pérez, José; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Un problema de localización max-min con restricciones
(1993) Fernández Palacín, Fernando; Muñoz Pérez, José; García Rendón, Antonino; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
En nuestro trabajo, tratamos el problema de localización de un centro peligroso en un polígono convexo, S -aunuqe en la Segunda parte del Capítulo II consideramos un caso en el que sólo exigimos a S que sea múltiplemente conexo- dentro de una región donde
El impacto económico de la innovación en las empresas andaluzas
(2012) Romero García de Paredes, María José; Solís Cabrera, Francisco Manuel; Galán González, José Luis; Pino Mejías, José Luis; Universidad de Sevilla. Departamento de Economía Aplicada I; Universidad de Sevilla. Departamento de Estadística e Investigación Operativa; Universidad de Sevilla. Departamento de Administración de Empresas y Comercialización e Investigación de Mercados (Marketing)
El objeto de este estudio es medir el impacto de la innovación en las empresas andaluzas con el fin de verificar si la innovación genera, o no, ventajas competitivas a las empresas innovadoras.

Examinar

Envíos recientes