Application of the Golden Ball to the Maximum Cut Problem

• Jailon W. B. Oliveira da Silva UFC
• Carlos V. Dantas Araújo UFC
• Pablo L. Braga Soares UFC

DOI: https://doi.org/10.5753/etc.2025.9186

Abstract

This work applies the Golden Ball metaheuristic to the Maximum Cut Problem in graphs, modeling solutions as players organized into teams that evolve to identify vertex partitions that maximize the sum of the weights of the cut edges.A total of 120 instances from the Biq Mac Library were evaluated, and the experiments showed that Golden Ball produces satisfactory solutions, with an average deviation of 37% on the Be set in 10 seconds and only 1.4% in 1200 seconds. As an evolutionary method, its results improve with more execution time. The approach was compared to the Biq Mac Library solver, a benchmark in the field, which ran for up to 10800 seconds.

References

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

Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM computing surveys (CSUR), 35(3):268–308.

Boros, E. and Hammer, P. L. (1991). The max-cut problem and quadratic 0–1 optimization; polyhedral aspects, relaxations and bounds. Annals of Operations Research, 33(3):151–180.

de Sousa, S., Haxhimusa, Y., and Kropatsch, W. G. (2013). Estimation of distribution algorithm for the max-cut problem. In Graph-Based Representations in Pattern Recognition: 9th IAPR-TC-15 International Workshop, GbRPR 2013, Vienna, Austria, May 15-17, 2013. Proceedings 9, pages 244–253. Springer.

Karp, R. M. (1972). Reducibility among combinatorial problems. complexity of computer computations (the ibm research symposia series).

Liers, F., Nieberg, T., and Pardella, G. (2011). Via minimization in vlsi chip design-application of a planar max-cut algorithm.

Miyazawa, F. K. and de Souza, C. C. (2015). Introdução à otimização combinatória. Sociedade Brasileira de Computação.

Osaba, E., Diaz, F., and Onieva, E. (2014). Golden ball: a novel meta-heuristic to solve combinatorial optimization problems based on soccer concepts. Applied intelligence, 41:145–166.

Otterbach, J. S., Manenti, R., Alidoust, N., Bestwick, A., Block, M., Bloom, B., Caldwell, S., Didier, N., Fried, E. S., Hong, S., et al. (2017). Unsupervised machine learning on a hybrid quantum computer. arXiv preprint arXiv:1712.05771.

Rendl, F., Rinaldi, G., and Wiegele, A. (2010). Solving Max-Cut to optimality by inter-secting semidefinite and polyhedral relaxations. Math. Programming, 121(2):307.

Wiegele, A. (2007). Biq mac library—a collection of max-cut and quadratic 0-1 programming instances of medium size. Preprint, 51.