Cargando…

A hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis

Mixed Integer Linear Programs (MILPs) are usually NP-hard mathematical programming problems, which present difficulties to obtain optimal solutions in a reasonable time for large scale models. Nowadays, metaheuristics are one of the potential tools for solving this type of problems in any context. I...

Descripción completa

Detalles Bibliográficos
Autores principales: Gonzalez, Martin, López-Espín, Jose J., Aparicio, Juan, Talbi, El-Ghazali
Formato: Online Artículo Texto
Lenguaje:English
Publicado: PeerJ Inc. 2022
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8802783/
https://www.ncbi.nlm.nih.gov/pubmed/35174264
http://dx.doi.org/10.7717/peerj-cs.828
_version_ 1784642742259810304
author Gonzalez, Martin
López-Espín, Jose J.
Aparicio, Juan
Talbi, El-Ghazali
author_facet Gonzalez, Martin
López-Espín, Jose J.
Aparicio, Juan
Talbi, El-Ghazali
author_sort Gonzalez, Martin
collection PubMed
description Mixed Integer Linear Programs (MILPs) are usually NP-hard mathematical programming problems, which present difficulties to obtain optimal solutions in a reasonable time for large scale models. Nowadays, metaheuristics are one of the potential tools for solving this type of problems in any context. In this paper, we focus our attention on MILPs in the specific framework of Data Envelopment Analysis (DEA), where the determination of a score of technical efficiency of a set of Decision Making Units (DMUs) is one of the main objectives. In particular, we propose a new hyper-matheuristic grounded on a MILP-based decomposition in which the optimization problem is divided into two hierarchical subproblems. The new approach decomposes the model into discrete and continuous variables, treating each subproblem through different optimization methods. In particular, metaheuristics are used for dealing with the discrete variables, whereas exact methods are used for the set of continuous variables. The metaheuristics use an indirect representation that encodes an incomplete solution for the problem, whereas the exact method is applied to decode the solution and generate a complete solution. The experimental results, based on simulated data in the context of Data Envelopment Analysis, show that the solutions obtained through the new approach outperform those found by solving the problem globally using a metaheuristic method. Finally, regarding the new hyper-matheuristic scheme, the best algorithm selection is found for a set of cooperative metaheuristics ans exact optimization algorithms.
format Online
Article
Text
id pubmed-8802783
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher PeerJ Inc.
record_format MEDLINE/PubMed
spelling pubmed-88027832022-02-15 A hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis Gonzalez, Martin López-Espín, Jose J. Aparicio, Juan Talbi, El-Ghazali PeerJ Comput Sci Algorithms and Analysis of Algorithms Mixed Integer Linear Programs (MILPs) are usually NP-hard mathematical programming problems, which present difficulties to obtain optimal solutions in a reasonable time for large scale models. Nowadays, metaheuristics are one of the potential tools for solving this type of problems in any context. In this paper, we focus our attention on MILPs in the specific framework of Data Envelopment Analysis (DEA), where the determination of a score of technical efficiency of a set of Decision Making Units (DMUs) is one of the main objectives. In particular, we propose a new hyper-matheuristic grounded on a MILP-based decomposition in which the optimization problem is divided into two hierarchical subproblems. The new approach decomposes the model into discrete and continuous variables, treating each subproblem through different optimization methods. In particular, metaheuristics are used for dealing with the discrete variables, whereas exact methods are used for the set of continuous variables. The metaheuristics use an indirect representation that encodes an incomplete solution for the problem, whereas the exact method is applied to decode the solution and generate a complete solution. The experimental results, based on simulated data in the context of Data Envelopment Analysis, show that the solutions obtained through the new approach outperform those found by solving the problem globally using a metaheuristic method. Finally, regarding the new hyper-matheuristic scheme, the best algorithm selection is found for a set of cooperative metaheuristics ans exact optimization algorithms. PeerJ Inc. 2022-01-20 /pmc/articles/PMC8802783/ /pubmed/35174264 http://dx.doi.org/10.7717/peerj-cs.828 Text en © 2022 Gonzalez et al. https://creativecommons.org/licenses/by/4.0/This is an open access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, reproduction and adaptation in any medium and for any purpose provided that it is properly attributed. For attribution, the original author(s), title, publication source (PeerJ Computer Science) and either DOI or URL of the article must be cited.
spellingShingle Algorithms and Analysis of Algorithms
Gonzalez, Martin
López-Espín, Jose J.
Aparicio, Juan
Talbi, El-Ghazali
A hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis
title A hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis
title_full A hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis
title_fullStr A hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis
title_full_unstemmed A hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis
title_short A hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis
title_sort hyper-matheuristic approach for solving mixed integer linear optimization models in the context of data envelopment analysis
topic Algorithms and Analysis of Algorithms
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8802783/
https://www.ncbi.nlm.nih.gov/pubmed/35174264
http://dx.doi.org/10.7717/peerj-cs.828
work_keys_str_mv AT gonzalezmartin ahypermatheuristicapproachforsolvingmixedintegerlinearoptimizationmodelsinthecontextofdataenvelopmentanalysis
AT lopezespinjosej ahypermatheuristicapproachforsolvingmixedintegerlinearoptimizationmodelsinthecontextofdataenvelopmentanalysis
AT apariciojuan ahypermatheuristicapproachforsolvingmixedintegerlinearoptimizationmodelsinthecontextofdataenvelopmentanalysis
AT talbielghazali ahypermatheuristicapproachforsolvingmixedintegerlinearoptimizationmodelsinthecontextofdataenvelopmentanalysis
AT gonzalezmartin hypermatheuristicapproachforsolvingmixedintegerlinearoptimizationmodelsinthecontextofdataenvelopmentanalysis
AT lopezespinjosej hypermatheuristicapproachforsolvingmixedintegerlinearoptimizationmodelsinthecontextofdataenvelopmentanalysis
AT apariciojuan hypermatheuristicapproachforsolvingmixedintegerlinearoptimizationmodelsinthecontextofdataenvelopmentanalysis
AT talbielghazali hypermatheuristicapproachforsolvingmixedintegerlinearoptimizationmodelsinthecontextofdataenvelopmentanalysis