Search

Preséntase unha introdución á programación e lineal e dúas ferramentas informáticas gratuítas que permiten a resolución dos problemas de programación lineal. Efectúase unha ilustración das ferramentas por medio de exemplos.

[Abstract]: One of the practical applications of cooperative transferable utility games involves determining the fee structure for users of a given facility, whose construction or maintenance costs need to be recouped. In this context, certain efficiency and equity criteria guide the considered solutions. This paper analyzes how to allocate the fixed costs of a highway among its users through tolls, considering that different classes of vehicles or travelers utilize the service. For this purpose, we make use of generalized highway games with a priori unions that represent distinct user groups, such as frequent travelers or truckers, who, due to enhanced bargaining power, often secure reductions in their fares in real-world scenarios. In particular, the Owen value, the coalitional Tijs value, and a new value termed the Shapley–Tijs value are axiomatically characterized. Additionally, straightforward formulations for calculating these values are provided. Finally, the proposed methodology is applied to actual traffic data from the AP-9 highway in Spain.

This paper presents a new formulation for the routing problem in which the available fleet consists of trucks and trailers divided into compartments. Solving the model for large instances is computationally expensive. Therefore, we introduce and implemented a two-phase heuristic algorithm. In the first phase, an initial solution is generated through a constructive heuristic algorithm based on concepts from the classic Clarke-Wright algorithm. In the second phase, the initial solution is improved by an iterated tabu search metaheuristic. Our algorithm was tested on 21 instances that were converted from the classic truck and trailer routing problem. The results of our computational study prove the effectiveness of our proposal; the algorithm always finds a feasible solution, which in small-sized problems it is proven to be of good quality. In addition, the algorithm outperforms previous approaches for some truck and trailer routing problem instances. Furthermore, an application of the proposed model and heuristic is demonstrated in the field of agricultural logistics by comparing the obtained results.

Based on Holler (1982), Colomer and Martínez (1995), and Armijos-Toro et al. (2021), we propose two power indices to measure the influence of the players in these classes of weighted majority games in partition function form. We compare the new power indices with their original versions on the class of games in characteristic function form. Finally, we use both new power indices and the two power indices for games in partition function form studied in Alonso-Meijide et al. (2017) to study the distribution of power in the National Assembly of Ecuador that emerged after the elections of February 7, 2021.

The identification of the most potentially hazardous agents in a terrorist organisation helps to prevent further attacks by effectively allocating surveillance resources and destabilising the covert network to which they belong. In this paper, several mechanisms for the overall ranking of covert networks members in a general framework are addressed based on their contribution to the overall relative effectiveness in the event of a merger. In addition, the possible organisation of agents outside of each possible merger naturally influences their relative effectiveness score, which motivates the innovative use of games in partition function form and specific ranking indices for individuals. Finally, we apply these methods to analyse the effectiveness of the hijackers of the covert network supporting the 9/11 attacks

Operations Research (OR) is a discipline in which advanced analytical methods are developed and used to solve problems and aid in decision-making. There are a wide variety of fields where OR can be applied, one of which is logistics. Optimizing and scheduling a certain network is a fundamental task, accomplished by proposing models and solving algorithms for each particular situation. Logistic problems are also often treated by the practitioners of OR from a cooperative standpoint, which can be approached through game theory. This thesis addresses several OR and game theoretical problems that have applications in the logistics domain. The performance of the proposed methodologies is analyzed and illustrated with real data applications.

In this paper, we first use the information we have on the patients of an oncology day hospital to distribute the treatment schedules they have in each of the visits to this centre. To do this, we propose a deterministic mathematical programming model in such a way that we minimise the duration of the waiting room stays of the total set of patients and taking into account the restrictions of the circuit. Secondly, we will look for a solution to the same problem under a stochastic approach. This model will explicitly consider the existing uncertainty in terms of the different times involved in the circuit, and this model also allows the reorganisation of the schedules of medical appointments with oncologists. The models are complemented by a tool that solves the problem of assigning nurses to patients. The work is motivated by the particular characteristics of a real hospital and the models are used and compared with data from this case.

