Skip to main content

OPTIMIZATION ON DATA SCIENCE AND NETWORK DESIGN PROBLEMS: DATA SCIENCE MEETS OPTIMIZATION AND NETWORK MODELS

PID2020-114594GB-C22

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Call Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Call year 2020
State Plan 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSIDAD DE CADIZ

Resultados relacionados

Resultados totales (Incluyendo duplicados): 16
Encontrada(s) 1 página(s)

RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Overlapping communities detection through weighted graph community games

  • Benati, Stefano
  • Puerto, Justo
  • Rodríguez Chía, Antonio Manuel
  • Temprano, Francisco
We propose a new model to detect the overlapping communities of a network that is based on cooperative games and mathematical programming. More specifically, communities are defined as stable coalitions of a weighted graph community game and they are revealed as the optimal solution of a mixed-integer linear programming problem. Exact optimal solutions are obtained for small and medium sized instances and it is shown that they provide useful information about the network structure, improving on previous contributions. Next, a heuristic algorithm is developed to solve the largest instances and used to compare two variations of the objective function., 35 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Exploring the possibilities of CoSpaces to create Virtual Reality environments for foreign language learning

  • Berns, Anke
  • Valero Franco, Concepción
  • Sánchez-Reyes, Salvador
The recent Covid-19 pandemic has presented teachers with new challenges, high- lighting the need for innovation, renovation, and increased digitisation across all areas of education, including foreign language learning. At the same time, the increasing advances in Extended Reality (XR) together with the availability of authoring tools have created new opportunities to support the teaching/learning process. However, research suggests that many educators are still reluctant to integrate such technologies into their teaching syllabus. In this context and with the idea of encouraging especially language teachers at A1/A2 level to explore the possibilities of creating novel learning environments using technologies such as Virtual Reality (VR), in the current study we will share our experience regarding the use of authoring tools and the design and implementation of a VR language learning app created with CoSpaces. The latter is a freely available authoring tool which allows teachers with no specific programming skills to easily create VR environments in line with their teaching needs. The study consists of two main parts: the first focuses on describing CoSpaces as an authoring tool and our expe- rience as developers of a VR app. The second shows the tool’s functioning and offers those unfamiliar with it a short introduction. It concludes with evaluating the app’s implementation and analysing teachers' and students' feedback., pp. 54-71
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Improved heuristics for solving large-scale Scanning Transmission Electron Microscopy image segmentation using the ordered median problem

  • Muñoz Ocaña, Juan Manuel
  • Puerto, Justo
  • Rodríguez Chía, Antonio Manuel
The discrete ordered median problem can be applied in a wide variety of areas. The application of this problem in electron tomography image segmentation is currently being considered since high-quality images are obtained when this model is applied. However, its application means that a high computing time is required to obtain solutions for large-scale instances. The size of the images is of great importance in electron tomography experiments, since the larger the image size, the higher the quality of the image. With the goal of reducing the computation times, this paper introduces different heuristic procedures to obtain feasible solutions for the ordered median problem that provide high-quality images in low computing times. Moreover, some noticeable improvements for the heuristic techniques are developed, taking advantage of the particular versions of the ordered median function that have been proven to be especially suitable for electron tomography image segmentation.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Segmentation of scanning-transmission electron microscopy images using the ordered median problem

  • Calvino Gámez, José Juan
  • López Haro, Miguel
  • Muñoz Ocaña, Juan Manuel
  • Puerto, Justo
  • Rodríguez Chía, Antonio Manuel
This paper presents new models for segmentation of 2D and 3D Scanning-Transmission Electron Micro- scope images based on the ordered median function. The main advantage of using this function is its good adaptability to the different types of images to be studied due to the wide range of weight vec- tors that can be cast. Classical segmentation models stand out for their ability to provide a segmentation of the original image very quickly and with low computational burden. However, they do not usually achieve high quality segmentations with a small number of clusters in order to classify the different ele- ments which compose the structure represented in the image. The quality of the segmentation provided by our approach is analysed using different choices of the weight vector in some real instances. More- over, improvements are proposed for the formulations to reduce the computational time needed to solve these problems by taking advantage of the weight vector structure, The authors have been partially supported by projects PID2020-114594GB-{C21, C22}, PID2020-1130 06RB-I0 0, PID2019- 110 018GA-I0 0, MAT2017-87579-R funded by MCIN/AEI/ 10.13039/50110 0 011033 and project NetmeetData Fundacion BBVA convocatoria 2019. This work has been co-funded by the 2014–2020 ERDF Operational Programme and by the Depart- ment of Economy, Knowledge, Business and University of the Regional Government of Andalusia; projects FEDER-UCA18-106895, FEDER-UCA18-107139, FEDER-US-1256951 and P18-FR-1422.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

