Random-Key Optimizers for Quadratic Unconstrained Binary Optimization
Resumo
This paper proposes RK-QUBO, a random-key optimization framework for the Quadratic Unconstrained Binary Optimization (QUBO) problem. The approach encodes both the candidate solution and the algorithmic configuration of the decoder in a continuous random-key vector, allowing any continuous optimizer to jointly search over solutions and decoding strategies. Several decoding strategies are proposed, combining solution construction and local search. Experiments on benchmark instances with up to 2500 variables show that the proposed approach consistently outperforms an iterated local search baseline, while a performance gap relative to a state-of-the-art hybrid heuristic indicates room for improvement through more specialized decoder design.Referências
Alkhamis, T. M., Hasan, M., and Ahmed, M. A. (1998). Simulated annealing for the unconstrained quadratic pseudo-Boolean function. European Journal of Operational Research, 108(3):641–652.
Andrade, C. E., Toso, R. F., Gonçalves, J. F., and Resende, M. G. C. (2021). The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications. European Journal of Operational Research, 289(1):17–30.
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6(2):154–160.
Beasley, J. E. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069–1072.
Bennet, P., Doerr, C., Moreau, A., Rapin, J., Teytaud, F., and Teytaud, O. (2021). Never-grad: Black-box optimization platform. ACM SIGEVOlution, 14(1):8–15.
Brubaker, K., Booth, K. E., Schuetz, M. J. A., Loick, P., Shen, J., Ramamurthy, A., and Paschos, G. (2025). Optimization of next-day delivery coverage using constraint programming and random key optimizers. Preprint arXiv:2504.18749 [math.OC].
Carvalho, M., Melo, R. A., Resende, M. G. C., Santos, M. C., and Toso, R. F. (2025). The connected grundy coloring problem: Formulations and a local-search enhanced biased random-key genetic algorithm. Computers & Operations Research, 183:107136.
Chaves, A. A., Resende, M. G. C., Schmidt, C. E., Brubaker, J. K., Katzgraber, H. G., and Schuetz, M. J. A. (2026). Applying a random-key optimizer on mixed integer programs. Preprint arXiv:2602.22173 [math.OC].
Chaves, A. A., Resende, M. G. C., Schuetz, M. J. A., Brubaker, J. K., Katzgraber, H. G., de Arruda, E. F., and Silva, R. M. A. (2025). A random-key optimizer for combinatorial optimization. Journal of Heuristics, 31(4):32.
Chaves, A. A., Resende, M. G. C., and Silva, R. M. A. (2024). A random-key GRASP for combinatorial optimization. J. Nonlinear and Variational Analysis, 8:855–881.
de Souza, M. and Ritt, M. (2018). Automatic grammar-based design of heuristic algorithms for unconstrained binary quadratic programming. In European Conference on Evolutionary Computation in Combinatorial Optimization, pages 67–84. Springer.
de Souza, M. and Ritt, M. (2022). Improved regression models for algorithm configuration. In The Genetic and Evolutionary Computation Conference, pages 222–231.
dos Santos Becker, C. and de Souza, M. (2026). Roteamento de drones para busca de vítimas em cenários de desastre. Revista Tecnologia e Sociedade, 21(67):379–397.
Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2):109–133.
Festa, P., Guerriero, F., Resende, M. G. C., and Scalzo, E. (2023). A BRKGA with implicit path-relinking for the vehicle routing problem with occasional drivers and time windows. In Metaheuristics. MIC 2022, volume 13838 of Lecture Notes in Computer Science, pages 17–31. Springer.
Fontes, D. B. M. M. and Homayouni, S. M. (2023). A bi-objective multi-population biased random-key genetic algorithm for joint scheduling quay cranes and speed adjustable vehicles in container terminals. Flexible Services and Manufacturing Journal, 35(1):241–268.
Glover, F., Kochenberger, G., and Du, Y. (2019). Quantum bridge analytics I: A tutorial on formulating and using QUBO models. 4OR, 17(4):335–371.
Glover, F., Kochenberger, G. A., and Alidaee, B. (1998). Adaptive memory tabu search for binary quadratic programs. Management Science, 44(3):336–345.
Glover, F., Lü, Z., and Hao, J.-K. (2010). Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR, 8(3):239–253.
Gonçalves, J. F. and Resende, M. G. C. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Gonçalves, J. F. and Wäscher, G. (2020). A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects. European Journal of Operational Research, 286(3):867–882.
Homayouni, S. M., Fontes, D. B. M. M., and Gonçalves, J. F. (2023). A multistart biased random-key genetic algorithm for the flexible job shop scheduling problem with transportation. International Transactions in Operational Research.
Kochenberger, G., Hao, J.-K., Glover, F., Lewis, M., Lü, Z., Wang, H., and Wang, Y. (2014). The unconstrained binary quadratic programming problem: A survey. Journal of Combinatorial Optimization, 28(1):58–81.
Londe, M. A., Pessoa, L. S., Andrade, C. E., and Resende, M. G. C. (2024). Early years of biased random-key genetic algorithms: A systematic review. Journal of Global Optimization.
Mangussi, A. D., Pola, H., Macedo, H. G., Julião, L. A., Proença, M. P. T., Gianfelice, P. R. L., Salezze, B. V., and Chaves, A. A. (2023). Meta-heurísticas via chaves aleatórias aplicadas ao problema de localização de hubs em árvore. In Anais do Simpósio Brasileiro de Pesquisa Operacional, São José dos Campos. Galoá.
Melo, R. A., Queiroz, M. F., and Ribeiro, C. C. (2023). A biased random-key genetic algorithm for the minimum quasi-clique partitioning problem. Annals of Operations Research.
Punnen, A. P., editor (2022). The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications. Springer.
Rapin, J. and Teytaud, O. (2018). Nevergrad - A gradient-free optimization platform. [link].
Santos, N. A., Jeske, M., and Chaves, A. A. (2026). Random-key optimizer and linearization for the quadratic multiple constraints variable-sized bin packing problem. Computers & Operations Research, page 107482.
Schuetz, M. J. A., Brubaker, J. K., Montagu, H., van Dijk, Y., Klepsch, J., Ross, P., Luckow, A., Resende, M. G. C., and Katzgraber, H. G. (2022). Optimization of robot trajectory planning with nature-inspired and hybrid quantum algorithms. Physical Review Applied, 18:054045.
Silva, E. M., Chaves, A. A., de Araujo, S. A., and Jans, R. (2025). Random-key optimizer with reinforcement learning for the capacitated multi-period cutting stock problem with setup cost. Computers & Operations Research, 183:107159.
Wang, Y., Lü, Z., Glover, F., and Hao, J.-K. (2012). Path relinking for unconstrained binary quadratic programming. European Journal of Operational Research, 223(3):595–604.
Andrade, C. E., Toso, R. F., Gonçalves, J. F., and Resende, M. G. C. (2021). The multi-parent biased random-key genetic algorithm with implicit path-relinking and its real-world applications. European Journal of Operational Research, 289(1):17–30.
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6(2):154–160.
Beasley, J. E. (1990). OR-library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11):1069–1072.
Bennet, P., Doerr, C., Moreau, A., Rapin, J., Teytaud, F., and Teytaud, O. (2021). Never-grad: Black-box optimization platform. ACM SIGEVOlution, 14(1):8–15.
Brubaker, K., Booth, K. E., Schuetz, M. J. A., Loick, P., Shen, J., Ramamurthy, A., and Paschos, G. (2025). Optimization of next-day delivery coverage using constraint programming and random key optimizers. Preprint arXiv:2504.18749 [math.OC].
Carvalho, M., Melo, R. A., Resende, M. G. C., Santos, M. C., and Toso, R. F. (2025). The connected grundy coloring problem: Formulations and a local-search enhanced biased random-key genetic algorithm. Computers & Operations Research, 183:107136.
Chaves, A. A., Resende, M. G. C., Schmidt, C. E., Brubaker, J. K., Katzgraber, H. G., and Schuetz, M. J. A. (2026). Applying a random-key optimizer on mixed integer programs. Preprint arXiv:2602.22173 [math.OC].
Chaves, A. A., Resende, M. G. C., Schuetz, M. J. A., Brubaker, J. K., Katzgraber, H. G., de Arruda, E. F., and Silva, R. M. A. (2025). A random-key optimizer for combinatorial optimization. Journal of Heuristics, 31(4):32.
Chaves, A. A., Resende, M. G. C., and Silva, R. M. A. (2024). A random-key GRASP for combinatorial optimization. J. Nonlinear and Variational Analysis, 8:855–881.
de Souza, M. and Ritt, M. (2018). Automatic grammar-based design of heuristic algorithms for unconstrained binary quadratic programming. In European Conference on Evolutionary Computation in Combinatorial Optimization, pages 67–84. Springer.
de Souza, M. and Ritt, M. (2022). Improved regression models for algorithm configuration. In The Genetic and Evolutionary Computation Conference, pages 222–231.
dos Santos Becker, C. and de Souza, M. (2026). Roteamento de drones para busca de vítimas em cenários de desastre. Revista Tecnologia e Sociedade, 21(67):379–397.
Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6(2):109–133.
Festa, P., Guerriero, F., Resende, M. G. C., and Scalzo, E. (2023). A BRKGA with implicit path-relinking for the vehicle routing problem with occasional drivers and time windows. In Metaheuristics. MIC 2022, volume 13838 of Lecture Notes in Computer Science, pages 17–31. Springer.
Fontes, D. B. M. M. and Homayouni, S. M. (2023). A bi-objective multi-population biased random-key genetic algorithm for joint scheduling quay cranes and speed adjustable vehicles in container terminals. Flexible Services and Manufacturing Journal, 35(1):241–268.
Glover, F., Kochenberger, G., and Du, Y. (2019). Quantum bridge analytics I: A tutorial on formulating and using QUBO models. 4OR, 17(4):335–371.
Glover, F., Kochenberger, G. A., and Alidaee, B. (1998). Adaptive memory tabu search for binary quadratic programs. Management Science, 44(3):336–345.
Glover, F., Lü, Z., and Hao, J.-K. (2010). Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR, 8(3):239–253.
Gonçalves, J. F. and Resende, M. G. C. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Gonçalves, J. F. and Wäscher, G. (2020). A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects. European Journal of Operational Research, 286(3):867–882.
Homayouni, S. M., Fontes, D. B. M. M., and Gonçalves, J. F. (2023). A multistart biased random-key genetic algorithm for the flexible job shop scheduling problem with transportation. International Transactions in Operational Research.
Kochenberger, G., Hao, J.-K., Glover, F., Lewis, M., Lü, Z., Wang, H., and Wang, Y. (2014). The unconstrained binary quadratic programming problem: A survey. Journal of Combinatorial Optimization, 28(1):58–81.
Londe, M. A., Pessoa, L. S., Andrade, C. E., and Resende, M. G. C. (2024). Early years of biased random-key genetic algorithms: A systematic review. Journal of Global Optimization.
Mangussi, A. D., Pola, H., Macedo, H. G., Julião, L. A., Proença, M. P. T., Gianfelice, P. R. L., Salezze, B. V., and Chaves, A. A. (2023). Meta-heurísticas via chaves aleatórias aplicadas ao problema de localização de hubs em árvore. In Anais do Simpósio Brasileiro de Pesquisa Operacional, São José dos Campos. Galoá.
Melo, R. A., Queiroz, M. F., and Ribeiro, C. C. (2023). A biased random-key genetic algorithm for the minimum quasi-clique partitioning problem. Annals of Operations Research.
Punnen, A. P., editor (2022). The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications. Springer.
Rapin, J. and Teytaud, O. (2018). Nevergrad - A gradient-free optimization platform. [link].
Santos, N. A., Jeske, M., and Chaves, A. A. (2026). Random-key optimizer and linearization for the quadratic multiple constraints variable-sized bin packing problem. Computers & Operations Research, page 107482.
Schuetz, M. J. A., Brubaker, J. K., Montagu, H., van Dijk, Y., Klepsch, J., Ross, P., Luckow, A., Resende, M. G. C., and Katzgraber, H. G. (2022). Optimization of robot trajectory planning with nature-inspired and hybrid quantum algorithms. Physical Review Applied, 18:054045.
Silva, E. M., Chaves, A. A., de Araujo, S. A., and Jans, R. (2025). Random-key optimizer with reinforcement learning for the capacitated multi-period cutting stock problem with setup cost. Computers & Operations Research, 183:107159.
Wang, Y., Lü, Z., Glover, F., and Hao, J.-K. (2012). Path relinking for unconstrained binary quadratic programming. European Journal of Operational Research, 223(3):595–604.
Publicado
19/10/2026
Como Citar
FROEHLICH, Érico; SOUZA, Marcelo de.
Random-Key Optimizers for Quadratic Unconstrained Binary Optimization. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 23. , 2026, Cuiabá/MT.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 2691-2702.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2026.30153.
