Pasar al contenido principal

OPTIMIZATION ON DATA SCIENCE AND NETWORK DESIGN PROBLEMS: LARGE SCALE NETWORK MODELS MEET OPTIMIZATION AND DATA SCIENCE TOOLS

PID2020-114594GB-C21

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2020
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE SEVILLA

Resultados relacionados

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

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación 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
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)

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
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 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
Publicación 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
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
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Allocating the surplus induced by cooperation in distribution chains with multiple suppliers and retailers

  • Guardiola, Luis A.
  • Meca, Ana
  • Puerto, Justo
  • Guardiola, Luis A.|||/items/e3a552b3-d66c-4863-b8c2-28bf05e1078d
The coordination of actions and the allocation of profit in supply chains under decentralized control plays an important role in improving the profits of retailers and suppliers in the supply chain. We focus on supply chains under decentralized control in which noncompeting retailers can order from multiple suppliers to replenish their stocks. The goal of the firms in the chain is to maximize their individual profits. As the outcome under decentralized control is inefficient, coordination of actions between cooperating agents can improve individual profits. Cooperative game theory is used to analyze cooperation between agents. We introduce multi-retailer-supplier games and show that agents can always achieve an optimal profit by cooperating and forming the grand coalition. Moreover, we show that there will always be stable allocations of total profit among the firms which cannot be improved by any coalition. In addition, we propose and characterize a stable allocation of the total surplus induced by cooperation.