On the complexity of the upgrading version of the maximal covering location problem

  • Baldomero Naranjo, Marta
  • Kalcsics, Jörg
  • Rodríguez Chía, Antonio Manuel
In this article, we study the complexity of the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem is NP-hard on general networks. However, in some particular cases, we prove that this problem is solvable in polynomial time. The cases of star and path networks combined with different assumptions for the model parameters are analysed. In particular, we obtain that the problem on star networks is solvable in (Formula presented.) time for uniform weights and NP-hard for non-uniform weights. On paths, the single facility problem is solvable in (Formula presented.) time, while the (Formula presented.) -facility problem is NP-hard even with uniform costs and upper bounds (maximal upgrading per edge), as well as, integer parameter values. Furthermore, a pseudo-polynomial algorithm is developed for the single facility problem on trees with integer parameters., 15 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

The p-median problem with upgrading of transportation costs and minimum travel time allocation

  • Espejo Miranda, Inmaculada
  • Marín, Alfredo
In this paper, we analyse the upgrading of arcs in the p-median problem on a bi-network. Both travel times and transportation costs are associated with each arc. Our goal consists of simultaneously finding p medians, allocating each node to the median of minimum travel time and distributing a known budget among the arcs of the network to reduce their transportation cost, in order to minimise the total transportation cost of the system. The problem is motivated by the warehouse-to-locker structure of the distribution networks of many ecommerce businesses. We formulate it in two different ways as an integer programming problem, derive some properties of any optimal solution, develop valid inequalities and present computational results., 13 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

The profit-oriented hub line location problem with elastic demand

  • Cobeña, Brenda
  • Contreras, Ivan
  • Martínez Merino, Luisa Isabel
  • Rodríguez Chía, Antonio Manuel
This paper deals with an extension of the hub line location problem considering demand elasticity with respect to travel times. The proposed model aims to capture the impact the hub network topology has on demand. The objective is to maximize the total revenue generated by each unit of demand using the hub line. We propose mixed-integer nonlinear formulations to model this problem. We study some properties of the nonlinear objective function associated with these formulations. Due to the inherent complexity involved in solving these nonlinear formulations with state-of-the-art solvers, we also present alternative mixed-integer linear programming formulations. Computational results compare the proposed formulations and the benefits of the presented model using benchmark instances commonly used in hub location. Moreover, a sensitivity analysis study is carried out with real data from the city of Montreal, Canada, to demonstrate the added value of incorporating demand elasticity when using the proposed model for public transportation planning.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Multi-product maximal covering second-level facility location problem

  • Baldomero Naranjo, Marta
  • Martínez Merino, Luisa Isabel
  • Rodríguez Chía, Antonio Manuel
This paper introduces a new hierarchical facility location model with three levels: first-level facilities which manufacture different products, second-level facilities which act as warehouses and a third-level consisting of the clients who demand the products that have been manufactured in the first level and stored in the second level. In this model, called multi-product maximal covering second-level facility location problem (SL-MCFLP), the aim is to decide the location of the second-level facilities and the products to be stored in each of them maximizing the overall clients’ satisfaction with respect their coverage. To deal with this model, we introduce a Mixed Integer Linear Program (MILP) which is reinforced by some families of valid inequalities. Since some of these families have an exponential number of constraints, separation algorithms are proposed. In addition, three variants of a matheuristic procedure are developed. Computational studies are included, showing the potentials and limits of the formulation and the effectiveness of the heuristic.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Using the ℓ1-norm for Image-based tomographic reconstruction

  • Calvino Gámez, José Juan
  • Fernández Areizaga, Elena
  • López Haro, Miguel
  • Muñoz Ocaña, Juan Manuel
  • Rodríguez Chía, Antonio Manuel
This paper introduces an ℓ1-norm model based on Total Variation Minimization for tomographic reconstruction. The reconstructions produced by the proposed model are more accurate than those obtained with classical reconstruction models based on the ℓ2-norm. This model can be linearized and solved by linear programming techniques. Furthermore, the complementary slackness conditions can be exploited to reduce the dimension of the resulting formulation by removing unnecessary variables and constraints. Since the efficacy of the reduced formulation strongly depends on the quality of the dual-multipliers used when applying the reduction method, Lagrangian relaxation is used to obtain near-optimal multipliers. This allows solving larger instances in an efficient way.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

A new formulation and branch-and-cut method for single-allocation hub location problems

  • Espejo Miranda, Inmaculada
  • Marín, Alfredo
  • Muñoz Ocaña, Juan Manuel
  • Rodríguez Chía, Antonio Manuel