Muchas situaciones de conflicto social o económico pueden modelizarse especificando los resultados sobre los que las partes implicadas pueden ponerse de acuerdo, y un resultado especial que resume lo que ocurre en caso de que no se llegue a un acuerdo. Este modelo se denomina juego de negociación, y una aplicación que asigna un resultado a cada juego de negociación se llama solución de negociación. En el enfoque cooperativo de la teoría de juegos, las soluciones de negociación se caracterizan matemáticamente por propiedades deseables, que suelen denominarse axiomas. En el enfoque no cooperativo, las soluciones se derivan como equilibrios de modelos estratégicos que describen un procedimiento de negociación subyacente. En este trabajo se propone un estudio de los modelos cooperativos y axiomáticos de la negociación, comenzando por el documento seminal de Nash, The Bargaining Problem. Se pretende una visión general de algunos de los principales resultados en esta área, así como una introducción a los modelos no cooperativos de negociación, en particular sobre aquellos modelos que conducen a soluciones de negociación que también resultan del enfoque axiomático. El foco principal estará en algunas de las principales axiomatizaciones existentes de soluciones para juegos de negociación, y se incluirá la herramienta necesaria de la teoría de la utilidad, así como alguna aplicación tomada de la vida real., Many situations of social or economic conflict can be modelled by specifying the outcomes on which the parties involved can agree, and a special result that summarizes what happens in the event of a no-deal. This model is called a negotiation game, and an application that assigns a result to each negotiation game is called a negotiation solution. In the cooperative approach of game theory, negotiation solutions are mathematically characterized by desirable properties, which are often referred to as axioms. In the non-cooperative approach, solutions are derived as balances of strategic models that describe an underlying trading procedure. This paper proposes a study of cooperative and axiomatic models of negotiation, starting with Nash’s seminal document, The Bargaining Problem. An overview of some of the main outcomes in this area is intended, as well as an introduction to non cooperative models of negotiation, in particular on those models that lead to negotiation solutions that also result from the axiomatic approach. The main focus will be on some of the main existing axiomatizations of solutions for trading games, and the necessary tool of utility theory will be included, as well as some application taken from real life.

A aprendizaxe profunda é unha disciplina que está en auxe dada a súa adecuación para resolver problemas complexos. Este traballo recolle a historia da aprendizaxe profunda dende os seus inicios, así como os conceptos básicos necesarios para a súa comprensión. Introdúcense as definicións formais dalgunhas funcións de activación, distintos tipos de redes neuronais como as redes recorrentes ou convolucionais e algoritmos e conceptos relativos ao seu adestramento. Finalmente, amósanse algunhas das aplicacións que ten no mundo real., Deep learning is a discipline that is on the rise given its suitability for solving complex problems. This project encompases the history of deep learning from its beginnings, as well as the basic concepts needed for its understanding. It introduces the formal definitions of some activation functions, several types of neural networks such as recurrent or convolutional networks and algorithms and concepts related to their training. Finally, it showcases some of the applications it has on the real world.

Esta tesis tiene como objetivo proponer nuevas representaciones distribucionales y métodos estadísticos en espacios métricos para modelar de forma eficaz los datos procedentes de la monitorización continua de los pacientes durante las actividades propias de su vida diaria. Proponemos nuevas pruebas de hipótesis para datos emparejados, modelos de regresión, algoritmos de cuantificación de la incertidumbre, pruebas de independencia estadística y algoritmos de análisis de conglomerados para las nuevas representaciones distribucionales y otros objetos estadísticos complejos. Los diferentes resultados recogidos a lo largo de la tesis muestran las ventajas en términos de predicción, interpretabilidad y capacidad de modelización de las nuevas propuestas frente a los metodos existentes.

This paper deals with an important subject in classification problems addressed by machine learning techniques: the evaluation of the influence of each of the features on the classification of individuals. Specifically, a measure of that influence is introduced using the Shapley value of cooperative games. In addition, an axiomatic characterisation of the proposed measure is provided based on properties of efficiency and balanced contributions. Furthermore, some experiments have been designed in order to validate the appropriate performance of such measure. Finally, the methodology introduced is applied to a sample of COVID-19 patients to study the influence of certain demographic or risk factors on various events of interest related to the evolution of the disease

The first part of this work reviews several mathematical programming models dedicated to resource allocation and planning problems in the context of extinguishing large forest fires. These problems have been studied as part of the research projects Lumes and Enjambre, which involve both the public and private sectors in Spain. The objective of Lumes and Enjambre is to develop advanced technologies for fighting forest fires. Moreover, the projects address other tasks such as the design of algorithms to prevent aircraft collisions and estimating the perimeters of forest fires using techniques such as estimating sets from thermal images. The second part of this work is focused on the R package and corresponding graphic interface, Wildfire Resources Management (wrm), which are designed to offer a user-friendly model interface in terms of the introduction of the necessary data, resolution, and presentation of the results, according to the needs of the interlocutors in the company dedicated to the extinction of forest fires. The auxiliary package uses various solvers, such as symphony and gurobi. This work presents the various components of wrm (which can be viewed in the GitHub repository), a computational study, and a procedure for its use.

