Skip to main content

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Flowshop with additional resources during setups: Mathematical models and a GRASP algorithm

  • Yepes-Borrero, Juan C.
  • Perea, Federico
  • Villa Juliá, Mª Fulgencia|||0000-0003-0019-8777
  • Vallada Regalado, Eva|||0000-0003-3918-1788
[EN] Machine scheduling problems arise in many production processes, and are something that needs to be consider when optimizing the supply chain. Among them, flowshop scheduling problems happen when a number of jobs have to be sequentially processed by a number of machines. This paper addressees, for the first time, the Permutation Flowshop Scheduling problem with additional Resources during Setups (PFSR-S). In this problem, in addition to the standard permutation flowshop constraints, each machine requires a setup between the processing of two consecutive jobs. A number of additional and scarce resources, e.g. operators, are needed to carry out each setup. Two Mixed Integer Linear Programming formulations and an exact algorithm are proposed to solve the PFSR-S. Due to its complexity, these approaches can only solve instances of small size to optimality. Therefore, a GRASP metaheuristic is also proposed which provides solutions for much larger instances. All the methods designed for the PFSR-S in this paper are computationally tested over a benchmark of instances adapted from the literature. The results obtained show that the GRASP metaheuristic finds good quality solutions in short computational times., Juan C. Yepes-Borrero acknowledges financial support by Colfuturo under program Credito-Beca grant number 201503877 and from ElInstituto Colombiano de Credito Educativo y Estudios Tecnicos en el Exterior - ICETEX under program Pasaporte a la ciencia - Doctor-ado, Foco-reto pais 4.2.3, grant number 3568118. This research hasbeen partially supported by the Agencia Estatal de Investigacion (AEI)and the European Regional Development's fund (ERDF): PID2020-114594GB-C21; Regional Government of Andalusia: projects FEDER-US-1256951, AT 21_00032, and P18-FR-1422; Fundacion BBVA: project Netmeet Data (Ayudas Fundacion BBVA a equipos de investigacioncientifica 2019). The authors are partially supported by Agencia Valenciana de la Innovacion (AVI) under the project ireves (innovacionen vehiculos de emergencia sanitaria): una herramienta inteligente dedecision'' (No. INNACC/2021/26) partially financed with FEDER funds(interested readers can visit http://ireves.upv.es), and by the Spanish Ministry of Science and Innovation under the project OPRES-RealisticOptimization in Problems in Public Health'' (No. PID2021-124975OB-I00), partially financed with FEDER funds. Part of the authors aresupported by the Faculty of Business Administration and Managementat Universitat Politecnica de Valencia
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)

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
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)

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)

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
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)

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).