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

Previous  |  FULL TEXT  |  Next

 

UDC 519.854

Application of the Global Equilibrium Search Method for Solving Boolean Programming Problems

Ivan Sergienko ORCID ID favicon Big,   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 ComputerAided 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. 4251. 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. 481493. 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. 11621173. https://doi.org/10.1016/j.engappai.2012.09.001

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT  |  Next

 

 

            Archive

 

© Website and Design. 2019-2024,

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

National Academy of Sciences of Ukraine.