This paper presents a new formulation for the routing problem in which the available fleet consists of trucks and trailers divided into compartments. Solving the model for large instances is computationally expensive. Therefore, we introduce and implemented a two-phase heuristic algorithm. In the first phase, an initial solution is generated through a constructive heuristic algorithm based on concepts from the classic Clarke–Wright algorithm. In the second phase, the initial solution is improved by an iterated tabu search metaheuristic. Our algorithm was tested on 21 instances that were converted from the classic truck and trailer routing problem. The results of our computational study prove the effectiveness of our proposal; the algorithm always finds a feasible solution, which in small-sized problems it is proven to be of good quality. In addition, the algorithm outperforms previous approaches for some truck and trailer routing problem instances. Furthermore, an application of the proposed model and heuristic is demonstrated in the field of agricultural logistics by comparing the obtained results

La presente tesis abarca cuestiones tanto de teoría de juegos como de programación lineal entera mixta, conectadas por un hilo común, la investigación sobre modelado de problemas reales y el cálculo eficiente de soluciones. Primeramente, se presenta el cálculo de dos índices de poder, el índice con configuración y el índice de Banzhaf- Coleman generalizado, para juegos de mayoría ponderada con configuración de coaliciones. El trabajo novedoso consiste en el empleo de las funciones generatrices para la obtención de estos índices demostrando matemáticamente su idoneidad. Además, se realiza una extensión de los algoritmos a la clase más amplia de juegos de mayoría ponderada múltiple. Se presentan ejemplos de la vida real que muestran el alcance del modelo considerado y los algoritmos introducidos. El resto del trabajo se centra en la resolución de algunos problemas surgidos de la colaboración con la empresa Babcock España, líder española en servicios aéreos de emergencia. Los problemas reflejan los requerimientos relativos a la selección y organización óptima de recursos para la contención de incendios forestales. En la tesis se da solución a tres problemas concretos: la Selección y Asignación temporal de Recursos para la Contención de un incendio forestal (SARC), la Asignación de Aeronaves a Rutas de Vuelo (AARV) y la Asignación de Aeronaves a Puntos de Repostaje (AAPR). Además, debido a la complejidad del problema SARC, se realiza un estudio de la aplicabilidad de distintas técnicas de descomposición para mejorar la eficiencia en la resolución del mismo.

[ES] Partiendo de un conjunto de datos que han sido clasificados en dos clases, queremos saber cuáles han sido los factores más importantes para determinar la clase que les ha sido asignada. Para ello se usará una aproximación axiomática con la finalidad de definir una medida de influencia única. Esta medida será una función que, a partir de un conjunto de datos clasificados, devolverá un valor para cada característica correspondiente a la influencia que ha tenido a la hora de determinar la clasificación. Primero se comenzará con una breve introducción a los juegos cooperativos con utilidad transferible, ya que axiomatizar una medida de influencia y una solución de teoría de juegos tienen características comunes, y varios modelos de clasificación. Después de definir la medida de influencia, se muestra que tiene una forma intuitiva cuando el clasificador es lineal. Y por último, aplicamos la medida en un conjunto de datos relacionados con pacientes afectados por el COVID-19 dependiendo de si han tenido algún incidente o no., [EN] Starting from a collection of data that have been classified into two classes, we want to know which factors have been the most important in determining the classification outcome. For this purpose, an axiomatic approach will be used in order to define a unique measure of influence. This measure will be a function that, given a set of classified data, outputs a value for each feature corresponding to its influence in determining the classification outcome. We will first begin with a brief introduction to cooperative games with transferable utility, since axiomatizing an influence measure and a game theory solution have common aspects, and several classification models. After defining the influence measure, we show that it has an intuitive form when the classifier is linear. Finally, we apply the measure on a dataset related to patients affected by COVID-19 depending on whether they have had any incident or not.