A new compact formulation for uncapacitated single-allocation hub location problems with fewer variables than the previous Integer Linear Programming formulations in the literature is introduced. Our formulation works even with costs not based on distances and not satisfying triangle inequality. Moreover, costs can be given in aggregated or disaggregated way. Different families of valid inequalities that strengthen the formulation are developed and a branch-and-cut algorithm based on a relaxed version of the formulation is designed, whose restrictions are inserted in a cut generation procedure together with two sets of valid inequalities. The performance of the proposed methodology is tested on well-known hub location data sets and compared to the most recent and efficient exact algorithms for single-allocation hub location problems. Extensive computational results prove the efficiency of our methodology, that solves large-scale instances in very competitive times.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

A mathematical programming approach to overlapping community detection

  • Benati, Stefano
  • Puerto, Justo
  • Rodríguez Chía, Antonio Manuel
  • Temprano, Francisco
We propose a new optimization model to detect overlapping communities in networks. The model elaborates suggestions contained in Zhang et al. (2007), in which overlapping communities were identified through the use of a fuzzy membership function, calculated as the outcome of a mathematical programming problem. In our approach, we retain the idea of using both mathematical programming and fuzzy membership to detect overlapping communities, but we replace the fuzzy objective function proposed there with another one, based on the Newman and Girvan's definition of modularity. Next, we formulate a new mixed-integer linear programming model to calculate optimal overlapping communities. After some computational tests, we provide some evidence that our new proposal can fix some biases of the previous model, that is, its tendency of calculating communities composed of almost all nodes. Conversely, our new model can reveal other structural properties, such as nodes or communities acting as bridges between communities. Finally, as mathematical programming can be used only for moderate size networks due to its computation time, we proposed two heuristic algorithms to solve the largest instances, that compare favourably to other methodologies. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Facility location problems on graphs with non-convex neighborhoods

  • Espejo Miranda, Inmaculada
  • Páez Jiménez, Raúl
  • Puerto Albornoz, Justo
  • Rodríguez Chía, Antonio Manuel
In this paper, we deal with some variants of classical facility location problems on graphs in which both the customers and the facilities belong to a non-necessarily convex neighborhood. Therefore, a point in each neighborhood representing the customer/facility has to be determined, and the customers have to be assigned to the facilities depending on a criterion. In particular, the p-median, the p-center, and the p-maximal covering versions of this problem on graphs are analyzed. An important difference with respect to their classical versions is that the lengths of the arcs depend on the location of the points chosen in the neighborhoods. Therefore, the lengths are not part of the input but part of the decision process. Assuming that the neighborhoods are Mixed-Integer Second Order Cone representable, different mixed-integer non-linear programming formulations are proposed for each one of the considered problems. Moreover, solution procedures providing bounds and a preprocessing phase are developed to reduce the number of variables and constraints of the proposed formulations. The results of an extensive computational experience are reported.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

The soft-margin Support Vector Machine with ordered weighted average

  • Marín, Alfredo
  • Martínez Merino, Luisa Isabel
  • Puerto, Justo
  • Rodríguez Chía, Antonio Manuel
This paper deals with a cost sensitive extension of the standard Support Vector Machine (SVM) using an ordered weighted sum of the deviations of misclassified individuals with respect to their corresponding supporting hyperplanes. In contrast with previous heuristic approaches, an exact method that applies the ordered weighted average operator in the classical SVM model is proposed. Specifically, when weights are sorted in non-decreasing order, a quadratic continuous formulation is developed. For general weights, a mixed integer quadratic formulation is proposed. In addition, our results prove that nonlinear kernel functions can be also applied to these new models extending its applicability beyond the linear case. Extensive computational results reported in the paper show that the predictive performance provided by the proposed exact solution approaches are better than the ones provided by the classical models (linear and nonlinear kernel) and similar or better than the previous ones provided by the heuristic solution by Maldonado et al. (2018). © 2021 The Authors, Alfredo Marín has been supported by Spanish Ministry of Science and Innovation under project PID2019-110886RB-I00 . Part of this research was conducted while he was on sabbatical at Universidad de Sevilla, Spain . Luisa I. Martínez-Merino, Antonio M. Rodríguez-Chía and Justo Puerto thank the Agencia Estatal de Investigación (AEI) and the European Regional Development’s funds (ERDF) : project PID2020-114594GB-C21/C22 ; Regional Government of Andalusia : projects FEDER-UCA18-106895 , FEDER-US-1256951 and P18-FR-1422 ; and Fundación BBVA : project NetmeetData (Ayudas Fundación BBVA a equipos de investigación científica 2019). Luisa I. Martínez-Merino has been supported by Subprograma Juan de la Cierva Formación 2019 ( FJC2019-039023-I ) and PAIDI 2020 postdoctoral fellowship financed by European Social Fund and Junta de Andalucía
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Constraint relaxation for the discrete ordered median problem

  • Ponce, Diego
  • Martínez Merino, Luisa Isabel
  • Puerto, Justo
