Descripción de las charlas.
A Branch-and-price procedure for continuous multifacility location problems
The Ordered Median Problem is a modeling tool, that provides flexible representations of a large variety of problems, which include most of the classical location problems considered in the literature. While most of the attention in Location Theory has been paid to discrete location problems (p-median, p-center, etc.), the mathematical origins of this theory are closer to Continous Location, through the classical Fermat-Torricelli or Weber problems.
In this work, we analyze a very general family of Continuos Location problems, namely multifacility continuous monotone ordered median location problems (COMP, for short), in which a given finite set of demand points is provided and the goal is to find the optimal location of a given number of new facilities such that: (1) each demand point is allocated to a single facility; (2) the measure of the goodness of the solution is an ordered weighted aggregation of the distances of the demand points to their closest facility. We consider a general framework for the problem, in which the ordered median functions are assumed to be defined by means of monotone weights.
We explore a different strategy to solve efficiently the COMP family of problems by means of a set partition formulation and a branch-and-price approach to solve it, which includes design of exact and heuristic resolution procedures of a pricing problem and the determination of an adequate branching rule.
The soft-margin SVM with ordered weighted average
Support vector machines (SVMs) have become one of the most useful mathematical programming approaches for supervised classification. The classical soft-margin SVM model minimizes an objective function given by the inverse of the margin between the supporting hyperplanes and the sum of the deviations of misclassified objects penalized by a parameter.
In this talk, we propose an SVM model where weights are assigned to the sorted values of slack variables associated with the deviations. Thus, we include the ordered weighted average operator in the soft-margin SVM. Unlike other approaches, this is a one-step method where the classical model is adequately modified.
We show that the dual form of the proposed model allows to use a Kernel function in order to construct nonlinear classifiers. Besides, we present some computational results about the predictive performance of the introduced model (also in its Kernel version) in comparison with other SVM models existing in the literature.
Localizando hiperplanos en el bosque
Los árboles de decisión, y los métodos derivados de estos como RF (Random Forests) o XGB (Extreme Gradient Boosting), componen uno de los principales bloques de herramientas utilizadas para abordar problemas de clasificación. La construcción de estos árboles está normalmente asociada a algoritmos heurísticos, rápidos y fáciles de entrenar, que no garantizan la optimalidad de su estructura, posibilitando la pérdida de estructuras globalmente fuertes por la desconsideración de algunos pasos intermedios aparentemente débiles.
En 2018 se publicó un estudio sobre el problema de árboles de clasificación desde el punto de vista de la Programación Matemática, obteniéndose la formulación de un árbol de clasificación óptimo. Motivados por esta formulación, en nuestros trabajos presentamos algunas formulaciones que combinan técnicas de Support Vector Machines con estructuras propias de árboles de decisión para abordar problemas de clasificación binarios, multiclase y con ruido en las etiquetas de los datos.
An efficient way to obtain nano-object segmentations
Electron tomography is a technique for imaging three-dimensional structures of materials at nanometer scale. This technique consists on reconstructing nano-objects thanks to projections provided by a microscope from different tilt angles for the purposes of identifying the elements that constitute the nano-objects under study. This recognition procedure is known as segmentation which consists of classifying the image intensities into different clusters.
The main idea behind this work is to apply the ordered median problem to allocate every intensity to a group of clusters. The image characteristics allow us to develop specific formulations taking advantage of the problem structure for each image. These formulations give good results in terms of segmentation quality and computing time.
Selección de carteras de valores con filtrado de escenarios: Un enfoque de Optimización Combinatoria
Estudios recientes revelan que las matrices de covarianzas calculadas a partir de las series temporales obtenidas del mercado financiero parecen contener una gran cantidad de ruido. Este hecho hace que el modelo clásico de Markowitz para la selección óptima de carteras de valores sea incapaz de evaluar correctamente el rendimiento asociado a dichas carteras. Dado que este modelo es uno de los más usados en la práctica, diferentes métodos de filtrado de ruido han sido propuestos en la literatura para vencer este inconveniente. Entre ellos, los dos más prometedores son los basados en las técnicas de Random Matrix Theory y Power Mapping. Sin embargo, estos métodos parecen no ser del todo adecuados cuando se aplican a datos financieros reales.
En este trabajo proponemos un nuevo método de filtrado de ruido basado en la eliminación de escenarios mediante Optimización Combinatoria. En particular, proponemos un nuevo modelo de Programación Matemática Cuadrática Entera-Mixta y discutimos algunas de sus propiedades. Mediante un estudio computacional con datos financieros reales, las carteras de valores seleccionadas por nuestro modelo son comparadas en términos de rendimiento out-of-sample con las obtenidos por los otros métodos de filtrado alternativos. Nuestro modelo demuestra obtener mejores resultados. Aunque nuestro modelo puede ser resuelto eficientemente con solvers de optimización estándar para datos de tamaño pequeño y medio, el coste computacional aumenta para datos de mayor tamaño. Por este motivo además proponemos un heurístico que ha demostrado ser realmente eficiente y efectivo en la práctica.
Problemas de coordinación de drones con otros vehículos
Esta charla aborda la optimización de problemas de enrutamiento con drones. Analiza la coordinación de una nave nodriza con un dron para obtener rutas óptimas que tienen como objetivo visitar algunos objetos modelados como grafos. El objetivo es minimizar la distancia total ponderada recorrida por ambos vehículos al tiempo que se satisfacen los requisitos en términos de porcentajes de visitas de estos objetos. En el problema tratado aparecen diferentes enfoques dependiendo de la suposición hecha en la ruta seguida por la nave nodriza: i) la nave nodriza puede moverse en un marco continuo (el plano euclidiano), ii) en una cadena poligonal o iii) en un grafo general. En todos los casos, desarrollamos formulaciones exactas que se basan en optimización cónica de segundo orden en enteros mixtos. La alta complejidad de los métodos exactos dificulta la búsqueda de soluciones óptimas en un tiempo de cálculo corto. Por esa razón, además de las formulaciones exactas, también se propone un algoritmo heurístico que permite obtener soluciones de alta calidad en un tiempo razonable.
New models in Continuous Maximal Covering Location Problem
New models in Continuous Maximal Covering Location Problem. Covering problems are one of the most known problem in the Location Science, in particular, the Maximal Covering Location Problem (MCLP, for short). This problem has proven to be a seminal contribution in logistics and network design, both by its technical merit and practical interest. The MCLP has been analyzed within the two main different frameworks in Location Analysis: discrete and continuous. The continuous one is useful when we need to locate the facilities in a more flexible context as for instance, in telecommunication networks. There are different papers and attempts in the literature to formulate severalproblems in a continuous context.
New models are being developed to improve the knowledge in the Continuous Maximal Covering Location Problem and incorporating different elements that allows the problem to be adapted to real-world situations. On the one hand, we will model the requirement of interconnection between the services, that is, the facilities are required to be linked by means of a given graph structure and two facilities are allowed to be linked if a given distance is not exceed. On the other hand, we will also model different versions of continuous ordered median MCLPs. Different approaches are provided for the problems, which are compared in terms of efficiency for solving them.
Mixed integer programming formulations for the upgrading version of the maximal covering location problem
In this presentation, we concentrated our study on the upgrading version of the maximal covering location problem with edge length modifications in networks.
The upgrading maximal covering location problem with edge length modifications aims at locating p facilities to maximize coverage, considering that the length of the edges can be reduced within a budget. Note that the clients are covered if the distance to an open facility is lower than or equal to the coverage radius. Hence, we seek both solutions: the optimal location of p facilities and the optimal reductions.
In this presentation, we propose some mixed-integer formulations of the problem on general graphs. Furthermore, we develop some strategies including valid inequalities and preprocessing for making the formulation solvable in a shorter time. After that, we compare the proposed formulations testing their performance on a set of networks.