[ES] El problema del viajante de comercio y su extensión, el problema de rutas de vehículos, son dos de los problemas de optimización combinatoria de clase NP-duros más estudiados a lo largo del tiempo. Su importancia se debe a que estos problemas cuentan con una gran cantidad de aplicaciones prácticas y el hecho de que sean problemas fáciles de entender pero con una resolución compleja ha motivado su gran investigación. El objetivo de este trabajo es abordar el estudio de ambos problemas. En el primer capítulo se realizará una revisión bibliográfica de conceptos importantes sobre la teoría de grafos. A continuación, en el segundo capítulo se estudia el TSP así como sus múltiples aplicaciones y métodos de resolución, tanto exactos como heurísticos. Por otro lado, en el tercer capítulo se estudia el VRP de manera similar. En el capítulo final, se presenta una aplicación práctica de todo lo expuesto anteriormente. Nos centramos en el estudio de un problema que presenta un centro de día de la ciudad de Lugo y que se puede modelar siguiendo el esquema de una variante del TSP. Para su resolución se hace uso del modelador AMPL y del solucionador Gurobi a través del servidor de optimización NEOS., [EN] The travelling salesman problem (TSP) and its extent, the vehicle routing problem (VRP) are two of the most studied problems in the combinatorial optimization of NP-hard class throughout time. Its importance is due to their wide range of practical applications and the fact that they are easy to understand. However, their complex resolution has motivated research in this field. The aim of this paper is analysing the study of both problems. In the first chapter, important graph theory concepts will be reviewed. In the second chapter, the TSP will be studied alongside with its multiple applications as well as exact and heuristic resolution methods. In the third chapter, the VRP will be studied likewise. In the final chapter, a practical application of the previous will be represented. The focus will be the study of a problem in a day care centre in the city of Lugo. This problem will be solved following a scheme of a TSP variant. For its resolution we use the model AMPL and its solver Gurobi through the NEOS optimization server.

[GL] A priori podemos pensar que o problema dun agricultor que debe decidir as cantidades que vai plantar de certos cultivos e o problema dun coordinador de rutas de transporte dun distribuidor de carburante non teñen nada en común; porén, non é certo. Ademais do obxectivo de optimizar certos beneficios ou custos suxeitos ás diversas restricións sobre as variables de decisión, algúns parámetros (rendementos de cultivos ou demandas de clientes, respectivamente) poden distar de ser deterministas, estar suxeitos a incerteza e requirir un tratamento como variables aleatorias. Ao longo deste traballo empregaranse diversos exemplos ilustrativos co fin de motivar a programación estocástica. Ademais estudaranse diversos elementos teóricos, como a guía para unha correcta modelización, as condicións de optimalidade e os conceptos de valor esperado de información perfecta e valor da solución estocástica. O traballo tamén consta de dous métodos para a resolución de diversos problemas. O primeiro é un modelador, denominado SMPS, que se emprega para resolver problemas lineais e que pode ser empregado no servidor de optimización NEOS. O outro método que se explicará é un algoritmo heurístico deseñado para resolver problemas de rutas de vehículos estocásticos, [EN] A priori we can think that the problem of a farmer who has to decide the quantities to plant of certain crops and the problem of transport route coordination of a fuel distributor have nothing in common; however, it is not true. Besides the objective of optimizing certain benefits or costs subject to several restrictions on decision variables, some parameters (crop yields or customer demands, respectively) may be far from deterministic, be subject to uncertainty and require treatment as random variables. Throughout this project, diverse illustrative examples will be used in order to motivate stochastic programming. Furthermore, various theoretical elements will be studied, such as the guide for a correct modelling, optimal conditions and the concepts of the expected value of perfect information and the value of the stochastic solution. The present work also consists of two methods to solve various problems. The first one is a modeller, called SMPS, which is utilized to solve linear problems and it can be used through the NEOS server of optimization. The other method that will be explained is a heuristic algorithm designed to solve stochastic vehicle routing problems

[ES] El valor de Shapley busca obtener un procedimiento justo para distribuir los beneficios (o costes) generados por un proyecto conjunto. Esta propuesta está basada en las contribuciones marginales de los agentes a dicho proyecto. En el presente trabajo mostramos que el valor de Shapley queda caracterizado de forma única por una serie de propiedades deseables y hallamos su fórmula explícita. Estudiamos algunas formas alternativas de cálculo del valor mediante extensiones multilineales de juegos, ya que su computación directa puede requerir la suma de un número elevado de términos. Estudiamos también otros valores relacionados, como son el índice de poder de Banzhaf-Coleman, el valor de Owen y el valor de Myerson. Finalmente, se muestran algunas aplicaciones del valor a problemas reales como el diseño de tarifas, repartición de ganancias o el pago a acreedores tras una quiebra, [EN] The Shapley value seeks to obtain a fair procedure to distribute the benefits (or costs) generated by a joint project. This proposal is based on the agents' marginal contributions to said project. In this work we show that the Shapley value is uniquely determined by a series of desirable properties and we find its explicit formula. We study some alternative ways of calculating the value using multilinear extensions of games, since computing it directly can require the sum of a very large number of terms. We also study other related values, such as the Banzhaf-Coleman power index, the Owen value and the Myerson value. Finally, we show some applications of the value to real problems such as designing a schedule of fees, sharing produts or paying creditors after a bankruptcy