This paper compares different exact approaches to solve the Discrete Ordered Median Problem (DOMP). In recent years, DOMP has been formulated using set packing constraints giving rise to one of its most promising formulations. The use of this family of constraints, known as strong order constraints (SOC), has been validated in the literature by its theoretical properties and because their linear relaxation provides very good lower bounds. Furthermore, embedded in branch-and-cut or branch-price-and-cut procedures as valid inequalities, they allow one to improve computational aspects of solution methods such as CPU time and use of memory. In spite of that, the above mentioned formulations require to include another family of order constraints, e.g., the weak order constraints (WOC), which leads to coefficient matrices with elements other than {0,1}. In this work, we develop a new approach that does not consider extra families of order constraints and furthermore relaxes SOC -in a branch-and-cut procedure that does not start with a complete formulation- to add them iteratively using row generation techniques to certify feasibility and optimality. Exhaustive computational experiments show that it is advisable to use row generation techniques in order to only consider {0,1}-coefficient matrices modeling the DOMP. Moreover, we test how to exploit the problem structure. Implementing an efficient separation of SOC using callbacks improves the solution performance. This allows us to deal with bigger instances than using fixed cuts/constraints pools automatically added by the solver in the branch-and-cut for SOC, concerning both the formulation based on WOC and the row generation procedure., 24 páginas
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Edge downgrades in the maximal covering location problem

  • Baldomero Naranjo, Marta
  • Kalcsics, Jörg
  • Rodríguez Chía, Antonio Manuel
We tackle the downgrading maximal covering location problem within a network. In this problem, two actors with conflicting objectives are involved: (a) The location planner aims to determine the location of facilities to maximize the covered demand while anticipating that an attacker will attempt to reduce coverage by increasing the length of some edges (downgrade); (b) The attacker seeks to maximize the demand initially covered by the facilities but left uncovered after the downgrade. The attacker can increase the length of certain edges within a specified budget. We introduce a mixed-integer linear bilevel program to formulate the problem, followed by a preprocessing phase and a matheuristic algorithm designed to address it. Additionally, computational results are presented to illustrate the potential and limitations of the proposed algorithm.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publication Artículo científico (JournalArticle)

Quantitative Evaluation of Supported Catalysts Key Properties from Electron Tomography Studies: Assessing Accuracy Using Material-Realistic 3D-Models

  • Bouzaine, A.
  • Muñoz Ocaña, Juan Manuel
  • Rodríguez Chía, Antonio Manuel
  • Hungría Hernández, Ana Belén
  • Calvino Gámez, José Juan
  • López Haro, Miguel
Electron Tomography (ET) reconstructions can be analysed, via segmentation techniques, to obtain quantitative, 3D-information about individual nanoparticles in supported catalysts. This includes values of parameters out of reach for any other technique, like their volume and surface, which are required to determine the dispersion of the supported particle system or the specific surface area of the support; two figures that play a major role in the performance of this type of catalysts. However, both the experimental conditions during the acquisition of the tilt series and the limited fidelity of the reconstruction and segmentation algorithms, restrict the quality of the ET results and introduce an undefined amount of error both in the qualitative features of the reconstructions and in all the quantitative parameters measured from them. Here, a method based on the use of well-defined 3D geometrical models (phantoms), with morphological features closely resembling those observed in experimental images of an Au/CeO2 catalyst, has been devised to provide a precise estimation of the accuracy of the reconstructions. Using this approach, the influence of noise and the number of projections on the errors of reconstructions obtained using a Total Variation Minimization in 3D (TVM-3D) algorithm have been determined. Likewise, the benefits of using smart denoising techniques based on Undecimated Wavelet Transforms (UWT) have been also evaluated. The results clearly reveal a large impact of usual noise levels on both the quality of the reconstructions and nanometrological measurement errors. Quantitative clues about the key role of UWT to largely compensate them are also provided., This work has received support from Projects: PID2020-113006-RB-I00, PID2019-110018GA-I00, PID2020-114594GB-C22, funded by MCIN/AEI/https://doi.org/10.13039/501100011033.This work has also been co-financed by Project ref: MAT2017-87579-R and by the 2014 -2020 ERDF Operational Programme and by the Department of Economy, Knowledge, Business and University of the Regional Government of Andalusia, Project references: FEDER-UCA18-107139, FEDERUCA18-106895 and P18-FR-1422. STEM ET experiments were recorded at the DME-UCA Node of the Spanish Singular Infrastructure for Electron Microscopy of Materials (ICTS ELECMI).