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...
Autores principales: | , , , |
---|---|
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 |