C&SA | Contents

Volume 59 >>> № 5 SEPTEMBER — OCTOBER 2023

-->

UDC 519.8

I.V. Sergienko¹, V.P. Shylo², V.O. Roshchyn³

¹ V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

Sergiyenko@nas.gov.ua

² V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

v.shylo@gmail.com

³ V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

dopt135@gmail.com

ALGORITHM UNIONS FOR SOLVING DISCRETE OPTIMIZATION PROBLEMS

Abstract. The algorithm unions (portfolios and teams) of optimization algorithms, their properties, and their impact on the acceleration of the optimization process are considered. The global equilibrium search applications in algorithm unions to individual discrete optimization problems and various information exchange schemes in algorithm teams are researched. Significant emphasis is placed on the experimental research and analysis of the developed algorithm portfolios and teams, conducted sequentially and using the multiprocessor computing complex SCIT-4 of the V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine. The resulting efficiency of algorithm unions shows that the team approach has significant advantages over algorithm portfolios.

Keywords: algorithm unions (portfolios and teams), discrete optimization, information exchange, experimental research, algorithm unions efficiency.

full text

REFERENCES

Sergienko I.V. Topical directions of informatics. In memory of V. M. Glushkov. New York; Heidelberg; Dordrecht; London: Springer, 2014. 286 p. https://doi.org/10.1007/978-1-4939-0476-1.

Papadimitriou H., Steiglitz K. Combinatorial optimization. Algorithms and complexity. Moscow: Mir, 1985. 512 p.

Mikhalevich V.S., Trubin V.A., Shor N.Z. Optimization problems of production and transport planning [in Russian]. Moscow: Nauka, 1986. 264 p.

Glover F., Laguna M. Tabu search. Boston: Kluwer Academic Publishers, 1997. 382 р.

Sergienko I.V., Shylo V.P. Problems of discrete optimization: problems, methods of solution, research [in Russian]. Kyiv: Nauk. Dumka, 2003. 264 p.

Sergienko I.V., Shylo V.P., Roschyn V.O. Discrete optimization. Algorithms and their effective use [in Ukrainian]. Kyiv: Nauk. Dumka, 2020. 144 p.

Stoyan Yu.G., Yakovlev S.V., Pichugina O.S. Euclidean combinatorial configurations [in Russian]. Kharkiv: Constanta, 2017. 404 p.

Semenova N.V., Kolechkina L.M. Vector problems of discrete optimization on combinatorial sets: Research and solution methods. Kyiv: Nauk. Dumka, 2009. 266 p.

Souravlias D., Parsopoulos K., Kotsireas I., Pardalos P. Algorithm portfolios: Advances, applications, and challenges. New York: Springer, 2021. 108 p. https://doi.org/10.1007/ 978-3-030-68514-0 .

Maksyshko N.K., Zakhovalko T.V. Models and methods of solving applied coverage problems on graphs and hypergraphs. Zaporizhzhia: Polygraph, 2009. 244 p.

Hulianytskyi L.F., Mulesa O.Yu. Applied methods of combinatorial optimization [in Ukrainian]. Kyiv: Kyiv University, 2016. 144 p.

Kozin I.V. Symmetry principles in decision theory [in Russian]. Zaporozhye: Polygraph, 2007. 164 p.

Gupal A.M., Sergienko I.V. Symmetry in DNA. Methods for recognition of discrete sequences [in Russian]. Kyiv: Nauk. Dumka, 2016. 228 p.

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.

Luby M., Ertel W. Optimal parallelization of Las Vegas algorithms. Lecture Notes in Computer Science. 1994. Vol. 775. Р. 461–474.

Shylo O.V., Middelkoop T., Pardalos P.M. Restart strategies in optimization: Parallel and serial cases. Parallel Computing. 2011. Vol. 37, N 1. Р. 60–68.

Gomes C.P., Selman B. Algorithm portfolios. Artificial Intelligence. 2001. Vol. 126, N 1–2. P. 43–62.

Huberman B.A. An economics approach to hard computational problems. Science. 1997. Vol. 275, N 5296. P. 51–54.

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.

Shylo V.P., Roshchin V.A., Shilo P.V. Building a portfolio of algorithms for parallelizing the process of solving the problem of the maximum weighted cut of a graph. Komp'yuternaya matematik. 2014. N 2. P. 163–170.

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.

Shylo V.P., Shylo O.V. Path relinking scheme for the max-cut problem within global equilibrium search. International J. of Swarm Intelligence Res. 2011. Vol. 2, N 2. P. 42–51.

Shylo V.P., Glover F., Sergienko I.V. Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel. Cybernetics and Systems Analysis. 2015. Vol. 51, N 1. P. 16–24. https://doi.org/10.1007/s10559-015-9692-2 .

Barahona F., Grotschel M., Junger M., Reinelt G. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research. 1988. Vol. 36, N 3. P. 493–513.

Chang K.C., Du D.H.-C. Efficient algorithms for layer assignment problem. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. 1987. Vol. 6, Iss. 1. P. 67–78.

Poljak S., Tuza Z. Maximum cuts and large bipartite subgraphs. In: Combinatorial Optimization. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Cook W., Lovasz L., Seymour P. (Eds.). 1995. Vol. 20. P. 181–244.

Palubeckis G. Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica. 2006. Vol. 17, N 2. P. 279–296.

Helmberg C., Rendl F. A spectral bundle method for semidefinite programming. SIAM J. on Optimization. 2000. Vol. 10, Iss. 3. P. 673–696.

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

Benlic U., Hao J.K. Breakout local search for the max-cut problem. Engineering Applications of Artificial Intelligence. 2013. Vol. 26, Iss. 3. P. 1162–1173.