Skip to main content
SpringerLink
Log in

Genetic Algorithms with Optimality Cuts to the Max-Cut Problem

  • Conference paper
  • First Online:
Intelligent Systems (BRACIS 2023)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 14197))

Included in the following conference series:

  • 240 Accesses

Abstract

The Max-Cut Problem involves dividing a set of n vertices in a weighted graph \(G = (V, E)\) into two subsets \((S, \bar{S})\) in such a way that the sum of the weights between the subsets is maximized. This research introduces two heuristic methods that combine Genetic Algorithm, Tabu Search, and a set of optimality cuts, which are also proven in this work. To the best of our knowledge, we are the first to utilize these inequalities in conjunction with the genetic algorithm methodology to solve the Max-Cut problem. Computational experiments using a benchmark set of 54 instances, ranging from 800 to 3000 vertices, demonstrate that the incorporation of optimality cuts is a crucial factor for our methodologies to compete effectively with six state-of-the-art approaches for the Max-Cut problem and our genetic algorithm that incorporated optimality cuts in the population generation was able to improve the state-of-the-art value for the G51 instance and find the same solutions as the literature in 31 other instances.

This work is partially supported by Universal CNPq [422912/2021-2].

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 59.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Agrawal, R., Rajagopalan, S., Srikant, R., Xu, Y.: Mining newsgroups using networks arising from social behavior. In: Proceedings of the 12th international conference on World Wide Web, pp. 529–535 (2003)

    Google Scholar 

  2. Alidaee, B., Sloan, H., Wang, H.: Simple and fast novel diversification approach for the UBQP based on sequential improvement local search. Comput. Ind. Eng. 111, 164–175 (2017)

    Article  Google Scholar 

  3. Barahona, F.: The max-cut problem on graphs not contractible to K5. Oper. Res. Lett. 2(3), 107–111 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  4. Barahona, F., Grötschel, M., Jünger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Oper. Res. 36(3), 493–513 (1988)

    Article  MATH  Google Scholar 

  5. Bramoullé, Y.: Anti-coordination and social interactions. Games Econom. Behav. 58(1), 30–49 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  6. Burer, S., Monteiro, R., Zhang, Y.: Rank-two relaxation heuristic for max-cut and other binary quadratic problems. SIAM J. Optim. 12(2), 503–521 (2001/2002)

    Google Scholar 

  7. Chui, K.T., Gupta, B.B., Vasant, P.: A genetic algorithm optimized RNN-LSTM model for remaining useful life prediction of turbofan engine. Electronics 10(3), 285 (2021)

    Article  Google Scholar 

  8. De Simone, C., Diehl, M., Jünger, M., Mutzel, P., Reinelt, G., Rinaldi, G.: Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm. J. Stat. Phys. 80(12), 487–496 (1995)

    Article  MATH  Google Scholar 

  9. De Simone, C., Rinaldi, G.: A cutting plane algorithm for the max-cut problem. Optim. Methods Softw. 3(13), 195–214 (1994)

    Article  Google Scholar 

  10. Dunning, I., Gupta, S., Silberholz, J.: What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS J. Comput. 30(3), 608–624 (2018)

    Article  MATH  Google Scholar 

  11. Facchetti, G., Iacono, G., Altafini, C.: Computing global structural balance in large-scale signed social networks. Proc. Natl. Acad. Sci. 108(52), 20953–20958 (2011)

    Article  Google Scholar 

  12. Galinier, P., Boujbel, Z., Fernandes, M.: An efficient memetic algorithm for the graph partitioning problem. Annals OR 191, 1–22 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  13. Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673–696 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  14. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85–103. Springer, Cham (1972). https://doi.org/10.1007/978-1-4684-2001-2_9

  15. Kim, S.H., Kim, Y.H., Moon, B.R.: A hybrid genetic algorithm for the MAX CUT problem. In: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, pp. 416–423. Morgan Kaufmann Publishers Inc. (2001)

    Google Scholar 

  16. Kim, Y.H., Yoon, Y., Geem, Z.W.: A comparison study of harmony search and genetic algorithm for the MAX-CUT problem. Swarm Evol. Comput. 44, 130–135 (2019)

    Article  Google Scholar 

  17. Kochenberger, G.A., Hao, J.K., Lü, Z., Wang, H., Glover, F.: Solving large scale Max Cut problems via tabu search. J. Heuristics 19(4), 565–571 (2013)

    Article  Google Scholar 

  18. Kolli, N., Narayanaswamy, B.: Influence maximization from cascade information traces in complex networks in the absence of network structure. IEEE Trans. Comput. Soc. Syst. 6(6), 1147–1155 (2019)

    Article  Google Scholar 

  19. Krislock, N., Malick, J., Rouoin, F.: Improved semidefinite bounding procedure for solving Max-Cut problems to optimality. Math. Program. 143(1–2), 61–86 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  20. Ma, F., Hao, J.K.: A multiple search operator heuristic for the max-k-cut problem. Ann. Oper. Res. 248(1–2), 365–403 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  21. Martí, R., Duarte, A., Laguna, M.: Advanced scatter search for the Max-Cut problem. INFORMS J. Comput. 21(1), 26–38 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  22. Mirjalili, S.: Genetic algorithm. In: Evolutionary Algorithms and Neural Networks. SCI, vol. 780, pp. 43–55. Springer, Cham (2019). https://doi.org/10.1007/978-3-319-93025-1_4

    Chapter  MATH  Google Scholar 

  23. Myklebust, T.G.: Solving maximum cut problems by simulated annealing. arXiv preprint (2015)

    Google Scholar 

  24. Pandey, A., Banerjee, S.: Test suite optimization using firefly and genetic algorithm. Int. J. Softw. Sci. Comput. Intell. (IJSSCI) 11(1), 31–46 (2019)

    Article  Google Scholar 

  25. Rendl, F., Rinaldi, G., Wiegele, A.: A branch and bound algorithm for Max-Cut based on combining semidefinite and polyhedral relaxations. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 295–309. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72792-7_23

    Chapter  MATH  Google Scholar 

  26. Sun, L., Cheng, X., Liang, Y.: Solving job shop scheduling problem using genetic algorithm with penalty function. Int. J. Intell. Inf. Process. 1(2), 65–77 (2010)

    Google Scholar 

  27. Wu, Q., Hao, J.-K.: A memetic approach for the Max-Cut problem. In: Coello, C.A.C., Cutello, V., Deb, K., Forrest, S., Nicosia, G., Pavone, M. (eds.) PPSN 2012. LNCS, vol. 7492, pp. 297–306. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32964-7_30

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. NEMO Research Laboratory, Federal University of Ceará - Campus Russas, Russas, CE, 62900-420, Brazil

    Pablo Luiz Braga Soares

  2. Institute of Computing, University of Campinas, Campinas, SP, 13083-970, Brazil

    Carlos Victor Dantas Araújo

Authors
  1. Pablo Luiz Braga Soares
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlos Victor Dantas Araújo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pablo Luiz Braga Soares .

Editor information

Editors and Affiliations

  1. Federal University of São Carlos, São Carlos, Brazil

    Murilo C. Naldi

  2. Centro Universitario da FEI, São Bernardo do Campo, Brazil

    Reinaldo A. C. Bianchi

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Soares, P.L.B., Araújo, C.V.D. (2023). Genetic Algorithms with Optimality Cuts to the Max-Cut Problem. In: Naldi, M.C., Bianchi, R.A.C. (eds) Intelligent Systems. BRACIS 2023. Lecture Notes in Computer Science(), vol 14197. Springer, Cham. https://doi.org/10.1007/978-3-031-45392-2_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-45392-2_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-45391-5

  • Online ISBN: 978-3-031-45392-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation