Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 6
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)

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

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
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

On the multisource hyperplanes location problem to fitting set of points

  • Blanco, V.
  • Japón, A.
  • Ponce, D.
  • Puerto, J.
In this paper we study the problem of locating a given number of hyperplanes minimizing an objective function of the closest distances from a set of points. We propose a general framework for the problem in which norm-based distances between points and hyperplanes are aggregated by means of ordered median functions. A compact Mixed Integer Linear (or Non Linear) programming formulation is presented for the problem and also an extended set partitioning formulation with a huge number of variables is derived. We develop a column generation procedure embedded within a branch-and-price algorithm for solving the problem by adequately performing its preprocessing, pricing and branching. We also analyze geometrically the optimal solutions of the problem, deriving properties which are exploited to generate initial solutions for the proposed algorithms. Finally, the results of an extensive computational experience are reported. The issue of scalability is also addressed showing theoretical upper bounds on the errors assumed by replacing the original datasets by aggregated versions.