Received 02.06.2021; Revised 09.06.2021; Accepted 24.06.2021

Published 30.06.2021; First Online 01.07.2021

https://doi.org/10.34229/2707-451X.21.2.1

Previous  |  Full text (in Ukrainian)  |  Next

 

UDC 519.854

The Efficiency of Discrete Optimization Algorithm Portfolios

Ivan Sergienko ,   Vladimir Shylo,   Valentyna Roshchyn,   Petro Shylo ^*

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

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.

 

Keywords: Discrete optimization, algorithm portfolios, computational experiment.

 

Cite as: Sergienko I., Shylo V., Roshchyn V., Shylo P. The Efficiency of Discrete Optimization Algorithm Portfolios. Cybernetics and Computer Technologies. 2021. 2. P. 5–12. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.2.1

 

References

           1.     Gomes C.P., Selman B. Algorithm portfolios. Artificial Intelligence. 2001. Vol. 126, N (1–2). P. 43–62. https://doi.org/10.1016/S0004-3702(00)00081-3

           2.     Huberman B.A. An economics approach to hard computational problems. Science. 1997. Vol. 275 N 5296. P. 51–54. https://doi.org/10.1126/science.275.5296.51

           3.     Chabrier A., Danna E., Pape C.L., Perron L. Solving a network design problem. Annals of Oper. Res. 2004. Vol. 130, N 1–4. P. 217–239. https://doi.org/10.1023/B:ANOR.0000032577.81139.84

           4.     Shylo V.P., Roshchyn V.A., Shylo P.V. Construction of algorithm portfolio for parallelization the solving process of WMAXCUT problem. Kompiuterna Matematyka. 2014. N 2. P. 163–170.

           5.     Shylo V.P., Glover F., Sergienko I.V. Teams of Global Equilibrium Search Algorithms for Solving the Weighted Maximum Cut Problem in Parallel. 2015. Cybern Syst Anal. Vol. 51, N 1. P. 16–24. https://doi.org/10.1007/s10559-015-9692-2

           6.     Shylo V.P., Shylo O.V. Algorithm Portfolios and Teams in Parallel Optimization. Optimization Methods and Applications. S. Butenko, P.M. Pardalos, V. Shylo (eds.). New York: Springer, 2017. P. 481–493. https://doi.org/10.1007/978-3-319-68640-0_23

           7.     Mostovyi O., Prokopyev O.A., Shylo O.V. On maximum speedup ratio of restart algorithm portfolios. INFORMS J. on Computing. 2013. Vol. 25, N 2. Р. 222–229. https://doi.org/10.1287/ijoc.1120.0497

           8.     Shylo O.V., Prokopyev O.A., Rajgopal J. On algorithm portfolios and restart strategies. Oper. Res. Lett. 2011. Vol. 39, N 1. P. 49–52. https://doi.org/10.1016/j.orl.2010.10.003

           9.     Shilo V.P. The method of global equilibrium search. Cybern Syst Anal. 1999. Vol. 35, N 1. P. 68–74. https://doi.org/10.1007/BF02667916

       10.     Sergienko I.V., Shylo V.P. Problems of discrete optimization: Challenges and main approaches to solve them. Kyiv: Naukova Dumka, 2003. 264 p.

       11.     Helmberg C., Rendl F. A spectral bundle method for semidefinite programming. SIAM J. on Optimization. 2000. Vol. 10. P. 673–696. https://doi.org/10.1137/S1052623497328987

       12.     Burer S., Monteiro R.D.C., Zhang Y. Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs. SIAM J. on Optimization. 2002. Vol. 12. P. 503–521. https://doi.org/10.1137/S1052623400382467

       13.     Glover F., Laguna M., Marti R. Fundamentals of scatter search and path relinking. Control and Cybernetics. 2000. Vol. 39. P. 653–684.

       14.     Benlic U., Hao J.K. Breakout local search for the max-cut problem. J. Engineering Applications of Artificial Intelligence. 2013. Vol. 26, N 3. P. 1162–1173. https://doi.org/10.1016/j.engappai.2012.09.001

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  Full text (in Ukrainian)  |  Next