The Efficiency of Discrete Optimization Algorithm Portfolios
Introduction. Solving large-scale discrete optimization problems requires the processing of large-scale data in a reasonable time. Efficient solving is only possible by using multiprocessor computer systems. However, it is a daunting challenge to adapt existing optimization algorithms to get all the...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
V.M. Glushkov Institute of Cybernetics
2021-06-01
|
| Series: | Кібернетика та комп'ютерні технології |
| Subjects: | |
| Online Access: | http://cctech.org.ua/13-vertikalnoe-menyu-en/233-abstract-21-2-1-arte |
| _version_ | 1798046376103247872 |
|---|---|
| author | Ivan Sergienko Vladimir Shylo Valentyna Roshchyn Petro Shylo |
| author_facet | Ivan Sergienko Vladimir Shylo Valentyna Roshchyn Petro Shylo |
| author_sort | Ivan Sergienko |
| collection | DOAJ |
| description | Introduction. Solving large-scale discrete optimization problems requires the processing of large-scale data in a reasonable time. Efficient solving is only possible by using multiprocessor computer systems. However, it is a daunting challenge to adapt existing optimization algorithms to get all the benefits of these parallel computing systems. The available computational resources are ineffective without efficient and scalable parallel methods. In this connection, the algorithm unions (portfolios and teams) play a crucial role in the parallel processing of discrete optimization problems.
The purpose. The purpose of this paper is to research the efficiency of the algorithm portfolios by solving the weighted max-cut problem. The research is carried out in two stages using stochastic local search algorithms.
Results. In this paper, we investigate homogeneous and non-homogeneous algorithm portfolios. We developed the homogeneous portfolios of two stochastic local optimization algorithms for the weighted max-cut problem, which has numerous applications. The results confirm the advantages of the proposed methods.
Conclusions. Algorithm portfolios could be used to solve well-known discrete optimization problems of unprecedented scale and significantly improve their solving time. Further, we propose using communication between algorithms, namely teams and portfolios of algorithm teams. The algorithms in a team communicate with each other to boost overall performance. It is supposed that algorithm communication allows enhancing the best features of the developed algorithms and would improve the computational times and solution quality. The underlying algorithms should be able to utilize relevant data that is being communicated effectively to achieve any computational benefit from communication. |
| first_indexed | 2024-04-11T23:37:53Z |
| format | Article |
| id | doaj.art-514e79e1ae754986b685fd165c2aec77 |
| institution | Directory Open Access Journal |
| issn | 2707-4501 2707-451X |
| language | English |
| last_indexed | 2024-04-11T23:37:53Z |
| publishDate | 2021-06-01 |
| publisher | V.M. Glushkov Institute of Cybernetics |
| record_format | Article |
| series | Кібернетика та комп'ютерні технології |
| spelling | doaj.art-514e79e1ae754986b685fd165c2aec772022-12-22T03:56:54ZengV.M. Glushkov Institute of CyberneticsКібернетика та комп'ютерні технології2707-45012707-451X2021-06-01251210.34229/2707-451X.21.2.110-34229-2707-451X-21-2-1The Efficiency of Discrete Optimization Algorithm PortfoliosIvan Sergienko0https://orcid.org/0000-0002-1118-7451Vladimir Shylo1Valentyna Roshchyn2Petro Shylo3V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, KyivV.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, KyivV.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, KyivV.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, KyivIntroduction. Solving large-scale discrete optimization problems requires the processing of large-scale data in a reasonable time. Efficient solving is only possible by using multiprocessor computer systems. However, it is a daunting challenge to adapt existing optimization algorithms to get all the benefits of these parallel computing systems. The available computational resources are ineffective without efficient and scalable parallel methods. In this connection, the algorithm unions (portfolios and teams) play a crucial role in the parallel processing of discrete optimization problems. The purpose. The purpose of this paper is to research the efficiency of the algorithm portfolios by solving the weighted max-cut problem. The research is carried out in two stages using stochastic local search algorithms. Results. In this paper, we investigate homogeneous and non-homogeneous algorithm portfolios. We developed the homogeneous portfolios of two stochastic local optimization algorithms for the weighted max-cut problem, which has numerous applications. The results confirm the advantages of the proposed methods. Conclusions. Algorithm portfolios could be used to solve well-known discrete optimization problems of unprecedented scale and significantly improve their solving time. Further, we propose using communication between algorithms, namely teams and portfolios of algorithm teams. The algorithms in a team communicate with each other to boost overall performance. It is supposed that algorithm communication allows enhancing the best features of the developed algorithms and would improve the computational times and solution quality. The underlying algorithms should be able to utilize relevant data that is being communicated effectively to achieve any computational benefit from communication.http://cctech.org.ua/13-vertikalnoe-menyu-en/233-abstract-21-2-1-artediscrete optimizationalgorithm portfolioscomputational experiment |
| spellingShingle | Ivan Sergienko Vladimir Shylo Valentyna Roshchyn Petro Shylo The Efficiency of Discrete Optimization Algorithm Portfolios Кібернетика та комп'ютерні технології discrete optimization algorithm portfolios computational experiment |
| title | The Efficiency of Discrete Optimization Algorithm Portfolios |
| title_full | The Efficiency of Discrete Optimization Algorithm Portfolios |
| title_fullStr | The Efficiency of Discrete Optimization Algorithm Portfolios |
| title_full_unstemmed | The Efficiency of Discrete Optimization Algorithm Portfolios |
| title_short | The Efficiency of Discrete Optimization Algorithm Portfolios |
| title_sort | efficiency of discrete optimization algorithm portfolios |
| topic | discrete optimization algorithm portfolios computational experiment |
| url | http://cctech.org.ua/13-vertikalnoe-menyu-en/233-abstract-21-2-1-arte |
| work_keys_str_mv | AT ivansergienko theefficiencyofdiscreteoptimizationalgorithmportfolios AT vladimirshylo theefficiencyofdiscreteoptimizationalgorithmportfolios AT valentynaroshchyn theefficiencyofdiscreteoptimizationalgorithmportfolios AT petroshylo theefficiencyofdiscreteoptimizationalgorithmportfolios AT ivansergienko efficiencyofdiscreteoptimizationalgorithmportfolios AT vladimirshylo efficiencyofdiscreteoptimizationalgorithmportfolios AT valentynaroshchyn efficiencyofdiscreteoptimizationalgorithmportfolios AT petroshylo efficiencyofdiscreteoptimizationalgorithmportfolios |