2023, issue 2, p. 11-22
Received 11.07.2023; Revised 21.07.2023; Accepted 25.07.2023
Published 28.07.2023; First Online 18.08.2023
https://doi.org/10.34229/2707-451X.23.2.2
Application of the Global Equilibrium Search Method for Solving Boolean Programming Problems
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. The significance of methods and algorithms for solving discrete optimization problems in mathematical supporting computer technologies of diverse levels and objectives is increasing. Consequently, the efficacy of discrete optimization methods deserves particular attention, as it drives the advancement of techniques capable of solving complex real-world problems. This paper introduces the Global Equilibrium Search (GES) method as a highly effective approach for solving Boolean programming problems, thus contributing to the field's progress and applicability.
Purpose. We describe the successful application of the approximate probabilistic GES method for effectively solving various Boolean programming problems.
Results. This paper explores the application of sequential GES algorithms for solving Boolean linear, Boolean quadratic programming, and other related problems with their specific characteristics. In our study, we conducted a comparative analysis to assess the effectiveness of GES algorithms by evaluating them against state-of-the-art approaches. Additionally, to parallelize the optimization process for discrete programming problems, we introduced algorithm unions, specifically portfolios, and teams. The efficiency of GES algorithm portfolios and teams is investigated by solving the maximum weighted graph cut problem, with subsequent comparisons to identify distinctions between them.
Conclusions. Based on the accumulated experience of applying GES algorithms and their modifications to solve discrete optimization problems, this study establishes the GES method as the leading approximate approach for Boolean programming. The results demonstrate the GES algorithm unions experience a significant boost in the optimization process speed, whereas algorithm teams demonstrate higher efficiency.
Keywords: global equilibrium search method, Boolean programming problems, experimental studies, algorithm efficiency, algorithm unions (portfolios and teams).
Cite as: Sergienko I., Shylo V., Roshchyn V., Shylo P. Application of the Global Equilibrium Search Method for Solving Boolean Programming Problems. Cybernetics and Computer Technologies. 2023. 2. P. 11–22. https://doi.org/10.34229/2707-451X.23.2.2
References
1. Shylo V.P. The method of global equilibrium search. Cybern Syst Anal. 1999. 35 (1). P. 68–74. https://doi.org/10.1007/BF02667916
2. Sergienko I.V. Mathematical models and methods for solving discrete optimization problems. Kyiv: Naukova dumka. 1988. 472 p. (in Russian)
3. Kirkpatrick S., Gelatti C.D., Vecchi M.P. Optimization by simulated annealing. Science. 1983. Vol. 220. P. 671–680. https://doi.org/10.1126/science.220.4598.671
4. Aarts E., Korst J. Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing. New York: J. Wiley and Sons, 1989. 284 p.
5. Sergienko I.V., Shylo V.P. Discrete optimization problems: problems, solution methods, studies. Kyiv: Naukova dumka, 2003. 264 p. (in Russian)
6. Sergienko I.V., Shylo V.P., Roshchyn V.O. Discrete optimization. Algorithms and their effective use. Kyiv: Naukova dumka, 2020. 144 p. (in Ukrainian)
7. Papadimitriou C., Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. New York: Dover Publications, 1998. 528 p.
8. Glover F., Laguna M. Tabu search. Boston: Kluwer Academic Publishers, 1997. 382 р. https://doi.org/10.1007/978-1-4615-6089-0
9. Roshchyn V.O., Boyarchuk D.O., Lyashko V.I., Shylo P.V. Solving set covering problem by global equilibrium search. Naukovi zapysky NaUKMA. Kompiuterni nauky. 2014. 163. P. 25–32. (in Ukrainian) https://ekmair.ukma.edu.ua/handle/123456789/3402
10. Shylo V.P., Shylo O.V. Systems Analysis; Solving unconstrained binary quadratic programming problem by global equilibrium search. Cybern Syst Anal. 2011. 47 (6). P. 889–897. https://doi.org/10.1007/s10559-011-9368-5
11. Alidaee B., Kochenberger G., Ahmadian A. 0–1 quadratic programming approach for the optimal solution of two scheduling problems. International J. of Systems Science. 1994. Vol. 25. P. 401–408. https://doi.org/10.1080/00207729408928968
12. Gallo G., Hammer P.L., Simeone B. Quadratic knapsack problems. Math. Programming. 1980. Vol. 12. P. 132–149. https://doi.org/10.1007/BFb0120892
13. Pardalos P.M., Xue J. The maximum clique problem. J. of Global Optimiz. 1994. Vol. 4. P. 301–328. https://doi.org/10.1007/BF01098364
14. Palubeckis G. Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica. 2006. Vol. 17. No. 2. P. 279–296. https://doi.org/10.15388/Informatica.2006.138
15. Lu Z., Glover F., Hao Jin-Kao. A hybrid metaheuristic approach to solving the UBQP problem. Eur. J. Oper. Res. 2010. 207 (3). P. 1254–1262. https://doi.org/10.1016/j.ejor.2010.06.039
16. Barahona F., Grotschel M., Junger M., Reinelt G. An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 1988. Vol. 36. P. 493–513. https://doi.org/10.1287/opre.36.3.493
17. 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. P. 67–78. https://doi.org/10.1109/TCAD.1987.1270247
18. Poljak S., Tuza Z. Maximum cuts and large bipartite subgraphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1995. Vol. 20. P. 181–244. https://doi.org/10.1090/dimacs/020/04
19. Prokopyev O., Shylo O., Shylo V. Solving weighted MAX-SAT via global equilibrium search. Oper. Res. Lett. 2008. Vol. 36. No. 4. P. 434–438. https://doi.org/10.1016/j.orl.2007.11.007
20. Shylo V.P., Shylo O.P. Solving the maxcut problem by the global equilibrium search. Cybern Syst Anal. 2010. 46 (5). P. 744–754. https://doi.org/10.1007/s10559-010-9256-4
21. Shylo V.P., Shylo O.V., Roshchyn V.O. Solving weighted max-cut problem by global equilibrium search. Cybern Syst Anal. 2012. 48 (4). P. 563–567. https://doi.org/10.1007/s10559-012-9435-6
22. 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. https://doi.org/10.4018/jsir.2011040103
23. Glover F., Laguna M., Marti R. Fundamentals of scatter search and path relinking. Control and Cybernetics. 2000. Vol. 39. P. 653–684.
24. 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
25. 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
26. Shylo V.P., Roshchyn V.O., Shylo P.V. Designing algorithms portfolio to parallelize the process of solving the maximum weighted graph cut problem. Kompiuterna matematyka. 2014. 1. P. 163–170. (in Russian)
27. Shylo V.P., Roshchyn V.O., Shylo P.V. Parallel algorithms for solving the Boolean quadratic programming problem. Kompiuterna matematyka. 2015. 2. P. 12–20. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/168376
28. 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. No. 1. P. 20–29. https://doi.org/10.1007/s10559-015-9692-2
29. 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. Vol 130. P. 481–493. https://doi.org/10.1007/978-3-319-68640-0_23
30. Benlic U., Hao J. K. Breakout local search for the max-cut problem. J. Engineering Applications of Artificial Intelligence. 2013. 26 (3). P. 1162–1173. https://doi.org/10.1016/j.engappai.2012.09.001
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)