This study considers the problem of optimizing the routes of vehicles used in an agricultural cooperative that distributes animal feed to its customers. Different peculiarities distinguish our problem from the general Vehicle Routing Problem because there exists a type of time window constraint, truck capacity is limited, trucks are compartmentalized, there are access restrictions for trucks to some farms and our problem has the main objective of maximizing the amount of feed distributed every day and an auxiliary criterion of minimizing the transport costs. We present a mathematical programming formulation of the model that represents the logistics management problem. As solving the exact model is computationally expensive, we opt for a hybrid heuristic approach that first uses an insertion heuristic algorithm to obtain an initial solution and then improvement processes are performed using the so-called simulated annealing metaheuristic. We have built a graphical interface that allows easy use of the system and, in particular, efficient post-optimality analysis. Moreover, this interface can easily interface with other management tools. The utility of our model is shown with real and simulated data sets.

[GL] Nun sistema de passepartout, un grupo de provedores de servizos deciden emitir un passepartout que permite aos seus clientes acceder aos seus servizos durante un período limitado de tempo e a un prezo fixo. O problema do passepartout consiste en como dividir os beneficios comúns obtidos pola venda dos passepartouts. Neste traballo abordamos esta cuestión empregando diferentes ferramentas que nos proporciona a teoría de xogos cooperativos, centrándonos no caso no que o sistema de passepartout está formado exclusivamente por museos., [EN] In a passepartout system, a group of service providers decide to offer a passepartout to their clients which allows them to access to its services for a limited period of time for a fixed price. The passepartout's problem consists in how to divide the common benefits obtained by the passepartouts' sale. In this work we approach this issue employing different tools provided by the cooperative game theory, focusing in the case in which the passepartout system is formed exclusively by museums.

[GL] Os Problemas de Rutas de Vehículos (VRP) son un exemplo de problemas para os que moitas veces non é posible aplicar algoritmos que os resolvan en tempo polinomial, principalmente debido ao seu tamaño e á súa complexidade. Habitualmente para resolver exemplos deste tipo de problemas usaranse algoritmos heurísticos. Neste traballo presentamos o Problema do Viaxante de Comercio (TSP) para continuar cos Problemas de Rutas de Vehículos. A continuación enunciaremos o algoritmo heurístico proposto por Clarke and Wright para o VRP con restricións de capacidade. Finalmente contaremos cos datos dun problema de rutas da vida real que usaremos para comparar as solucións obtidas usando unha implementación en R do algoritmo de Clarke and Wright coa solución obtida a dito problema mediante a súa modelación con linguaxe AMPL., [EN] The Vehicle Routing Problems (VRP) are an example of problems where it can not be possible to apply an exact method to solve them in a polynomial time in many times due to their complexity or size. Frequently to solve examples of this kind of problems heuristic algorithms will be used. In this project we will first present the Travelling Salesman Problem (TSP) to continue with the Vehicle Routing Problems. Next, we will show the heuristic algorithm proposed by Clarke and Wright for Capacited VRP. Finally, based on a realworld problem, we will compare the solutions obtained by an R implementation of Clarke and Wright algorithm versus the results returned by an AMPL model used together with an exact optimization method.

Recently, physicians in an area of northwestern Spain became concerned about the large number of patients whose serum potassium concentrations were above the normal range, as well as differences in the values recorded from one area to another. With the aim of identifying geographical differences in both mean and variability of potassium levels, analyses were performed using modern flexible regression techniques based on a structured additive distributional regression model. In this type of model, every parameter of a response distribution – rather than just the mean – is related to a structured additive predictor. After adjusting for variables such as age, sex, clot-contact time and spatial effects, differences in potassium concentrations were confirmed. The type of distributional regression model used permitted the mean and variance of the potassium concentrations to be modelled using additive predictors that allow for different types of covariate effects. A variety of complex distributions were contemplated.

Optimal planning of the amount and type of resources needed for extinguishing a forest fire is a task that has been addressed in the literature, using models obtained from operational research. In this study, a general integer linear programming model is proposed, which addresses the allocation of resources in different time periods during the planning period for extinguishing a fire, and with the goal of meeting Spanish regulations for the non-negligence of fronts and periods of rest for pilots and brigades. A computer program and interface were developed using the R language. By means of an example using historical data, we illustrate the model at work and its exact resolution. Then, we carry out a simulation study to analyze the obtained objective functions and resolution times. Our simulation study shows that an exact solution can be obtained very quickly without requiring heuristic algorithms, provided that the planning period does not exceed five hours