A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers
Metaheuristic and exact methods are one of the most common tools to solve Mixed-Integer Optimization Problems (MIPs). Most of these problems are NP-hard problems, being intractable to obtain optimal solutions in a reasonable time when the size of the problem is huge. In this paper, a hybrid parallel...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-09-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/9/9/1541 |
| _version_ | 1797553089872396288 |
|---|---|
| author | Martín González Jose J. López-Espín Juan Aparicio |
| author_facet | Martín González Jose J. López-Espín Juan Aparicio |
| author_sort | Martín González |
| collection | DOAJ |
| description | Metaheuristic and exact methods are one of the most common tools to solve Mixed-Integer Optimization Problems (MIPs). Most of these problems are NP-hard problems, being intractable to obtain optimal solutions in a reasonable time when the size of the problem is huge. In this paper, a hybrid parallel optimization algorithm for matheuristics is studied. In this algorithm, exact and metaheuristic methods work together to solve a Mixed Integer Linear Programming (MILP) problem which is divided into two different subproblems, one of which is linear (and easier to solve by exact methods) and the other discrete (and is solved using metaheuristic methods). Even so, solving this problem has a high computational cost. The algorithm proposed follows an efficient decomposition which is based on the nature of the decision variables (continuous versus discrete). Because of the high cost of the algorithm, as this kind of problem belongs to NP-hard problems, parallelism techniques have been incorporated at different levels to reduce the computing cost. The matheuristic has been optimized both at the level of the problem division and internally. This configuration offers the opportunity to improve the computational time and the fitness function. The paper also focuses on the performance of different optimization software packages working in parallel. In particular, a comparison of two well-known optimization software packages (CPLEX and GUROBI) is performed when they work executing several simultaneous instances, solving various problems at the same time. Thus, this paper proposes and studies a two-level parallel algorithm based on message-passing (MPI) and shared memory (Open MP) schemes where the two subproblems are considered and where the linear problem is solved by using and studying optimization software packages (CPLEX and GUROBI). Experiments have also been carried out to ascertain the performance of the application using different programming paradigms (shared memory and distributed memory). |
| first_indexed | 2024-03-10T16:10:25Z |
| format | Article |
| id | doaj.art-32a43e785c434715b5aa6d972c686925 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-10T16:10:25Z |
| publishDate | 2020-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-32a43e785c434715b5aa6d972c6869252023-11-20T14:31:00ZengMDPI AGElectronics2079-92922020-09-0199154110.3390/electronics9091541A Parallel Algorithm for Matheuristics: A Comparison of Optimization SolversMartín González0Jose J. López-Espín1Juan Aparicio2Center of Operations Research, Univeristy Miguel Hernandez of Elche, 03202 Elche, SpainCenter of Operations Research, Univeristy Miguel Hernandez of Elche, 03202 Elche, SpainCenter of Operations Research, Univeristy Miguel Hernandez of Elche, 03202 Elche, SpainMetaheuristic and exact methods are one of the most common tools to solve Mixed-Integer Optimization Problems (MIPs). Most of these problems are NP-hard problems, being intractable to obtain optimal solutions in a reasonable time when the size of the problem is huge. In this paper, a hybrid parallel optimization algorithm for matheuristics is studied. In this algorithm, exact and metaheuristic methods work together to solve a Mixed Integer Linear Programming (MILP) problem which is divided into two different subproblems, one of which is linear (and easier to solve by exact methods) and the other discrete (and is solved using metaheuristic methods). Even so, solving this problem has a high computational cost. The algorithm proposed follows an efficient decomposition which is based on the nature of the decision variables (continuous versus discrete). Because of the high cost of the algorithm, as this kind of problem belongs to NP-hard problems, parallelism techniques have been incorporated at different levels to reduce the computing cost. The matheuristic has been optimized both at the level of the problem division and internally. This configuration offers the opportunity to improve the computational time and the fitness function. The paper also focuses on the performance of different optimization software packages working in parallel. In particular, a comparison of two well-known optimization software packages (CPLEX and GUROBI) is performed when they work executing several simultaneous instances, solving various problems at the same time. Thus, this paper proposes and studies a two-level parallel algorithm based on message-passing (MPI) and shared memory (Open MP) schemes where the two subproblems are considered and where the linear problem is solved by using and studying optimization software packages (CPLEX and GUROBI). Experiments have also been carried out to ascertain the performance of the application using different programming paradigms (shared memory and distributed memory).https://www.mdpi.com/2079-9292/9/9/1541parallel algorithmexact methodsMixed Integer ProblemsMILP decompositionmatheuristics |
| spellingShingle | Martín González Jose J. López-Espín Juan Aparicio A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers Electronics parallel algorithm exact methods Mixed Integer Problems MILP decomposition matheuristics |
| title | A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers |
| title_full | A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers |
| title_fullStr | A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers |
| title_full_unstemmed | A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers |
| title_short | A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers |
| title_sort | parallel algorithm for matheuristics a comparison of optimization solvers |
| topic | parallel algorithm exact methods Mixed Integer Problems MILP decomposition matheuristics |
| url | https://www.mdpi.com/2079-9292/9/9/1541 |
| work_keys_str_mv | AT martingonzalez aparallelalgorithmformatheuristicsacomparisonofoptimizationsolvers AT josejlopezespin aparallelalgorithmformatheuristicsacomparisonofoptimizationsolvers AT juanaparicio aparallelalgorithmformatheuristicsacomparisonofoptimizationsolvers AT martingonzalez parallelalgorithmformatheuristicsacomparisonofoptimizationsolvers AT josejlopezespin parallelalgorithmformatheuristicsacomparisonofoptimizationsolvers AT juanaparicio parallelalgorithmformatheuristicsacomparisonofoptimizationsolvers |