Pasar al contenido principal

Resultados relacionados

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

RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación 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
Publicación Artículo científico (JournalArticle)

Minmax regret maximal covering location problems with edge demands

  • Baldomero Naranjo, Marta
  • Kalcsics, Jörg
  • Rodríguez Chía, Antonio Manuel
This paper addresses a version of the single-facility Maximal Covering Location Problem on a network where the demand is: (i) distributed along the edges and (ii) uncertain with only a known interval estimation. To deal with this problem, we propose a minmax regret model where the service facility can be located anywhere along the network. This problem is called Minmax Regret Maximal Covering Location Problem with demand distributed along the edges (MMR-EMCLP). Furthermore, we present two polynomial algorithms for finding the location that minimises the maximal regret assuming that the demand realisation is an unknown constant or linear function on each edge. We also include two illustrative examples as well as a computational study for the unknown constant demand case to illustrate the potential and limits of the proposed methodology.
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación 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
Publicación 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
Publicación Artículo científico (JournalArticle)

Upgrading edges in the maximal covering location problem

  • Baldomero Naranjo, Marta
  • Kalcsics, Jörg
  • Marín, Alfredo
  • Rodríguez Chía, Antonio Manuel
We study the upgrading version of the maximal covering location problem with edge length modifications on networks. This problem aims at locating p facilities on the vertices (of the network) so as to maximise coverage, considering that the length of the edges can be reduced at a cost, subject to a given budget. Hence, we have to decide on: the optimal location of p facilities and the optimal edge length reductions. This problem is NP-hard on general graphs. To solve it, we propose three different mixed-integer formulations and a preprocessing phase for fixing variables and removing some of the constraints. Moreover, we strengthen the proposed formulations including valid inequalities. Finally, we compare the three formulations and their corresponding improvements by testing their performance over different datasets. © 2022 The Author(s)
RODIN. Repositorio de Objetos de Docencia e Investigación de la Universidad de Cádiz
Publicación 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
Publicación 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